Minimal covers and hyperdegrees

Simpson, Stephen G.

doi:10.1090/S0002-9947-1975-0392534-3

Minimal covers and hyperdegrees
HTML articles powered by AMS MathViewer

by Stephen G. Simpson

Trans. Amer. Math. Soc. 209 (1975), 45-64

DOI: https://doi.org/10.1090/S0002-9947-1975-0392534-3

PDF | Request permission

Abstract:

Every hyperdegree at or above that of Kleene’s $O$ is the hyperjump and the supremum of two minimal hyperdegrees (Theorem 3.1). There is a nonempty $\Sigma _1^1$ class of number-theoretic predicates each of which has minimal hyperdegree (Theorem 4.7). If $V = L$ or a generic extension of $L$, then there are arbitrarily large hyperdegrees which are not minimal over any hyperdegree (Theorems 5.1, 5.2). If ${O^\# }$ exists, then there is a hyperdegree such that every larger hyperdegree is minimal over some hyperdegree (Theorem 5.4). Several other theorems on hyperdegrees and degrees of nonconstructibility are presented.

References

K. J. Barwise, R. O. Gandy, and Y. N. Moschovakis, The next admissible set, J. Symbolic Logic 36 (1971), 108–120. MR 300876, DOI 10.2307/2271519
George Boolos and Hilary Putnam, Degrees of unsolvability of constructible sets of integers, J. Symbolic Logic 33 (1968), 497–513. MR 239977, DOI 10.2307/2271357
S. B. Cooper, Degrees of unsolvability complementary between recursively enumerable degrees. I, Ann. Math. Logic 4 (1972), 31–73. MR 294126, DOI 10.1016/0003-4843(72)90011-3
S. B. Cooper, Minimal degrees and the jump operator, J. Symbolic Logic 38 (1973), 249–271. MR 347572, DOI 10.2307/2272061

A minimal degree below

0

not realizing least possible jump

Harvey M. Friedman, Borel sets and hyperdegrees, J. Symbolic Logic 38 (1973), 405–409. MR 335248, DOI 10.2307/2273034
Harvey M. Friedman, Determinateness in the low projective hierarchy, Fund. Math. 72 (1971), no. 1, 79–95. (errata insert). MR 299470, DOI 10.4064/fm-72-1-79-95

degree determinateness fails in all Boolean extensions

R. O. Gandy and G. E. Sacks, A minimal hyperdegree, Fund. Math. 61 (1967), 215–223. MR 225653, DOI 10.4064/fm-61-2-215-223
Joseph Harrison, Recursive pseudo-well-orderings, Trans. Amer. Math. Soc. 131 (1968), 526–543. MR 244049, DOI 10.1090/S0002-9947-1968-0244049-7
Ronald Jensen, Definable sets of minimal degree, Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968) North-Holland, Amsterdam, 1970, pp. 122–128. MR 0306002
Carl G. Jockusch Jr., An application of $\sum ^{0}_{4}$ determinacy to the degrees of unsolvability, J. Symbolic Logic 38 (1973), 293–294. MR 332459, DOI 10.2307/2272064
Carl G. Jockusch Jr. and Robert I. Soare, Degrees of members of $\Pi ^{0}_{1}$ classes, Pacific J. Math. 40 (1972), 605–616. MR 309722, DOI 10.2140/pjm.1972.40.605
Carl G. Jockusch Jr. and Robert I. Soare, A minimal pair of $\Pi _{1}{}^{0}$ classes, J. Symbolic Logic 36 (1971), 66–78. MR 282834, DOI 10.2307/2271516
Carl G. Jockusch Jr. and Robert I. Soare, Minimal covers and arithmetical sets, Proc. Amer. Math. Soc. 25 (1970), 856–859. MR 265154, DOI 10.1090/S0002-9939-1970-0265154-X
Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
Alexander S. Kechris, The theory of countable analytical sets, Trans. Amer. Math. Soc. 202 (1975), 259–297. MR 419235, DOI 10.1090/S0002-9947-1975-0419235-7
S. C. Kleene, Quantification of number-theoretic functions, Compositio Math. 14 (1959), 23–40. MR 103822
G. Kreisel and Gerald E. Sacks, Metarecursive sets, J. Symbolic Logic 30 (1965), 318–338. MR 213233, DOI 10.2307/2269621
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 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 10.4064/fm-66-3-287-291
D. A. Martin and R. M. Solovay, A basis theorem for $\sum _3^1$ sets of reals, Ann. of Math. (2) 89 (1969), 138–159. MR 255391, DOI 10.2307/1970813
J. B. Paris, $\textrm {ZF}\vdash \sum _{4}^{0}$ determinateness, J. Symbolic Logic 37 (1972), 661–667. MR 363904, DOI 10.2307/2272410
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto-London, 1967. MR 0224462
Gerald E. Sacks, Countable admissible ordinals and hyperdegrees, Advances in Math. 20 (1976), no. 2, 213–262. MR 429523, DOI 10.1016/0001-8708(76)90187-0
Gerald E. Sacks, Forcing with perfect closed sets, Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1971, pp. 331–355. MR 0276079
Gerald E. Sacks, Measure-theoretic uniformity in recursion theory and set theory, Trans. Amer. Math. Soc. 142 (1969), 381–420. MR 253895, DOI 10.1090/S0002-9947-1969-0253895-6
Leonard P. Sasso Jr., A minimal degree not realizing least possible jump, J. Symbolic Logic 39 (1974), 571–574. MR 360242, DOI 10.2307/2272899
Joseph R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR 0225631
J. R. Shoenfield, Unramified forcing, Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1971, pp. 357–381. MR 0280359

