Precomplete numberings

V. L. Selivanov

Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Tome 157 (2018), pp. 106-134.

Résumé

In this survey, we discuss the theory of precomplete numberings which appear frequently in computability theory. Precomplete numberings are closely related to some variants of fixed point theorem having an important methodological value. This sometimes permits to eliminate cumbersome proofs involving the so called priority method in favour of 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.

Détail

Keywords: numbering, precomplete numbering, complete numbering, universality, reducibility, hierarchy, index set.

Bibliographie

[1] Arslanov M. M., “Nekotorye obobscheniya teoremy o nepodvizhnoi tochke”, Izv. vuzov. Mat., 228:5 (1981), 9–16 | Zbl

[2] Arslanov M. M., “Ob odnoi ierarkhii stepenei nerazreshimosti”, Veroyatnostnye metody i kibernetika, v. 18, Kazan. gos. un-t, Kazan, 1982, 10–17

[3] Arslanov M. M., Rekursivno perechislimye mnozhestva i stepeni, Kazan. gos. un-t, Kazan, 1986

[4] Arslanov M. M., “Polnota v arifmeticheskoi ierarkhii i nepodvizhnye tochki”, Algebra i logika, 28 (1989), 3–18

[5] Arslanov M. M., Nadyrov R. F. Solovev V. D., “Kriterii polnoty rekursivno perechislimykh mnozhestv i nekotorye obobscheniya teoremy o nepodvizhnoi tochke”, Izv. vuzov. Mat., 179:4 (1977), 3–7

[6] Arslanov M. M., Solovev V. D., “Effektivizatsii opredelenii klassov prostykh mnozhestv”, Algoritmy i avtomaty, Kazan. gos. un-t, Kazan, 1978, 100–108 | Zbl

[7] Akhtyamov R. B., “Indeksnye mnozhestva v ierarkhii Ershova”, Veroyatnostnye metody i kibernetika, v. 24, Kazan. gos. un-t, Kazan, 1990, 3–15

[8] Denisov S. D., “Ob $m$-stepenyakh rekursivno perechislimykh mnozhestv”, Algebra i logika, 9 (1970), 422–427

[9] Dvornikov S. G., “Predpolno numerovannye mnozhestva”, Sib. mat. zh., 20 (1979), 1303—1305 | MR

[10] Dvornikov S. G., “Reshetka stepenei otdelimosti”, Tr. 7 Vses. konf. po mat. logike (Novosibirsk, 1984), 55 | Zbl

[11] Ershov Yu. L., “Ob odnoi ierarkhii mnozhestv, 1”, Algebra i logika, 7:1 (1968), 47–74 2 | MR | Zbl

[12] Ershov Yu. L., “Polno numerovannye mnozhestva”, Sib. mat. zh., 10 (1969), 1048–1064

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

[14] Kallibekov S., “Ob indeksnykh mnozhestvakh $m$-stepenei”, Sib. mat. zh., 12 (1971), 1292–1300 | MR

[15] Kallibekov S., “O $tt$-stepenyakh rekursivno perechislimykh mnozhestv”, Mat. zametki, 14:5 (1973), 421–426 | MR | Zbl

[16] Kuzmina T. M., “Struktura $m$-stepenei indeksnykh mnozhestv semeistv chastichno rekursivnykh funktsii”, Algebra i logika, 20 (1981), 55–68 | Zbl

[17] Kuzmina T. M., “O slabykh polureshetkakh i $m$-stepenyakh indeksnykh mnozhestv”, Algebra i logika, 28 (1989), 555–569 | Zbl

[18] Maltsev A. I., “Konstruktivnye algebry, I”, Usp. mat. nauk, 16:3 (1961), 3–60 | MR | Zbl

[19] Maltsev A. I., “Polno numerovannye mnozhestva”, Algebra i logika, 2 (1963), 4–29 | MR | Zbl

[20] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, M., 1965 | MR

[21] Maltsev A. I., Algebraicheskie sistemy, Nauka, M., 1970 | MR

[22] Selivanov V. L., “Neskolko zamechanii o klassakh rekursivno perechislimykh mnozhestv”, Sib. mat. zh., 19 (1978), 153–161

[23] Selivanov V. L., “Ob indeksnykh mnozhestvakh klassov numeratsii”, Algoritmy i avtomaty, Kazan. gos. un-t, Kazan, 1978, 95–99 | Zbl

