Minimal covers and arithmetical sets
Authors:
Carl G. Jockusch and Robert I. Soare
Journal:
Proc. Amer. Math. Soc. 25 (1970), 856-859
MSC:
Primary 02.70
DOI:
https://doi.org/10.1090/S0002-9939-1970-0265154-X
MathSciNet review:
0265154
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: If $a$ and $b$ are degrees of unsolvability, $a$ is called a minimal cover of $b$ if $b < a$ and no degree $c$ satisfies $b < c < a$. The degree $a$ is called a minimal cover if it is a minimal cover of some degree $b$. We prove by a very simple argument that ${0^n}$ is not a minimal cover for any $n$. From this result and the axiom of Borel determinateness (BD) we show that the degrees of arithmetical sets (with their usual ordering) are not elementarily equivalent to all the degrees. We also point out how this latter result can be proved without BD when the jump operation is added to the structures involved.
- Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. MR 98025, DOI https://doi.org/10.2307/2964177
- S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, DOI https://doi.org/10.2307/1969708
- Donald A. Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc. 74 (1968), 687–689. MR 227022, DOI https://doi.org/10.1090/S0002-9904-1968-11995-0
- Donald A. Martin, Measurable cardinals and analytic games, Fund. Math. 66 (1969/70), 287–291. MR 258637, DOI https://doi.org/10.4064/fm-66-3-287-291
- Jan Mycielski, On the axiom of determinateness, Fund. Math. 53 (1963/64), 205–224. MR 161787, DOI https://doi.org/10.4064/fm-53-2-205-224
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- Clifford Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581–592. MR 82457, DOI https://doi.org/10.2307/1969604
Retrieve articles in Proceedings of the American Mathematical Society with MSC: 02.70
Retrieve articles in all journals with MSC: 02.70
Additional Information
Keywords:
Recursive function,
degree of unsolvability,
arithmetical hierarchy,
axiom of determinateness
Article copyright:
© Copyright 1970
American Mathematical Society