Some results on hyperdegrees

18

A remark on the elementary theory of the hyperdegrees

18

Robert M. Solovay, A nonconstructible $\Delta _3^1$ set of integers, Trans. Amer. Math. Soc. 127 (1967), 50–75. MR 211873, DOI 10.1090/S0002-9947-1967-0211873-5
Clifford Spector, Recursive well-orderings, J. Symbolic Logic 20 (1955), 151–163. MR 74347, DOI 10.2307/2266902
Clifford Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581–592. MR 82457, DOI 10.2307/1969604
S. K. Thomason, The forcing method and the upper semilattice of hyperdegrees, Trans. Amer. Math. Soc. 129 (1967), 38–57. MR 219421, DOI 10.1090/S0002-9947-1967-0219421-0
S. K. Thomason, On initial segments of hyperdegrees, J. Symbolic Logic 35 (1970), 189–197. MR 288027, DOI 10.2307/2270508
Harvey Friedman, Bar induction and $\Pi _{1}{}^{1}-\textrm {CA}$, J. Symbolic Logic 34 (1969), 353–362. MR 250877, DOI 10.2307/2270902
Leo A. Harrington and Alexander S. Kechris, A basis result for $\Sigma ^{0}_{3}$ sets of reals with an application to minimal covers, Proc. Amer. Math. Soc. 53 (1975), no. 2, 445–448. MR 398832, DOI 10.1090/S0002-9939-1975-0398832-7

singletons and

G. E. Sacks and S. G. Simpson, The $\alpha$-finite injury method, Ann. Math. Logic 4 (1972), 343–367. MR 369041, DOI 10.1016/0003-4843(72)90004-6
Stephen G. Simpson, Degree theory on admissible ordinals, Generalized recursion theory (Proc. Sympos., Univ. Oslo, Oslo, 1972) Studies in Logic and the Foundations of Math., Vol. 79, North-Holland, Amsterdam, 1974, pp. 165–193. MR 0537203
C. E. M. Yates, Prioric games and minimal degrees below ${\bf 0}^{(1)}$, Fund. Math. 82 (1974/75), 217–237. MR 406784, DOI 10.4064/fm-82-3-217-237