Skip to main content
SpringerLink
Log in

Precomplete Numberings

  • Published:
Journal of Mathematical Sciences Aims and scope Submit manuscript

Abstract

In this survey, we discuss the theory of precomplete numberings, which appear frequently in computability theory. Precomplete numberings are closely related to some versions of the fixed-point theorem having an important methodological value. Sometimes, this allows one to replace cumbersome proofs based on the so-called priority method by elegant and simple applications of this theorem. In a sense, this paper covers the part of computability theory that may be developed by elementary methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. B. Akhtiamov, “Index sets in Ershov hierarchy,” in: Probabilistic Methods and Cybernetics [in Russian], 24, Kazan State Univ., Kazan (1990), pp. 3–15.

  2. M. M. Arslanov, “Some generalizations of the fixed-point theorem,” Izv. Vysch. Uchebh. Zaved. Mat., 228, No. 5 (1981).

  3. M. M. Arslanov, “On a hierarchy of degrees of unsolvability,” in: Probabilistic Methods and Cybernetics [in Russian], 18, Kazan State Univ., Kazan (1982), pp. 10–17.

  4. M. M. Arslanov, Recursively Enumerable Sets and Degrees [in Russian], Kazan State Univ., Kazan (1986).

    MATH  Google Scholar 

  5. M. M. Arslanov, “Completeness in the arithmetical hierarchy and fixed points,” Algebra Logika, 28, 3–18 (1989).

    Article  MathSciNet  MATH  Google Scholar 

  6. M. M. Arslanov, R. F. Nadyrov, and V. D. Solov’ev, “A completeness criterion for recursively enumerable sets and some generalizations of the fixed-point theorem,” Izv. Vyssh. Ucheb. Zav. Mat., 179, No. 4, 3–7 (1977).

    MATH  Google Scholar 

  7. M. M. Arslanov and V. D. Solov’ev, “Effectivizations of definitions of classes of simple sets,” in: Algorithms and Automata [in Russian], Kazan State Univ. (1978), pp. 100–108.

  8. S. Badaev, S. Goncharov, and A. Sorbi, “Completeness and universality of arithmetical numberings,” in: Computability and Models (S. B. Cooper and S. S. Goncharov, eds.), Kluwer Academic–Plenum Publishers, New York (2003), pp. 11–44.

  9. S. Badaev, S. Goncharov, and A. Sorbi, “Algebraic properties of Rogers semilattices of arithmetical numberings,” in: Computability and Models (S. B. Cooper and S. S. Goncharov, eds.), Kluwer Academic–Plenum Publishers, New York (2003), pp. 45–78.

  10. C. Bernardi and A. Sorbi, “Classifying positive equivalence relations,” J. Symb. Logic, 48, 529–538 (1983).

    Article  MathSciNet  MATH  Google Scholar 

  11. U. Brandt, “Index sets in the arithmetical hierarchy,” Ann. Pure Appl. Logic, 37, 101—110 (1988).

    Article  MathSciNet  MATH  Google Scholar 

  12. S. B. Cooper, Degrees of Unsolvability, Ph.D. thesis, Leicester University, Leicester, England (1971).

  13. S. D. Denisov, “On m-degrees of recursively enumerable sets,” Algebra Logika, 9, 422–427 (1970).

    Article  MathSciNet  Google Scholar 

  14. S. G. Dvornikov, “Precomplete enumerated sets,” Sib. Mat. Zh., 20, 1303—1305 (1979).

    MathSciNet  MATH  Google Scholar 

  15. S. G. Dvornikov, “The lattice of degrees of separability,” in: Proc. 7th All-Union Conf. in Mathematical Logic [in Russian], Novosibirsk (1984), pp. 55.

  16. R. L. Epstein, R. Haas, and R. Kramer, “Hierarchies of sets and degrees below 0’,” in: Logic Year 1979-80. University of Connecticut (M. Lerman, J. H. Schmerl, and R. I. Soare, eds.), Springer-Verlag, Berlin (1981), pp. 32–48.

  17. Yu. L. Ershov, “On a hierarchy of sets, 1,” Algebra Logika, 7, No. 1, 47–74 (1968).

  18. Yu. L. Ershov, “On a hierarchy of sets, 2,” Algebra Logika, 7, No. 4, 15–47 (1968).

  19. Yu. L. Ershov, “On a hierarchy of sets, 3,” Algebra Logika, 9, No. 1, 34–51 (1970).

  20. Yu. L. Ershov, “Completely numbered sets,” Sib. Mat. Zh., 10, 1048–1064 (1969).

    Google Scholar 

  21. Yu. L. Ershov, “Theorie der Numerierungen, 1,” Z. Math. Logik, 19, 289–388 (1973).

    Article  MathSciNet  MATH  Google Scholar 

  22. Ershov Yu. L., “Theorie der Numerierungen, 2,” Z. Math. Logik, 21, 473–584 (1975).

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  24. J. Grassin, “Index sets in Ershov hierarchy,” J. Symb. Logic, 39, No. 1, 97–104 (1974).

    Article  MathSciNet  MATH  Google Scholar 

  25. L. Hay, “Index sets of finite classes of recursively enumerable sets,” J. Symb. Logic, 34, 39–44 (1969).

    Article  MathSciNet  MATH  Google Scholar 

  26. L. Hay, “A discrete chain of degrees of index sets,” J. Symb. Logic, 37, 139–149 (1972).

    Article  MathSciNet  MATH  Google Scholar 

  27. L. Hay, “Discrete ω-sequences of index sets,” Trans. Am. Math. Soc., 183, 293–311 (1973).

    MathSciNet  MATH  Google Scholar 

  28. L. Hay, “Index sets in 0’,” Algebra Logika, 12, 713–729 (1973).

    Article  MathSciNet  MATH  Google Scholar 

  29. L. Hay, “A noninitial segment of index sets,” J. Symb. Logic, 39, 209–224 (1974).

    Article  MathSciNet  MATH  Google Scholar 

  30. L. Hay, “Rice theorems for d.c.e. sets,” Can. J. Math., 27, 352–365 (1975).

    Article  MathSciNet  MATH  Google Scholar 

  31. L. Hay, “Boolean combinations of c.e. sets,” J. Symb. Logic, 41, 255–278 (1976).

    Article  MathSciNet  Google Scholar 

  32. L. Hay and N. Johnson, “Extensional characterization of index sets,” Z. Math. Logik, 25, 227—234 (1979).

    Article  MathSciNet  MATH  Google Scholar 

  33. C. G. Jockusch Jr., “Degrees of functions without fixed points,” in: Proc. 8th Congress for LMPS, 1, Moscow (1987), pp. 116–118.

  34. C. G. Jockusch Jr., M. Lerman, R. I. Soare, and R. M. Solovay, “Recursively enumerable sets modulo iterated jumps and extensions of Arslanov’s completeness criterion,” J. Symb. Logic, 54, 1288–1323 (1989).

    Article  MathSciNet  MATH  Google Scholar 

  35. C. G. Jockusch Jr. and R. Shore, “Pseudo jump operators, 1. The recursively enumerable case,” Trans. Am. Math. Soc., 275, No. 2, 599–609 (1983).

    MATH  Google Scholar 

  36. C. G. Jockusch Jr. and R. Shore, “Pseudo jump operators, 2. Transfinite iterations, hierarchies, and minimal covers,” J. Symb. Logic, 49, 1205–1236 (1984).

    Article  MATH  Google Scholar 

  37. S. Kallibekov, “On index sets of m-degrees,” Sib. Mat. Zh., 12, 1292–1300 (1971).

    MathSciNet  Google Scholar 

  38. S. Kallibekov, “On tt-degrees of recursively enumerable sets,” Mat. Zametki, 14, No. 5, 421–426 (1973).

    MathSciNet  MATH  Google Scholar 

  39. A. Kanda and A. Lachlan, “Alternative characterizations of precomplete numberings,” Z. Math. Logik, 33, 97–100 (1987).

    Article  MATH  Google Scholar 

  40. T. Kihara and A. Montalban, The uniform Martin’s conjecture for many-one degrees, arxiv 1608.05065v1 [Math.LO] (2016).

  41. A. Kucera, “An alternative, priority-free, solution to Post’s problem,” in: Mathematical Foundations of Computer Science, Proc. 12th Symp. Bratislava/Czech. 1986, Lect. Notes Comput. Sci., 233 (1986), pp. 493–500.

  42. K. Kuratowski and A. Mostowski, Set Theory, North-Holland, Amsterdam (1967).

    MATH  Google Scholar 

  43. T. M. Kuzmina, “Structure of m-degrees of index sets of families of partial recursive functions,” Algebra Logika, 20, 55–68 (1981).

    MathSciNet  Google Scholar 

  44. T. M. Kuzmina, “On weak semilattices and m-degrees of index sets,” Algebra Logika, 28, 555–569 (1989).

    Google Scholar 

  45. A. H. Lachlan, “A note on positive equivalence relations,” Z. Math. Logik, 33, 43–46 (1987).

    Article  MathSciNet  MATH  Google Scholar 

  46. A. I. Malcev, “Constructive algebras, I,” Usp. Mat. Nauk, 16, No. 3, 3–60 (1961).

    MathSciNet  Google Scholar 

  47. A. I. Malcev, “Completely numbered sets,” Algebra Logika, 2, 4–29 (1963).

    Google Scholar 

  48. A. I. Malcev, Algorithms and Recursive Functions, Wolters-Noordhoff, Groningen (1970).

    Google Scholar 

  49. A. I. Malcev, Algebraic Systems, Springer, Berlin, (1973).

    Book  MATH  Google Scholar 

  50. J. Mohrherr, “Kleene index sets and functional m-degrees,” J. Symb. Logic, 48, 829–840 (1983).

    Article  MathSciNet  MATH  Google Scholar 

  51. F. Montagna, “Relatively precomplete numberings and arithmetic,” J. Philos. Logic, 11, 419–430 (1982).

    Article  MathSciNet  MATH  Google Scholar 

  52. F. Montagna and A. Sorbi, “Universal recursion-theoretic properties of c.e. preordered structures,” J. Symb. Logic, 50, 397—406 (1985).

    Article  MathSciNet  MATH  Google Scholar 

  53. Y. N. Moschovakis, Descriptive Set Theory, North-Holland, Amsterdam (2009).

    Book  MATH  Google Scholar 

  54. A. Nerode and R. A. Shore, “Reducibility orderings: theories, definability and automorphisms,” Ann. Math. Logic, 18, 61–89 (1980).

    Article  MathSciNet  MATH  Google Scholar 

  55. H. Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York (1967).

    MATH  Google Scholar 

  56. V. L. Selivanov, “Some remarks on classes of recursively enumerable sets,” Sib. Mat. Zh., 19, 153–161 (1978).

    Article  MATH  Google Scholar 

  57. V. L. Selivanov, “On index sets of computable classes of finite sets,” in: Algorithms and Automata [in Russian], Kazan State Univ., Kazan (1978), pp. 95–99.

  58. V. L. Selivanov, “On the structure of degrees of index sets,” Algebra Logika, 18, 463–480 (1979).

    Article  MathSciNet  MATH  Google Scholar 

  59. V. L. Selivanov, “On the structure of degrees of generalized index sets,” Algebra Logika, 21, 472–491 (1982).

    Article  MathSciNet  Google Scholar 

  60. V. L. Selivanov, “On index sets in the Kleene–Mostowski hierarchy,” Tr. Sobolev Mat. Inst., 2, 135–158 (1982).

    MathSciNet  MATH  Google Scholar 

  61. V. L. Selivanov, “Hierarchies of hyperarithmetical sets and functions,” Algebra Logika, 22, 666–692 (1983).

    Article  MathSciNet  MATH  Google Scholar 

  62. V. L. Selivanov, “Index sets in the hyperarithmetical hierarchy,” Sib. Mat. Zh., 25, 164–181 (1984).

    MathSciNet  MATH  Google Scholar 

  63. V. L. Selivanov, “On a hierarchy of limiting computations,” Sib. Mat. Zh., 25, 146–156 (1984).

    Google Scholar 

  64. V. L. Selivanov, “On Ershov hierarchy,” Sib. Mat. Zh., 26, 134–149 (1985).

    Article  MathSciNet  MATH  Google Scholar 

  65. V. L. Selivanov, “Index sets of factor-objects of the Post numbering,” in: Proc. Int. Conf. on Fundamentals of Computation Theory, Kazan, Lect. Notes Comp. Sci., 278 (1987), pp. 396–400.

  66. V. L. Selivanov, “Index sets of factor-objects of the Post numbering,” Algebra Logika, 27, 343–358 (1988).

    Google Scholar 

  67. V. L. Selivanov, “Ershov hierarchy and Turing jump,” Algebra Logika, 27, 464–478 (1988).

    MathSciNet  Google Scholar 

  68. V. L. Selivanov, “On algorithmic complexity of algebraic systems,” Mat. Zametki, 44, No. 6, 823–832 (1988).

    MathSciNet  MATH  Google Scholar 

  69. V. L. Selivanov, “Applications of precomplete numberings to degrees of tt-type and to index sets,” Algebra Logika, 12, 165–185 (1989).

    Google Scholar 

  70. V. L. Selivanov, “Fine hierarchies of arithmetical sets and definable index sets,” Tr. Sobolev Mat. Inst., 12, 165–185 (1989).

    MATH  Google Scholar 

  71. V. L. Selivanov, Hierarchical classification of arithmetical sets and index sets [in Russian], Doctoral dissertation, Sobolev Inst. Math., Novosibirsk (1989).

    Google Scholar 

  72. V. L. Selivanov, “Fine hierarchies and definable index sets,” Algebra Logika, 30, 705–725 (1991).

    Google Scholar 

  73. V. L. Selivanov, “Jumps of some classes of \( {\Delta}_2^0 \)-sets,” Mat. Zametki, 50, No. 6, 122–125 (1991).

    Google Scholar 

  74. V. L. Selivanov, “Universal Boolean algebras with applications,” in: Proc. Int. Conf. in Honor of A. I. Shishov [in Russian], Novosibirsk (1991), pp. 127.

  75. V. L. Selivanov, “Precomplete numberings and functions without fixed points,” Mat. Zametki, 51, No. 1, 175–181 (1992).

    MATH  Google Scholar 

  76. V. L. Selivanov, Hierarchies, Numerations, and Index Sets, Handwritten Lect. Notes (1992).

    Google Scholar 

  77. V. L. Selivanov, Precomplete numerations with applications, Univ. Heidelberg (1994).

    Google Scholar 

  78. V. L. Selivanov, “Fine hierarchies and Boolean terms,” J. Symb. Logic, 60, 289–317 (1995).

    Article  MathSciNet  MATH  Google Scholar 

  79. V. L. Selivanov, “Fine hierarchy and definability in the Lindenbaum algebra,” in: Logic: From Foundations to Applications, Clarendon Press, Oxford (1996), pp. 425–452.

  80. V. L. Selivanov, “On recursively enumerable structures,” Ann. Pure Appl. Logic, 78, 243–258 (1996).

    Article  MathSciNet  MATH  Google Scholar 

  81. V. L. Selivanov, “Precomplete numberings,” in: Proc. Int. Conf. “Logic and Applications” dedicated to Yu. L. Ershov and A. I. Maltsev, Sobolev Inst. Math., Novosibirsk (2002), pp. 104–143.

  82. V. L. Selivanov, “Fine hierarchies and m-reducibilities in theoretical computer science,” Theor. Comp. Sci., 405, 116–163 (2008).

    Article  MathSciNet  MATH  Google Scholar 

  83. V. L. Selivanov, “Total representations,” Logic. Meth. Comp. Sci., 9, No. 2, 1–30 (2013).

    MathSciNet  MATH  Google Scholar 

  84. V. L. Selivanov, “Towards the effective descriptive set theory,” in: Evolving Computability, Lect. Notes Comp. Sci., 9136 (A. Beckmann, V. Mitrana, and M. Soskova, eds.), Springer-Verlag (2015), pp. 324–333.

  85. V. L. Selivanov and M. M. Yamaleev, “On the Turing degrees in refinements of the arithmetical hierarchy,” Algebra Logika, 57, No. 3, 338–361 (2018).

  86. V. L. Selivanov and M. M. Yamaleev, “Extending Cooper’s theorem to \( {\Delta}_3^0 \) Turing degrees,” Computability, 7, No. 2-3, 289–300 (2018).

  87. V. L. Selivanov and M. M. Yamaleev, “Extending Cooper’s theorem to \( {\Delta}_3^0 \) Turing degrees,” Computability, 7, No. 2-3, 289–300 (2018).

  88. V. Yu. Shavrukov, Remarks on uniformly finitely precomplete positive equivalences, ML-93-12, ILLC Prepublication Series for Math. Logic and Foundations, Univ. Amsterdam (1993).

    Google Scholar 

  89. R. I. Soare, Recursively Enumerable Sets and Degrees, Springer, Berlin (1987).

    Book  MATH  Google Scholar 

  90. D. Spreen, “Can partial indexings be totalized?,” J. Symb. Logic, 6, 1157–1185 (2001).

    Article  MathSciNet  MATH  Google Scholar 

  91. Spreen D., “Partial numberings and precompeteness,” in: Logic, Computation, Hierarchies (V. Brattka et al., eds.), De Gruyter, Berlin–Boston (2014), pp. 325–340.

  92. D. Spreen, “An isomorphism theorem for partial numberings,” in: Logic, Computation, Hierarchies (V. Brattka et al., eds.), De Gruyter, Berlin–Boston (2014), pp. 341–481.

  93. V. A. Uspensky, “Kolmogorov and mathematical logic,” J. Symb. Logic, 57, No. 2, 385–412 (1992).

    Article  MathSciNet  MATH  Google Scholar 

  94. A. Visser, “Numberings, λ-calculus and arithmetic,” in: To H. B. Curry: Essays on Combinatory Logic, λ-Calculus and Formalism (J. P. Seldin and J. R. Hindley, eds.), Academic Press, New York (1980), pp. 259–284.

  95. K. Weihrauch, Computability, Springer, Berlin (1987).

    Book  MATH  Google Scholar 

  96. K. Weihrauch, Computable Analysis, Springer, Berlin (2000).

    Book  MATH  Google Scholar 

  97. L. V. Welch, “A hierarchy of families of recursively enumerable degrees,” J. Symb. Logic, 49, 1160–1170 (1984).

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia

    V. L. Selivanov

  2. Kazan (Volga Region) Federal University, Kazan, Russia

    V. L. Selivanov

Authors
  1. V. L. Selivanov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. L. Selivanov.

Additional information

Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory, Vol. 157, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, 2018.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Selivanov, V.L. Precomplete Numberings. J Math Sci 256, 96–124 (2021). https://doi.org/10.1007/s10958-021-05422-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10958-021-05422-2

Keywords and phrases:

AMS Subject Classification

Search

Navigation