[24] Selivanov V. L., “O strukture stepenei indeksnykh mnozhestv”, Algebra i logika, 18 (1979), 463–480 | Zbl

[25] Selivanov V. L., “O strukture stepenei obobschennykh indeksnykh mnozhestv”, Algebra i logika, 21 (1982), 472–491

[26] Selivanov V. L., “Ob indeksnykh mnozhestvakh v ierarkhii Klini—Mostovskogo”, Tr. IM SO AN SSSR, v. 2, Novosibirsk, 1982, 135–158 | Zbl

[27] Selivanov V. L., “Ierarkhii giperarifmeticheskikh mnozhestv i funktsii”, Algebra i logika, 22 (1983), 666–692 | Zbl

[28] Selivanov V. L., “Indeksnye mnozhestva v giperarifmeticheskoi ierarkhii”, Sib. mat. zh., 25 (1984), 164–181 | Zbl

[29] Selivanov V. L., “Ob ierarkhii predelnykh vychislenii”, Sib. mat. zh., 25 (1984), 146–156

[30] Selivanov V. L., “Ob ierarkhii Ershova”, Sib. mat. zh., 26 (1985), 134–149 | MR | Zbl

[31] Selivanov V. L., “Indeksnye mnozhestva faktor-ob'ektov numeratsii Posta”, Algebra i logika, 27 (1988), 343–358 | Zbl

[32] Selivanov V. L., “Ierarkhiya Ershova i T-skachok”, Algebra i logika, 27 (1988), 464–478 | Zbl

[33] Selivanov V. L., “Ob algoritmicheskoi slozhnosti algebraicheskikh sistem”, Mat. zametki, 44:6 (1988), 823–832

[34] Selivanov V. L., “Primeneniya predpolnykh numeratsii k stepenyam tablichnogo tipa i indeksnym mnozhestvam”, Algebra i logika, 12 (1989), 165–185 | Zbl

[35] Selivanov V. L., “Tonkie ierarkhii arifmeticheskikh mnozhestv i indeksnye mnozhestva”, Tr. IM SO AN SSSR, v. 12, Novosibirsk, 1989, 165–185 | Zbl

[36] Selivanov V. L., Ierarkhicheskaya klassifikatsiya arifmeticheskikh mnozhestv i indeksnye mnozhestva, Diss. na soisk. uch. step. dokt. fiz.-mat. nauk, IM SO AN SSSR, Novosibirsk, 1989

[37] Selivanov V. L., “Tonkie ierarkhii i opredelimye indeksnye mnozhestva”, Algebra i logika, 30 (1991), 705–725 | Zbl

[38] Selivanov V. L., “Skachki nekotorykh klassov $\Delta^0_2$-mnozhestv”, Mat. zametki, 50:6 (1991), 122–125

[39] Selivanov V. L., “Universalnye bulevy algebry s primeneniyami”, Tr. Mezhdunar. konf. v chest A. I. Shirshova (Novosibirsk, 1991), S. 127

[40] Selivanov V. L., “Predpolnye numeratsii i funktsii bez nepodvizhnykh tochek”, Mat. zametki, 51:1 (1992), 175–181

[41] Selivanov V. L., Yamaleev M. M., “O tyuringovykh stepenyakh v utoncheniyakh arifmeticheskoi ierarkhii”, Algebra i logika, 57:3 (2018), 338–361 | MR | Zbl

[42] Badaev S., Goncharov S., Sorbi A., “Completeness and universality of arithmetical numberings”, Computability and Models, Perspectives East and West, eds. Cooper S. B., Goncharov S. S., Kluwer Academic, New York; Plenum Publishers, 2003, 11–44 | MR

[43] Badaev S., Goncharov S., Sorbi A., “Algebraic properties of Rogers semilattices of arithmetical numberings”, Computability and Models, Perspectives East and West, eds. Cooper S. B., Goncharov S. S., Kluwer Academic, New York; Plenum Publishers, 2003, 45–78 | MR

[44] Bernardi C., Sorbi A., “Classifying positive equivalence relations”, J. Symb. Logic, 48 (1983), 529–538 | DOI | MR | Zbl

