Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Minimal covers and hyperdegrees


Author: Stephen G. Simpson
Journal: Trans. Amer. Math. Soc. 209 (1975), 45-64
MSC: Primary 02F30
DOI: https://doi.org/10.1090/S0002-9947-1975-0392534-3
MathSciNet review: 0392534
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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^\char93 }$ 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 [Enhancements On Off] (What's this?)

  • [1] K. J. Barwise, R. O. Gandy and Y. N. Moschovakis, The next admissible set, J. Symbolic Logic 36 (1971), 108-120. MR 46 #36. MR 0300876 (46:36)
  • [2] G. Boolos and H. Putnam, Degrees of unsolvability of constructible sets of integers, J. Symbolic Logic 33 (1968), 497-513. MR 39 #1331. MR 0239977 (39:1331)
  • [3] S. B. Cooper, Degrees of unsolvability complementary between recursively enumerable degrees. I, Ann. Math. Logic 4 (1972), 31-73. MR 45 #3199. MR 0294126 (45:3199)
  • [4] -, Minimal degrees and the jump operator, J. Symbolic Logic 38 (1973), 249-271. MR 0347572 (50:75)
  • [5] S. B. Cooper, R. Epstein, L. P. Sasso, A minimal degree below 0' not realizing least possible jump (abstract), Recursive Function Theory Newsletter, No. 6 (July 1973), p. 7.
  • [6] H. Friedman, Borel sets and hyperdegrees, J. Symbolic Logic 38 (1973), 405-409. MR 0335248 (49:30)
  • [7] -, Determinateness in the low projective hierarchy, Fund. Math. 72 (1971), 79-95. MR 45 #8518. MR 0299470 (45:8518)
  • [8] -, $ \Sigma _1^1$ degree determinateness fails in all Boolean extensions, Mimeographed Notes, SUNY at Buffalo, 1973.
  • [9] R. O. Gandy and G. E. Sacks, A minimal hyperdegree, Fund. Math. 61 (1967), 215-223. MR 37 #1246. MR 0225653 (37:1246)
  • [10] J. Harrison, Recursive pseudo-well-orderings, Trans. Amer. Math. Soc. 131 (1968), 526-543. MR 39 #5366. MR 0244049 (39:5366)
  • [11] R. B. Jensen, Definable sets of minimal degree, Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968), edited by Y. Bar-Hillel, North-Holland, Amsterdam, 1970, pp. 122-128. MR 46 #5130. MR 0306002 (46:5130)
  • [12] C. G. Jockusch, Jr., An application of $ \Sigma _4^0$ determinacy to the degrees of unsolvability, J. Symbolic Logic 38 (1973), 293-294. MR 0332459 (48:10786)
  • [13] C. G. Jockusch, Jr. and R. I. Soare, Degrees of members of $ \Pi _1^0$ classes, Pacific J. Math. 40 (1972), 605-616. MR 46 #8827. MR 0309722 (46:8827)
  • [14] -, A minimal pair of $ \Pi _1^0$ classes, J. Symbolic. Logic 36 (1971), 66-78. MR 44 #68. MR 0282834 (44:68)
  • [15] -, Minimal covers and arithmetical sets, Proc. Amer. Math. Soc. 25 (1970), 856-859. MR 42 #67. MR 0265154 (42:67)
  • [16] -, $ \Pi _1^0$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33-56. MR 47 #4775. MR 0316227 (47:4775)
  • [17] A. S. Kechris, The theory of countable analytical sets, Trans. Amer. Math. Soc. 202 (1975), 259-297. MR 0419235 (54:7259)
  • [18] S. C. Kleene, Quantification of number-theoretic functions, Compositio Math. 14 (1959), 23-40. MR 21 #2586. MR 0103822 (21:2586)
  • [19] G. Kreisel and G. E. Sacks, Metarecursive sets, J. Symbolic Logic 30 (1965), 318-338. MR 35 #4097. MR 0213233 (35:4097)
  • [20] D. A. Martin, The axiom of determinateness and reduction principles in the analytic hierarchy, Bull. Amer. Math. Soc. 74 (1968), 687-689. MR 37 #2607. MR 0227022 (37:2607)
  • [21] -, Measurable cardinals and analytic games, Fund. Math. 66 (1969/70), 287-291. MR 41 #3283. MR 0258637 (41:3283)
  • [22] D. A. Martin and R. M. Solovay, A basic theorem for $ \Sigma _3^1$ sets of reals, Ann. of Math. (2) 89 (1969), 138-159. MR 41 #53. MR 0255391 (41:53)
  • [23] J. B. Paris, $ ZF \vdash \Sigma _4^0$ determinateness, J. Symbolic Logic 37 (1972), 661-667. MR 0363904 (51:159)
  • [24] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)
  • [25] G. E. Sacks, Countable admissible ordinals and hyperdegrees, Advances in Math. (to appear). MR 0429523 (55:2536)
  • [26] -, Forcing with perfect closed sets, Proc. Sympos. Pure Math., vol. 13, part I, Amer. Math. Soc., Providence, R. I., 1971, pp. 331-355. MR 43 #1827. MR 0276079 (43:1827)
  • [27] -, Measure-theoretic uniformity in recursion theory and set theory, Trans. Amer. Math. Soc. 142 (1969), 381-420. MR 40 #7108. MR 0253895 (40:7108)
  • [28] L. P. Sasso, A minimal degree not realizing least possible jump, J. Symbolic Logic 39 (1974), 571-574. MR 0360242 (50:12692)
  • [29] J. R. Shoenfield, Mathematical logic, Addison-Wesley, Reading, Mass., 1967. MR 37 #1224. MR 0225631 (37:1224)
  • [30] -, Unramified forcing, Proc. Sympos. Pure Math., vol. 13, part I, Amer. Math. Soc., Providence, R. I., 1971, pp. 357-381. MR 43 #6079. MR 0280359 (43:6079)
  • [31] S. G. Simpson, Some results on hyperdegrees, Notices Amer. Math. Soc. 18 (1971), 565. Abstract #71T-E36.
  • [32] -, A remark on the elementary theory of the hyperdegrees, Notices Amer. Math. Soc. 18 (1971), 661. Abstract #71T-E40.
  • [33] R. M. Solovay, A nonconstructible $ \Delta _3^1$ set of integers, Trans. Amer. Math. Soc. 127 (1967), 50-75. MR 35 #2748. MR 0211873 (35:2748)
  • [34] C. Spector, Recursive well-orderings, J. Symbolic Logic 20 (1955), 151-163. MR 17, 570; 1437. MR 0074347 (17:570b)
  • [35] -, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581-592. MR 18, 552; 1118. MR 0082457 (18:552d)
  • [36] S. K. Thomason, The forcing method and the upper semilattice of hyperdegrees, Trans. Amer. Math. Soc. 129 (1967) 38-57. MR 36 #2503. MR 0219421 (36:2503)
  • [37] -, On initial segments of hyperdegrees, J. Symbolic Logic 35 (1970), 189-197. MR 44 #5225. MR 0288027 (44:5225)
  • [38] H. M. Friedman, Bar induction and $ \Pi _1^1 - CA$, J. Symbolic Logic 34 (1969), 353-362. MR 40 #4109. MR 0250877 (40:4109)
  • [39] L. Harrington and A. S. Kechris, A basis result for $ \Sigma _3^0$ sets of reals with an application to minimal covers, Proc. Amer. Math. Soc. (to appear). MR 0398832 (53:2683)
  • [40] -, $ \Pi _2^1$ singletons and $ {O^\char93 }$, Fund. Math. (to appear).
  • [41] G. E. Sacks and S. G. Simpson, The $ \alpha $-finite injury method, Ann. Math. Logic 4 (1972), 343-367. MR 0369041 (51:5277)
  • [42] S. G. Simpson, Degree theory on admissible ordinals, Generalized Recursion Theory, edited by J. E. Fenstad and P. G. Hinman, North-Holland, Amsterdam, 1974, 165-193. MR 0537203 (58:27405)
  • [43] C. E. M. Yates, Prioric games and minimal degrees below 0', Fund. Math. 82 (1974), 217-237. MR 0406784 (53:10570)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02F30

Retrieve articles in all journals with MSC: 02F30


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1975-0392534-3
Keywords: Hyperdegrees, hyperjump, degrees of unsolvability, Turing degrees, constructible sets, sharp operation
Article copyright: © Copyright 1975 American Mathematical Society

American Mathematical Society