Computable Families of Sets in the Ershov Hierarchy Without Principal Numberings

1. S. S. Goncharov and A. Sorbi, “Generalized computable numerations and nontrivial Rogers semilattices” [in Russian], Algebra Logika 36, No. 6, 621–641 (1997); English transl.: Algebra Logic 36, No. 6, 359–369 (1997).

2. S. S. Goncharov, S. Lempp, and D. R. Solomon, “Friedberg numberings of families of n-computably enumerable sets” [in Russian], Algebra Logika 41, No. 2, 143–154 (2002); English transl.: Algebra Logic 41, No. 2, 81–86 (2002).

3. S. A. Badaev amd S. Lempp, “A decomposition of the Rogers semilattice of a family of d.c.e. sets” J. Symb. Log. 74, No. 2, 618–640 (2009).

4. S. S. Ospichev, “Infinite family of ∑ ^− 1 _a -sets with a unique computable numbering” [in Russian], Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform. 11, No. 2, 89–92 (2011); English transl.: J. Math. Sci., 188, No. 4, 449–451 (2013).

5. S. S. Ospichev, “Properties of numberings in various levels of the Ershov hierarchy” [in Russian], Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform. 10, No. 4, 125–132 (2010); English transl.: J. Math. Sci., 188, No. 4, 441–448 (2013).

6. M. Manat and A. Sorbi, “Positive undecidable numberings in the Ershov hierarchy” [in Russian], Algebra Logika 50, No. 6, 759–780 (2011); English transl.: Algebra Logic 50, No. 6, 512–525 (2012).

7. K. Sh. Abeshev, S. A. Badaev, and M. Manat, “Families without minimal numberings” [in Russian], Algebra Logika 53, No. 4, 427–450 (2014); English transl.: Algebra Logic 53, No. 4, 271–286 (2014).

8. K. Sh. Abeshev, “On the existence of universal numberings for finite families of d.c.e. sets,” Math. Log. Q. 60, No. 3, 161–167 (2014).

   Article  MathSciNet  MATH  Google Scholar 

9. S. A. Badaev and S. S. Goncharov, “Rogers semilattices of families of arithmetic sets” [in Russian], Algebra Logika 40, No. 5, 507–522 (2001); English transl.: Algebra Logic 40, No. 5, 283–291 (2001).

10. S. A. Badaev, S. S. Goncharov, and A. Sorbi, “Elementary theories for Rogers semilattices” [in Russian], Algebra Logika 44, No. 3, 261–268 (2005); English transl.: Algebra Logic 44, No. 3, 143–147 (2005).

11. S. A. Badaev, S. S. Goncharov, and A. Sorbi, “Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy” [in Russian], Algebra Logika 45, No. 6, 637–654 (2006); English transl.: Algebra Logic 45, No. 6, 361–370 (2006).

12. S. A. Badaev and S. Yu. Podzorov, “Minimal coverings in the Rogers semilattices of ∑ ⁰ _n -computable numberings” [in Russian], Sib. Mat. Zh. 43, No. 4, 769–778 (2002); English transl.: Sib. Math. J. 43, No. 4, 616–622 (2002).

13. S. Yu. Podzorov, “Local structure of Rogers semilattices of ∑ ⁰ _n -computable numberings” [in Russian], Algebra Logika 44, No. 2, 148–172 (2005); English transl.: Algebra Logic 44, No. 2, 82–94 (2005).

14. S. A. Badaev and S. S. Goncharov, “Computability and numberings,” In: New Computational Paradigms. Changing Conceptions of What is Computable, pp. 19–34, Springer, New York (2008).

15. N. A. Baklanova, “Undecidability of elementary theories of Rogers semilattices on the limit levels of the arithmetical hierarchy” [in Russian], Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform. 11, No. 4, 3–7 (2011);

16. N. A. Baklanova, “Minimal elements and minimal coverings in the Rogers semilattice of computable numberings in the hyperarithmetical hierarchy” [in Russian], Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform. 11, No. 3, 77–84 (2011);

17. Yu. L. Ershov, “On a hierarchy of sets. III” [in Russian], Algebra Logika 9, No. 1, 34–51 (1970); English transl.: Algebra Logic 9, No. 1, 20–31 (1970).

18. Yu. L. Ershov, Theory of Numberings [in Russian], Nauka, Moscow (1977);

19. V. L. Selivanov, “Hierarchy of limiting computations” [in Russian], Sib. Mat. Zh. 25, No. 5, 146–156 (1984); English transl.: Sib. Math. J. 25, No. 5, 798–806 (1984).

Download references