×

zbMATH — the first resource for mathematics

Effectively closed sets and enumerations. (English) Zbl 1140.03026
Summary: An effectively closed set, or \({\Pi^{0}_{1}}\) class, may be viewed as the set of infinite paths through a computable tree. A numbering, or enumeration, is a map from \(\omega\) onto a countable collection of objects. One numbering is reducible to another if equality holds after the second is composed with a computable function. Many commonly used numberings of \({\Pi^{0}_{1}}\) classes are shown to be mutually reducible via a computable permutation. Computable injective numberings are given for the family of \({\Pi^{0}_{1}}\) classes and for the subclasses of decidable and of homogeneous \({\Pi^{0}_{1}}\) classes. However, no computable numberings exist for small or thin classes. No computable numbering of trees exists that includes all computable trees without dead ends.

MSC:
03D45 Theory of numerations, effectively presented structures
03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Binns, S.: Small \({\Pi^{0}_{1}}\) classes. Arch. Math. Logic 45(4), 393–410 (2006) · Zbl 1147.03024 · doi:10.1007/s00153-005-0319-6
[2] Brodhead, P.: Enumerations of \({\Pi^{0}_{1}}\) classes: acceptability and decidable classes. In: Proceedings of CCA 2006, Gainesville, Elect. Notes in Th. Comp. Sci., Elsevier, Amsterdam (2006) (to appear, electronic) · Zbl 1262.03072
[3] Brodhead, P.: Computable aspects of closed sets. Ph.D. Dissertation, University of Florida (2008) · Zbl 1140.03026
[4] Cholak, P., Coles, R., Downey, R., Hermann, E.: Automorphisms of the lattice of \({\Pi^{0}_{1}}\) classes: perfect thin classes and anc degrees. Trans. Am. Math. Soc. 353, 4899–4924 (2001) (electronic) · Zbl 0978.03033 · doi:10.1090/S0002-9947-01-02821-5
[5] Cenzer, D., Downey, R., Jockusch, C., Shore, R.: Countable thin \({\Pi^{0}_{1}}\) classes. Ann. Pure App. Logic 59, 79–139 (1993) · Zbl 0909.03039 · doi:10.1016/0168-0072(93)90001-T
[6] Cenzer, D.: \({\Pi^{0}_{1}}\) classes in computability theory. In: Griffor, E.R.(eds) Handbook of Computability Theory, pp. 37–85. Elsevier, Amsterdam (1999) · Zbl 0939.03047
[7] Cenzer, D., Remmel, J.B.: Effectively Closed Sets, ASL Lecture Notes in Logic (to appear) · Zbl 1039.03033
[8] Cenzer, D., Remmel, J.: Index sets for \({\Pi^{0}_{1}}\) classes. Ann. Pure App. Logic 93, 3–61 (1998) · Zbl 0926.03042 · doi:10.1016/S0168-0072(97)00052-3
[9] Cenzer, D., Remmel, J.: \({\Pi^{0}_{1}}\) classes in mathematics. In: Ershov, Y., Goncharov, S., Nerode, A., Remmel, J.(eds) Handbook of Recursive Mathematics, pp. 623–821. North-Holland, Amsterdam (1999) · Zbl 0941.03044
[10] Cenzer, D., Remmel, J.: Index sets for computable real functions. In: Proceedings of CCA 2003, Cincinnati, pp. 163–182 (2003)
[11] Downey, R., Jockusch, C., Stob, M.: Array nonrecursive sets of multiple permitting arguments. In: Ambos-Spies, K., Muller, G., Sacks, G.(eds) Recursion Theory Week: Proc. Ober. 1989, pp. 141–173. Springer, Heidelberg (1990) · Zbl 0713.03020
[12] Downey, R.: Maximal theories. Ann. Pure App. Logic 33, 245–282 (1987) · Zbl 0629.03019 · doi:10.1016/0168-0072(87)90083-2
[13] Ershov, Y.: Theory of numberings. In: Griffor, E.R.(eds) Handbook of Computability Theory, pp. 473–503. North-Holland, Amsterdam (1999) · Zbl 0948.03040
[14] Friedberg, R.: Three theorems on recursive enumeration. J. Symb. Logic 23, 309–316 (1958) · Zbl 0088.01601 · doi:10.2307/2964290
[15] Goncharov, S., Lempp, S., Solomon, R.: Friedburg numberings of families of n-computably enumerable sets. Algebra Logic 41, 81–86 (2002) · Zbl 1063.03028 · doi:10.1023/A:1015352513117
[16] Hinman, P.: Recursion-Theoretic Hierarchies. Springer, Heidelberg (1978) · Zbl 0371.02017
[17] Jockusch, C., Soare, R.: \({\Pi^{0}_{1}}\) classes and degrees of theories. Trans. Am. Math. Soc. 173, 35–56 (1972) · Zbl 0262.02041
[18] Lempp, S.: Hyperarithmetical index sets in recursion theory. Trans. Am. Math. Soc. 303, 559–583 (1987) · Zbl 0652.03030 · doi:10.1090/S0002-9947-1987-0902785-2
[19] Pour-El, M., Putnam, H.: Recursively enumerable classes and their application to recursive sequences of formal theories. Archiv Math. Logik Grund 8, 104–121 (1965) · Zbl 0242.02046 · doi:10.1007/BF01976264
[20] Raichev, A.: Relative Randomness via RK-Reducibility, Ph.D. Thesis, University of Wisconsin, Madison (2006)
[21] Rogers, H.: Gödel numberings of partial recursive functions. J. Symb. Logic 23, 331–341 (1958) · Zbl 0088.01602 · doi:10.2307/2964292
[22] Rogers, H.: Theory of recursive functions and effective computability. McGraw-Hill, New York (1967) · Zbl 0183.01401
[23] Simpson, S.: Mass problems and randomness. Bull. Symb. Logic 11(1), 1–27 (2005) · Zbl 1090.03015 · doi:10.2178/bsl/1107959497
[24] Soare, R.: Recursively Enumerable Sets and Degrees. Springer, Heidelberg (1987) · Zbl 0667.03030
[25] Solomon, R.: Thin classes of separating sets. Contemporary mathematics 425, pp 67–86. American Mathematical Society (2007) · Zbl 1123.03037
[26] Suzuki, Y.: Enumerations of recursive sets. J. Symb. Logic 24, 311 (1959) · Zbl 0096.24503 · doi:10.2307/2963902
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.