RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sibirsk. Mat. Zh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sibirsk. Mat. Zh., 2014, Volume 55, Number 6, Pages 1221–1239 (Mi smj2600)  

This article is cited in 1 scientific paper (total in 1 paper)

$Q$-reducibility and $m$-reducibility on computably enumerable sets

I. I. Batyrshin

Kazan (Volga Region) Federal University, Kazan, Russia

Abstract: We study the distinctions between $Q$-reducibility and $m$-reducibility on computably enumerable sets. We construct a noncomputable $m$-incomplete computably enumerable set $B$ such that all computably enumerable sets $A\le_QB$ satisfy $A\le_mB$. We prove that for every noncomputable computably enumerable set $A$ there exists a computably enumerable set $B$ such that $A\le_QB$ but $A\not\le_mB$. We prove that for every simple set $B$ there exists a computably enumerable set $A$ such that $A\le_QB$ but $A\not\le_mB$. The last result implies in particular that the $Q$-degree of every simple set contains infinitely many computably enumerable $m$-degrees.

Keywords: $Q$-reducibility, $m$-reducibility, computably enumerable set, simple set.

Full text: PDF file (415 kB)
References: PDF file   HTML file

English version:
Siberian Mathematical Journal, 2014, 55:6, 995–1008

Bibliographic databases:

UDC: 510.5
Received: 27.11.2013

Citation: I. I. Batyrshin, “$Q$-reducibility and $m$-reducibility on computably enumerable sets”, Sibirsk. Mat. Zh., 55:6 (2014), 1221–1239; Siberian Math. J., 55:6 (2014), 995–1008

Citation in format AMSBIB
\Bibitem{Bat14}
\by I.~I.~Batyrshin
\paper $Q$-reducibility and $m$-reducibility on computably enumerable sets
\jour Sibirsk. Mat. Zh.
\yr 2014
\vol 55
\issue 6
\pages 1221--1239
\mathnet{http://mi.mathnet.ru/smj2600}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3330031}
\transl
\jour Siberian Math. J.
\yr 2014
\vol 55
\issue 6
\pages 995--1008
\crossref{https://doi.org/10.1134/S0037446614060032}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000346495200003}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84919423115}


Linking options:
  • http://mi.mathnet.ru/eng/smj2600
  • http://mi.mathnet.ru/eng/smj/v55/i6/p1221

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. I. I. Batyrshin, “Noncancellable, singular, and conjugate degrees”, Algebra and Logic, 56:3 (2017), 181–196  mathnet  crossref  crossref  isi
  • Сибирский математический журнал Siberian Mathematical Journal
    Number of views:
    This page:132
    Full text:39
    References:25
    First page:7

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020