The members of thin and minimal \(\Pi_1^0\) classes, their ranks and Turing degrees. (English) Zbl 1353.03042
Summary: We study the relationship among members of \(\Pi_1^0\) classes, thin \(\Pi_1^0\) classes, their Cantor-Bendixson ranks and their Turing degrees; in particular, we show that any nonzero \(\Delta_2^0\) degree contains a member of rank \(\alpha\) for any computable ordinal \(\alpha\). Furthermore we observe that the degrees containing members of thin \(\Pi_1^0\) classes are not closed under join.
MSC:
| 03D25 | Recursively (computably) enumerable sets and degrees |
| 03D28 | Other Turing degree structures |
| 03D30 | Other degrees and reducibilities in computability and recursion theory |
| 03D60 | Computability and recursion theory on ordinals, admissible sets, etc. |
Keywords:
computably enumerable degrees; \(\Pi_1^0\) classes; thin \(\Pi_1^0\) classes; Cantor-Bendixson ranksReferences:
| [1] | Cenzer, D.; Remmel, J. B., \( \Pi_1^0\)-classes in mathematics, (Handbook of Recursive Mathematics, vol. 2. Handbook of Recursive Mathematics, vol. 2, Stud. Logic Found. Math., vol. 139 (1998), North-Holland: North-Holland Amsterdam), 623-821 · Zbl 0941.03044 |
| [2] | Cenzer, D.; Smith, R. L., On the ranked points of a \(\Pi_1^0\) set, J. Symbolic Logic, 54, 3, 975-991 (1989) · Zbl 0689.03022 |
| [3] | Cenzer, D.; Clote, P.; Smith, R. L.; Soare, R. I.; Wainer, S. S., Members of countable \(\Pi_1^0\)-classes, Ann. Pure Appl. Logic, 31, 2-3, 145-163 (1986), Special issue: Second Southeast Asian Logic Conference (Bangkok, 1984) · Zbl 0605.03020 |
| [4] | Cenzer, D.; Downey, R. G.; Jockusch, C.; Shore, R. A., Countable thin \(\Pi_1^0\)-classes, Ann. Pure Appl. Logic, 59, 2, 79-139 (1993) · Zbl 0909.03039 |
| [5] | Cholak, P.; Downey, R. G., On the Cantor-Bendixson rank of recursively enumerable sets, J. Symbolic Logic, 58, 2, 629-640 (1993) · Zbl 0782.03021 |
| [6] | Cholak, P.; Coles, R.; Downey, R. G.; Herrmann, E., Automorphisms of the lattice of \(\Pi_1^0\)-classes: perfect thin classes and anc degrees, Trans. Amer. Math. Soc., 353, 12, 4899-4924 (2001) · Zbl 0978.03033 |
| [7] | Downey, R. G., On \(\Pi_1^0\)-classes and their ranked points, Notre Dame J. Form. Log., 32, 4, 499-512 (1992), 1991 · Zbl 0753.03016 |
| [9] | Jockusch, C. G., Relationships between reducibilities, Trans. Amer. Math. Soc., 142, 229-237 (1969) · Zbl 0188.02604 |
| [10] | Jockusch, C. G.; Soare, R. I., \( \Pi_1^0\)-classes and degrees of theories, Trans. Amer. Math. Soc., 173, 33-56 (1972) · Zbl 0262.02041 |
| [11] | Martin, D. A.; Pour-El, M. B., Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic, 35, 205-209 (1970) · Zbl 0209.01204 |
| [12] | Metakides, G.; Nerode, A., Effective content of field theory, Ann. Math. Logic, 17, 289-320 (1979) · Zbl 0469.03028 |
| [13] | Sacks, G., On the degrees less than \(0^\prime \), Ann. of Math., 77, 211-231 (1963) · Zbl 0118.25104 |
| [14] | Sacks, G., Higher Recursion Theory, Perspect. Math. Log. (1990), Springer-Verlag: Springer-Verlag Heidelberg · Zbl 0716.03043 |
| [15] | Solomon, R., Thin classes of separating sets, (Advances in Logic. Advances in Logic, Contemp. Math., vol. 425 (2007), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 67-86 · Zbl 1123.03037 |
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.
