Geodesic
Noncancellable, singular, and conjugate degrees
Algebra i logika, Tome 56 (2017) no. 3, pp. 275-299.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study degree structures of stronger algorithmic reducibilities inside the degrees of weaker algorithmic ones. Results in this area are reviewed for algorithmic reducibilities $m$-, $1$-, $tt$-, $wtt$-, $T$-, $e$-, $s$-, $Q$-, and we formulate questions that are still not settled for these. A computably enumerable $Q$-degree which consists of one computably enumerable $m$-degree is constructed.
Keywords: $Q$-reducibility, $m$-reducibility, computably enumerable degrees, noncancellable degrees, singular degrees, conjugate degrees. 
@article{AL_2017_56_3_a0,
     author = {I. I. Batyrshin},
     title = {Noncancellable, singular, and conjugate degrees},
     journal = {Algebra i logika},
     pages = {275--299},
     publisher = {mathdoc},
     volume = {56},
     number = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2017_56_3_a0/}
}
TY  - JOUR
AU  - I. I. Batyrshin
TI  - Noncancellable, singular, and conjugate degrees
JO  - Algebra i logika
PY  - 2017
SP  - 275
EP  - 299
VL  - 56
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2017_56_3_a0/
LA  - ru
ID  - AL_2017_56_3_a0
ER  - 
%0 Journal Article
%A I. I. Batyrshin
%T Noncancellable, singular, and conjugate degrees
%J Algebra i logika
%D 2017
%P 275-299
%V 56
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2017_56_3_a0/
%G ru
%F AL_2017_56_3_a0
I. I. Batyrshin. Noncancellable, singular, and conjugate degrees. Algebra i logika, Tome 56 (2017) no. 3, pp. 275-299. http://geodesic.mathdoc.fr/item/AL_2017_56_3_a0/

[1] R. G. Downey, S. Lempp, “Contiguity and distributivity in the enumerable Turing degrees”, J. Symb. Log., 62:4 (1997), 1215–1240 | DOI | MR | Zbl

[2] R. Sh. Omanadze, I. O. Chitaia, “$Q_1$-degrees of c.e. sets”, Arch. Math. Logic, 51:5/6 (2012), 503–515 | DOI | MR | Zbl

[3] R. I. Soare, Recursively enumerable sets and degrees, Perspect. Math. Log., Omega Series, Springer-Verlag, Heidelberg a.o., 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni, Kazanskoe matem. ob-vo, Kazan, 2000 | DOI | MR | Zbl | MR

[4] P. Odifreddi, Classical recursion theory. The theory of functions and sets of natural numbers, Stud. Log. Found. Math., 125, North-Holland, Amsterdam etc., 1989 | MR | Zbl

[5] P. G. Odifreddi, Classical recursion theory, v. II, Stud. Log. Found. Math., 143, Elsevier, Amsterdam, 1999 | MR | Zbl

[6] J. Myhill, “Creative sets”, Z. Math. Logik Grundlagen Math., 1 (1955), 97–108 | DOI | MR | Zbl

[7] Yu. L. Ershov, “Pozitivnye ekvivalentnosti”, Algebra i logika, 10:6 (1971), 620–650

[8] G. N. Kobzev, “O $r$-otdelimykh mnozhestvakh”, Issledovaniya po matematicheskoi logike i teorii algoritmov, 1, Tbilisi, 1975, 19–30 | MR

[9] R. Downey, “On irreducible $m$-degrees”, Rend. Semin. Mat. Torino, 51:2 (1993), 109–112 | MR | Zbl

[10] P. R. Young, “Linear orderings under one-one reducibility”, J. Symb. Log., 31 (1966), 70–85 | DOI | MR | Zbl

[11] C. G. Jockusch (jun.), “Relationships between reducibilities”, Trans. Am. Math. Soc., 142 (1969), 229–237 | DOI | MR | Zbl

[12] R. G. Downey, “Recursively enumerable $m$- and $tt$-degrees. I: The quantity of $m$-degrees”, J. Symb. Log., 54:2 (1989), 533–567 | DOI | MR | Zbl

[13] A. N. Degtev, “O $tt$- i $m$-stepenyakh”, Algebra i logika, 12:2 (1973), 143–161 | MR

[14] P. Cholak, R. G. Downey, “Recursively enumerable $m$- and $tt$-degrees. III: Realizing all finite distributive lattices”, J. Lond. Math. Soc. II Ser., 50:3 (1994), 440–453 | DOI | MR | Zbl

[15] A. H. Lachlan, “$wtt$-complete sets are not necessarily $tt$-complete”, Proc. Am. Math. Soc., 48:2 (1975), 429–434 | MR | Zbl

[16] P. F. Cohen, Weak truth-table reducibility and the pointwise ordering of 1-1 recursive functions, Ph. D. thesis, Univ. Illinois, Urbana, 1975 | MR | Zbl