[45] Brandt U., “Index sets in the arithmetical hierarchy”, Ann. Pure Appl. Logic, 37 (1988), 101—110 | DOI | MR | Zbl

[46] Cooper S. B., Degrees of unsolvability, Ph.D. thesis, Leicester University, Leicester, England, 1971 | MR

[47] Epstein R. L., Haas R., Kramer R., “Hierarchies of sets and degrees below $0^\prime$”, Logic Year 1979-80. University of Connecticut, eds. Lerman M., Schmerl J. H., Soare R. I., Springer-Verlag, Berlin, 1981, 32–48 | MR

[48] Ershov Yu. L., “Theorie der Numerierungen 1”, Z. Math. Logik Grundl. Math., 19 (1973), 289–388 | DOI | MR

[49] Ershov Yu. L., “Theorie der Numerierungen 2”, Z. Math. Logik Grundl. Math., 21 (1975), 473–584 | DOI | MR | Zbl

[50] Grassin J., “Index sets in Ershov hierarchy”, J. Symb. Logic, 39:1 (1974), 97–104 | DOI | MR | Zbl

[51] Hay L., “Index sets of finite classes of recursively enumerable sets”, J. Symb. Logic, 34 (1969), 39–44 | DOI | MR | Zbl

[52] Hay L., “A discrete chain of degrees of index sets”, J. Symb. Logic, 37 (1972), 139–149 | DOI | MR | Zbl

[53] Hay L., “Discrete $\omega$-sequences of index sets”, Trans. Am. Math. Soc., 183 (1973), 293–311 | MR | Zbl

[54] Hay L., “Index sets in $0^\prime$”, Algebra i logika, 12 (1973), 713–729 | MR | Zbl

[55] Hay L., “A noninitial segment of index sets”, J. Symb. Logic, 39 (1974), 209–224 | DOI | MR | Zbl

[56] Hay L., “Rice theorems for d.c.e. sets”, Can. J. Math., 27 (1975), 352–365 | DOI | MR | Zbl

[57] Hay L., “Boolean combinations of c.e. sets”, J. Symb. Logic, 41 (1976), 255–278 | DOI | MR

[58] Hay L., Johnson N., “Extensional characterization of index sets”, Z. Math. Logik Grundl. Math., 25 (1979), 227—234 | DOI | MR | Zbl

[59] Jockusch C. G. jr., “Degrees of functions without fixed points”, Abstr. Eighth Congress for LMPS, v. 1, Moscow, 1987, 116–118 | MR

[60] Jockusch C. G. jr., Lerman M., Soare R. I., Solovay R. M., “Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion”, J. Symb. Logic, 54 (1989), 1288–1323 | DOI | MR | Zbl

[61] Jockusch C. G. jr., Shore R., “Pseudo jump operators, 1. The recursively enumerable case”, Trans. Am. Math. Soc., 275:2 (1983), 599–609 | MR | Zbl

[62] Jockusch C. G. jr., Shore R., “Pseudo jump operators, 2. Transfinite iterations, hierarchies and minimal covers”, J. Symb. Logic, 49 (1984), 1205–1236 | DOI | MR | Zbl

[63] Kanda A., Lachlan A., “Alternative characterizations of precomplete numberings”, Z. Math. Logik Grundl. Math., 33 (1987), 97–100 | DOI | MR | Zbl

[64] Kihara T., Montalban A., The uniform Martin's conjecture for many-one degrees, arXiv: 1608.05065 [math.LO] | MR

[65] Kucera A., “An alternative, priority-free, solution to Post's problem”, Mathematical Foundations of Computer Science, Proc. 12th Symp. Bratislava/Czech. 1986, Lect. Notes Comput. Sci., 233, 1986, 493–500 | DOI | MR | Zbl

[66] Kuratowski K., Mostowski A., Set theory, North Holland, Amsterdam, 1967 | MR

[67] Lachlan A. H., “A note on positive equivalence relations”, Z. Math. Logik Grundl. Math., 33 (1987), 43–46 | DOI | MR | Zbl

[68] Mohrherr J., “Kleene index sets and functional $m$-degrees”, J. Symb. Logic, 48 (1983), 829–840 | DOI | MR | Zbl

[69] Montagna F., “Relatively precomplete numberings and arithmetic”, J. Phil. Logic, 11 (1982), 419–430 | DOI | MR | Zbl

