Minimal generalized computable numberings and families of positive preorders. (English. Russian original) Zbl 1515.03193
Algebra Logic 61, No. 3, 188-206 (2022); translation from Algebra Logika 61, No. 3, 280-307 (2022).
Summary: We study \(A\)-computable numberings for various natural classes of sets. For an arbitrary oracle \(A\geq_T\boldsymbol{0}'\), an example of an \(A\)-computable family \(S\) is constructed in which each \(A\)-computable numbering of \(S\) has a minimal cover, and at the same time, \(S\) does not satisfy the sufficient conditions for the existence of minimal covers specified in [S. A. Badaev and S. Yu. Podzorov, Sib. Mat. Zh. 43, No. 4, 769–778 (2002; Zbl 1008.03026); translation in Sib. Math. J. 43, No. 4, 616–622 (2002)]. It is proved that the family of all positive linear preorders has an \(A\)-computable numbering iff \(A' \geq_T\boldsymbol{0}"\). We obtain a series of results on minimal \(A\)-computable numberings, in particular, Friedberg numberings and positive undecidable numberings.
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
Keywords:
\(A\)-computable numbering; positive linear preorder; Rogers semilattice; Friedberg numbering; positive numbering; minimal coverCitations:
Zbl 1008.03026References:
| [1] | Goncharov, SS; Sorbi, A., Generalized computable numerations and nontrivial Rogers semilattices, Algebra and Logic, 36, 6, 359-369 (1997) · Zbl 0969.03052 · doi:10.1007/BF02671553 |
| [2] | Badaev, SA; Goncharov, SS, Rogers semilattices of families of arithmetic sets, Algebra and Logic, 40, 5, 283-291 (2001) · Zbl 0989.03040 · doi:10.1023/A:1012516217265 |
| [3] | S. A. Badaev and S. Yu. Podzorov, “Minimal coverings in the Rogers semilattices of \({\Sigma}_n^0 \)- computable numberings,” Sib. Math. J., 43, No. 4, 616-622 (2002). · Zbl 1008.03026 |
| [4] | S. Yu. Podzorov, “Initial segments in Rogers semilattices of \({\Sigma}_n^0 \)-computable numberings,” Algebra and Logic, 42, No. 2, 121-129 (2003). · Zbl 1029.03033 |
| [5] | Podzorov, SY, The limit property of the greatest element in the Rogers semilattice, Math. Trudy, 7, 2, 98-108 (2004) · Zbl 1095.03027 |
| [6] | S. Yu. Podzorov, “Local structure of Rogers semilattices of \({\Sigma}_n^0 \)-computable numberings,” Algebra and Logic, 44, No. 2, 82-94 (2005). · Zbl 1104.03038 |
| [7] | Badaev, SA; Goncharov, SS; Sorbi, A., Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy, Algebra and Logic, 45, 6, 361-370 (2006) · Zbl 1164.03340 · doi:10.1007/s10469-006-0034-3 |
| [8] | Podzorov, SY, Arithmetical D-degrees, Sib. Math. J., 49, 6, 1109-1123 (2008) · Zbl 1224.03021 · doi:10.1007/s11202-008-0107-8 |
| [9] | Badaev, SA; Goncharov, SS, Generalized computable universal numberings, Algebra and Logic, 53, 5, 355-364 (2014) · Zbl 1318.03050 · doi:10.1007/s10469-014-9296-3 |
| [10] | Issakhov, A., Ideals without minimal elements in Rogers semilattices, Algebra and Logic, 54, 3, 197-203 (2015) · Zbl 1393.03024 · doi:10.1007/s10469-015-9340-y |
| [11] | Faizrakhmanov, MK, Universal generalized computable numberings and hyperimmunity, Algebra and Logic, 56, 4, 337-347 (2017) · Zbl 1420.03092 · doi:10.1007/s10469-017-9454-5 |
| [12] | Faizrakhmanov, MK, The Rogers semilattices of generalized computable enumerations, Sib. Math. J., 58, 6, 1104-1110 (2017) · Zbl 1420.03094 · doi:10.1134/S0037446617060192 |
| [13] | Ershov, YL, Theory of Numerations (1977), Moscow: Nauka, Moscow |
| [14] | Yu. L. Ershov, “Theory of numberings,” in Handbook of Computability Theory, Stud. Log. Found. Math., 140, Elsevier, Amsterdam (1999), pp. 473-503. · Zbl 0948.03040 |
| [15] | S. A. Badaev and S. S. Goncharov, “Theory of numberings: Open problems,” in Computability Theory and Its Applications, Cont. Math., 257, Am. Math. Soc., Providence, RI (2000), pp. 23-38. · Zbl 0961.03038 |
| [16] | S. A. Badaev and S. S. Goncharov, “Computability and numberings,” in New Computational Paradigms. Changing Conceptions of What Is Computable, S. B. Cooper, B. Lowe, and A. Sorbi (eds.), Springer, New York (2008), pp. 19-34. · Zbl 1157.03022 |
| [17] | Kalmurzayev, BS; Bazhenov, NA; Torebekova, MA, Index sets for classes of positive preorders, Algebra and Logic, 61, 1, 30-53 (2022) · Zbl 1515.03186 · doi:10.1007/s10469-022-09673-z |
| [18] | R. I. Soare, Recursively Enumerable Sets and Degrees, Persp. Math. Log., Omega Ser., Springer, Berlin (1987). · Zbl 0623.03042 |
| [19] | Miller, W.; Martin, DA, The degrees of hyperimmune sets, Z. Math. Log. Grundl. Math., 14, 159-166 (1968) · Zbl 0216.29102 · doi:10.1002/malq.19680140704 |
| [20] | Badaev, SA, On weakly pre-complete positive equivalences, Sib. Math. J., 32, 2, 321-323 (1991) · Zbl 0733.03034 · doi:10.1007/BF00972779 |
| [21] | Badaev, S.; Sorbi, A., Weakly precomplete computably enumerable equivalence relations, Math. Log. Q., 62, 1-2, 111-127 (2016) · Zbl 1361.03043 · doi:10.1002/malq.201500057 |
| [22] | Issakhov, AA; Rakymzhankyzy, F.; Ostemirova, U., Infinite families of total functions with principal numberings, Herald Kazakh-British Tech. Univ., 18, 2, 53-58 (2021) · doi:10.55452/1998-6688-2021-18-2-53-58 |
| [23] | Issakhov, AA; Rakymzhankyzy, F., Friedberg numberings with a hyperimmune oracle, Herald Kazakh-British Tech. Univ., 16, 1, 68-72 (2019) |
| [24] | Jockusch, CG Jr, Degrees in which the recursive sets are uniformly recursive, Can. J. Math., 24, 6, 1092-1099 (1972) · Zbl 0221.02029 · doi:10.4153/CJM-1972-113-9 |
| [25] | Bazhenov, NA; Kalmurzaev, BS, Rogers semilattices for families of equivalence relations in the Ershov hierarchy, Sib. Math. J., 60, 2, 223-234 (2019) · Zbl 1445.03050 · doi:10.1134/S0037446619020046 |
| [26] | Khutoretsky, AB, Two existence theorems for computable numerations, Algebra and Logic, 8, 4, 277-282 (1969) · Zbl 0298.02034 · doi:10.1007/BF02306734 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
