Geodesic
Initial Segments in Rogers Semilattices of $\Sigma^0_n$-Computable Numberings
Algebra i logika, Tome 42 (2003) no. 2, pp. 211-226.

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

S. Goncharov and S. Badaev showed that for $n\geqslant 2$, there exist infinite families whose Rogers semilattices contain ideals without minimal elements. In this connection, the question was posed as to whether there are examples of families that lack this property. We answer this question in the negative. It is proved that independently of a family chosen, the class of semilattices that are principal ideals of the Rogers semilattice of that family is rather wide: it includes both a factor lattice of the lattice of recursively enumerable sets modulo finite sets and a family of initial segments in the semilattice of $m$-degrees generated by immune sets.
Keywords: Rogers semilattice, recursively enumerable set, $m$-degree.
Mots-clés : immune set 
@article{AL_2003_42_2_a4,
     author = {S. Yu. Podzorov},
     title = {Initial {Segments} in {Rogers} {Semilattices} of $\Sigma^0_n${-Computable} {Numberings}},
     journal = {Algebra i logika},
     pages = {211--226},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2003_42_2_a4/}
}
TY  - JOUR
AU  - S. Yu. Podzorov
TI  - Initial Segments in Rogers Semilattices of $\Sigma^0_n$-Computable Numberings
JO  - Algebra i logika
PY  - 2003
SP  - 211
EP  - 226
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2003_42_2_a4/
LA  - ru
ID  - AL_2003_42_2_a4
ER  - 
%0 Journal Article
%A S. Yu. Podzorov
%T Initial Segments in Rogers Semilattices of $\Sigma^0_n$-Computable Numberings
%J Algebra i logika
%D 2003
%P 211-226
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2003_42_2_a4/
%G ru
%F AL_2003_42_2_a4
S. Yu. Podzorov. Initial Segments in Rogers Semilattices of $\Sigma^0_n$-Computable Numberings. Algebra i logika, Tome 42 (2003) no. 2, pp. 211-226. http://geodesic.mathdoc.fr/item/AL_2003_42_2_a4/

[1] S. S. Goncharov, A. Sorbi, “Obobschenno vychislimye numeratsii i netrivialnye polureshetki Rodzhersa”, Algebra i logika, 36:6 (1997), 621–641 | MR | Zbl

[2] Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR

[3] S. A. Badaev, S. S. Goncharov, “O polureshetkakh Rodzhersa semeistv arifmeticheskikh mnozhestv”, Algebra i logika, 40:5 (2001), 507–522 | MR | Zbl

[4] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR

[5] S. A. adaev, “Minimalnye numeratsii”, Matematicheskaya logika i teoriya algoritmov, Trudy in-ta matem. SO RAN, 25, 1993, 3–34

[6] Yu. L. Ershov, “Verkhnyaya polureshetka numeratsii konechnogo mnozhestva”, Algebra i logika, 14:3 (1975), 258–284 | MR | Zbl

[7] A. H. Lachlan, “Initial segments of many-one degrees”, Can. J. Math., 22:1 (1970), 75–85 | MR | Zbl

[8] A. H. Lachlan, “Recursively enumerable many-one degrees”, Algebra i logika, 11:3 (1972), 326–358 | MR | Zbl