[17] G. N. Kobzev, “Sootnosheniya mezhdu rekursivno perechislimymi $tt$- i $w$-stepenyami”, Soob. AN GSSR, 84:3 (1976), 585–586

[18] R. E. Ladner, “A completely mitotic nonrecursive r.e. degree”, Trans. Am. Math. Soc., 184 (1973), 479–507 | DOI | MR

[19] R. G. Downey, “$\Delta^0_2$ degrees and transfer theorems”, Ill. J. Math., 31 (1987), 419–427 | MR | Zbl

[20] R. E. Ladner, L. P. Sasso, “The weak truth table degrees of recursively enumerable sets”, Ann. Math. Logic, 8 (1975), 429–448 | DOI | MR | Zbl

[21] S. D. Zakharov, “O $e$- i $s$-stepenyakh”, Algebra i logika, 23:4 (1984), 395–406 | MR | Zbl

[22] S. D. Zakharov, “O stepenyakh svodimostei po perechislimosti”, Algebra i logika, 25:2 (1986), 121–135 | Zbl

[23] S. D. Zakharov, “O vnutrennem stroenii $e$-stepenei”, Devyataya Vsesoyuz. konf. matem. logike, posv. 85-letiyu A. A. Markova, Tez. dokl. (Leningrad, 27–29 sent. 1988 g.), Nauka, Leningr. otd-nie, L., 1988, 61 | MR

[24] S. S. Marchenkov, “Ob odnom klasse nepolnykh mnozhestv”, Matem. zametki, 20:4 (1976), 473–478 | MR | Zbl

[25] O. V. Belegradek, “Ob algebraicheski zamknutykh gruppakh”, Algebra i logika, 13:3 (1974), 239–255 | MR | Zbl

[26] O. V. Belegradek, “Higman's embedding theorem in a general setting and its application to existentially closed algebras”, Notre Dame J. Formal Logic, 37:4 (1996), 613–624 | DOI | MR | Zbl

[27] M. Kummer, “Kolmogorov complexity and instance complexity of recursively enumerable sets”, SIAM J. Comput., 25:6 (1996), 1123–1143 | DOI | MR | Zbl

[28] I. I. Batyrshin, “Quasi-completeness and functions without fixed-points”, Math. Log. Q., 52:6 (2006), 595–601 | DOI | MR | Zbl

[29] R. Downey, G. LaForte, A. Nies, “Computably enumerable sets and quasireducibility”, Ann. Pure Appl. Logic, 95:1–3 (1998), 1–35 ; “Addendum”, Ann. Pure Appl. Logic, 98:1–3 (1999), 295 | DOI | MR | Zbl | DOI | MR

[30] R. Sh. Omanadze, “Quasi-degrees of recursively enumerable sets”, Computability and models. Perspectives east and west, Univ. Ser. Math., eds. S. B. Cooper, S. S. Goncharov, Kluwer Academic/Plenum Publishers, New York, 2003, 289–319 | MR

[31] M. M. Arslanov, R. Sh. Omanadze, “$Q$-degrees of n-c.e. sets”, Ill. J. Math., 51:4 (2007), 1189–1206 | MR | Zbl

[32] M. M. Arslanov, I. I. Batyrshin, R. Sh. Omanadze, “Structural properties of $Q$-degrees of n-c.e. sets”, Ann. Pure Appl. Logic, 156:1 (2008), 13–20 | DOI | MR | Zbl

[33] I. I. Batyrshin, “Izolirovannye 2-vychislimo perechislimye $Q$-stepeni”, Izv. vuzov. Matem., 2010, no. 4, 3–9 | MR | Zbl

[34] I. I. Batyrshin, “Non-isolated quasi-degrees”, Math. Log. Q., 55:6 (2009), 587–597 | DOI | MR | Zbl

[35] M. L. Affatato, T. F. Kent, A. Sorbi, “Undecidability of local structures of $s$-degrees and $Q$-degrees”, Tbil. Math. J., 1 (2008), 15–32 | MR | Zbl

[36] D. Marsibilio, A. Sorbi, “Singleton enumeration reducibility and arithmetic”, J. Logic Comput., 23:6 (2013), 1267–1292 | DOI | MR | Zbl

[37] R. Sh. Omanadze, “Sootnosheniya mezhdu nekotorymi svodimostyami”, Algebra i logika, 33:6 (1994), 681–688 | MR | Zbl

[38] I. I. Batyrshin, “$Q$-svodimost i $m$-svodimost na vychislimo perechislimykh mnozhestvakh”, Sib. matem. zh., 55:6 (2014), 1221–1239 | MR | Zbl

[39] R. Sh. Omanadze, “Slozhnostnye svoistva rekursivno perechislimykh mnozhestv i $bsQ$-polnota”, Matem. zametki, 68:4 (2000), 554–559 | DOI | MR | Zbl