Isolation from side in $2$-computably enumerable degrees

M. M. Yamaleev

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 8 (2020), pp. 81-86.

Résumé

In this work we consider isolation from side in different degree structures, in particular, in the $2$-computably enumerable $wtt$-degrees and in low Turing degrees. Intuitively, a $2$-computably enumerable degree is isolated from side if all computably enumerable degrees from its lower cone are bounded from above by some computably enumerable degree which is incomparable with the given one. It is proved that any properly $2$-computably enumerable $wtt$-degree is isolated from side by some computable enumerable $wtt$-degree. Also it is shown that the same result holds for the low $2$-computable enumerable Turing degrees.

Détail

Mots-clés : $2$-computably enumerable set, $wtt$-degree, Turing degree, isolation from side.

Bibliographie

[1] Cooper B., Yi X., Isolated d.r.e. degrees, Preprint ser. 17, Univ. Leeds, Dept of Pure Math., Leeds, 1995 | Zbl

[2] Sacks G. E., “The recursively enumerable degrees are dense”, Ann. Math., 80:2 (1964), 300–312 | DOI | MR | Zbl

[3] Wu G., “Isolation and lattice embedding”, J. Symb. Logic, 67 (2002), 1055–1064 | DOI | MR | Zbl

[4] Ding D., Qian L., “Isolated d.r.e. degrees are dense in r.e. degree structure”, Arch. Math. Logic, 36:1 (1996), 1–10 | MR | Zbl

[5] LaForte G., “The isolated d.r.e. degrees are dense in the r.e. degrees”, Math. Logic Quart., 42 (1996), 83–103 | DOI | MR | Zbl

[6] Arslanov M. M., Lempp S., Shore R. A., “On isolating r.e. and isolated d-r.e. degrees”, Computability, enumerability, unsolvability, London Math. Society, Lect. Note Ser., 224, 1996, 61–80 | MR | Zbl

[7] Cooper B., Li A., “Turing Definability in the Ershov Hierarchy”, J. London Math. Society, 66:3 (2002), 513–538 | DOI | MR

[8] Arslanov M. M., “Definability and Elementary Equivalence in the Ershov Difference Hierarchy”, Lect. Notes in Logic, 32 (2009), 1–17 | MR | Zbl

[9] Arslanov M. M., Yamaleev M. M., “On the problem of definability of the computably enumerable degrees in the difference hierarchy”, Lobachevskii J. Math., 39:5 (2018), 634–638 | DOI | MR | Zbl

[10] Yang Y., Yu L., “On $\Sigma_1$-structural differences among Ershov hierarchies”, J. Symb. Logic, 71 (2006), 1223–1236 | MR | Zbl

[11] Cai M., Shore R. A., Slaman T. A., “The $n$-r.e. degrees: undecidability and $\Sigma_1$ substructures”, J. Math. Logic, 12 (2012), 1–30 | DOI | MR | Zbl

[12] Wu G., Yamaleev M. M., “Isolation: motivations and applications”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauk, 154, no. 2, 2012, 204–217 | MR

[13] Soar R. I., Vychislimo-perechislimye mnozhestva i stepeni, Kazansk. matem. o-vo, Kazan, 2000

[14] Robinson R. W., “Interpolation and embedding in the recursively enumerable degrees”, Ann. Math., 93:2 (1971), 285–314 | MR | Zbl