[70] Montagna F., Sorbi A., “Universal recursion-theoretic properties of c.e. preordered structures”, J. Symb. Logic, 50 (1985), 397—406 | DOI | MR | Zbl

[71] Moschovakis Y. N., Descriptive set theory, North Holland, Amsterdam, 2009 | MR

[72] Nerode A., Shore R. A., “Reducibility orderings: theories, definability and automorphisms”, Ann. Math. Logic, 18 (1980), 61–89 | DOI | MR | Zbl

[73] Rogers H. jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967 | MR | Zbl

[74] Selivanov V. L., “Index sets of factor-objects of the Post numbering”, Proc. Int. Conf. on Fundamentals of Computation Theory, Kazan, Lect. Notes Comp. Sci., 278, 1987, 396–400 | DOI | Zbl

[75] Selivanov V. L., “Hierarchies, numerations, index sets”, Handwritten lecture notes, 1992

[76] Selivanov V. L., Precomplete numerations with applications, Univ. Heidelberg, 1994

[77] Selivanov V. L., “Fine hierarchies and Boolean terms”, J. Symb. Logic, 60 (1995), 289–317 | DOI | MR | Zbl

[78] Selivanov V. L., “Fine hierarchy and definability in the Lindenbaum algebra”, Logic: from foundations to applications, European logic colloquium, Clarendon Press, Oxford, 1996, 425–452 | MR

[79] Selivanov V. L., “On recursively enumerable structures”, Ann. Pure Appl. Logic, 78 (1996), 243–258 | DOI | MR | Zbl

[80] Selivanov V. L., “Precomplete numberings”, Int. Conf. «Logic and Applications» (dedicated to Yu. L. Ershov and A. I. Maltsev), Sobolev Inst. Math., Novosibirsk, 2002, 104–143 | MR

[81] Selivanov V. L., “Fine hierarchies and $m$-reducibilities in theoretical computer science”, Theor. Comp. Sci., 405 (2008), 116–163 | DOI | MR | Zbl

[82] Selivanov V. L., “Total representations”, Logic. Meth. Comp. Sci., 9:2 (2013), 1–30 | MR

[83] Selivanov V. L., “Towards the effective descriptive set theory”, Evolving computability, CiE 2015, Lect. Notes Comp. Sci., 9136, eds. Beckmann A., Mitrana V., Soskova M., Springer, 2015, 324–333 | DOI | MR | Zbl

[84] Selivanov V. L. and Yamaleev M. M., “Extending Cooper's theorem to $\Delta^0_3$ Turing degrees”, Computability, 7:2-3 (2018), 289–300 | DOI | MR | Zbl

[85] Shavrukov V. Yu., Remarks on uniformly finitely precomplete positive equivalences, Univ. Amsterdam, 1993

[86] Soare R. I., Recursively enumerable sets and degrees, Springer, Berlin, 1987 | MR

[87] Spreen D., “Can partial indexings be totalized?”, J. Symb. Logic, 6 (2001), 1157–1185 | DOI | MR

[88] Spreen D., “Partial numberings and precompeteness”, Logic, Computation, Hierarchies, eds. Brattka V. et al., De Gruyter, Berlin–Boston, 2014, 325–340 | MR | Zbl

[89] Spreen D., “An isomorphism theorem for partial numberings”, Logic, Computation, Hierarchies, eds. Brattka V. et al., De Gruyter, Berlin–Boston, 2014, 341–481 | MR

[90] Uspensky V. A., “Kolmogorov and mathematical logic”, J. Symb. Logic, 57:2 (1992), 385–412 | DOI | MR | Zbl

[91] Visser A., “Numberings, $\lambda$-calculus and arithmetic”, Essays on combinatory logic, $\lambda$-calculus and formalism, eds. Seldin J. P., Hindley J. R. To H. B. Curry, Academic Press, New York, 1980, 259–284 | MR

[92] Weihrauch K., Computability, Springer, Berlin, 1987 | MR | Zbl

[93] Weihrauch K., Computable Analysis, Springer, Berlin, 2000 | MR | Zbl

[94] Welch L. V., “A hierarchy of families of recursively enumerable degrees”, J. Symb. Logic, 49 (1984), 1160–1170 | DOI | MR | Zbl