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)

 
 

 

$ \Pi \sp{0}\sb{1}$ classes and degrees of theories


Authors: Carl G. Jockusch and Robert I. Soare
Journal: Trans. Amer. Math. Soc. 173 (1972), 33-56
MSC: Primary 02F30; Secondary 02F35, 02G05
DOI: https://doi.org/10.1090/S0002-9947-1972-0316227-0
MathSciNet review: 0316227
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Using the methods of recursive function theory we derive several results about the degrees of unsolvability of members of certain $ \Pi _1^0$ classes of functions (i.e. degrees of branches of certain recursive trees). As a special case we obtain information on the degrees of consistent extensions of axiomatizable theories, in particular effectively inseparable theories such as Peano arithmetic, $ {\mathbf{P}}$. For example: THEOREM 1. If a degree $ {\mathbf{a}}$ contains a complete extension of $ {\mathbf{P}}$, then every countable partially ordered set can be embedded in the ordering of degrees $ \leqslant {\mathbf{a}}$. (This strengthens a result of Scott and Tennenbaum that no such degree $ {\mathbf{a}}$ is a minimal degree.) THEOREM 2. If $ {\mathbf{T}}$ is an axiomatizable, essentially undecidable theory, and if $ \{ {{\mathbf{a}}_n}\} $ is a countable sequence of nonzero degrees, then $ {\mathbf{T}}$ has continuum many complete extensions whose degrees are pairwise incomparable and incomparable with each $ {{\mathbf{a}}_n}$. THEOREM 3. There is a complete extension $ {\mathbf{T}}$ of $ {\mathbf{P}}$ such that no nonrecursive arithmetical set is definable in $ {\mathbf{T}}$. THEOREM 4. There is an axiomatizable, essentially undecidable theory $ {\mathbf{T}}$ such that any two distinct complete extensions of $ {\mathbf{T}}$ are Turing incomparable. THEOREM 5. The set of degrees of consistent extensions of $ {\mathbf{P}}$ is meager and has measure zero.


References [Enhancements On Off] (What's this?)

  • [1] A. Ehrenfeucht, Separable theories, Bull. Acad. Polon. Sci. Sér. Sci. Math Astronom. Phys. 9 (1961), 17-19. MR 24 #A1825. MR 0131978 (24:A1825)
  • [2] W. Feller, An introduction to probability theory and its applications, Vol. II, Wiley, New York, 1966. MR 35 #1048. MR 0210154 (35:1048)
  • [3] R. M. Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159-160. MR 20 #4488. MR 0098025 (20:4488)
  • [4] H. Friedman, Borel sets and hyperdegrees (to appear). MR 0335248 (49:30)
  • [5] W. Hanf, Model-theoretic methods in the study of elementary logic, Theory of Models (Proc. 1963 Internat. Sympos., Berkeley), North-Holland, Amsterdam, 1965, pp. 132-145. MR 35 #1457. MR 0210570 (35:1457)
  • [6] L. Henkin, The completeness of the first-order functional calculus, J. Symbolic Logic 14 (1949), 159-166. MR 11, 487. MR 0033781 (11:487d)
  • [7] A. Janiczak, Undecidability of some simple formalized theories, Fund. Math. 40 (1953), 131-139. MR 15, 669; 1140. MR 0060439 (15:669c)
  • [8] C. G. Jockusch, Jr., Uniformly introreducible sets, J. Symbolic Logic 33 (1968), 521-536. MR 38 #5619. MR 0237330 (38:5619)
  • [9] C. G. Jockusch, Jr. and T. G. McLaughlin, Countable retracing functions and $ \Pi _2^0$ predicates, Pacific J. Math. 30 (1969), 67-93. MR 42 #4403. MR 0269508 (42:4403)
  • [10] C. G. Jockusch, Jr. and R. I. Soare, A minimal pair of $ \Pi _1^0$ classes, J. Symbolic Logic 36 (1971), 66-78. MR 0282834 (44:68)
  • [11] -, Degrees of members of $ \Pi _1^0$ classes, Pacific J. Math. 40 (1972), 605-616. MR 0309722 (46:8827)
  • [12] S. C. Kleene, Introduction to metamathematics, Van Nostrand, Princeton, N. J., 1950. MR 14, 525. MR 0051790 (14:525m)
  • [13] W. Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlagen Math. 14 (1968), 159-166. MR 37 #3922. MR 0228341 (37:3922)
  • [14] E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math Soc. 50 (1944), 284-316. MR 6, 29. MR 0010514 (6:29f)
  • [15] M. B. Pour-El and S. Kripke, Deduction-preserving ``recursive isomorphisms'' between theories, Fund. Math. 61 (1967), 141-163. MR 40 #5447. MR 0252226 (40:5447)
  • [16] H. G. Rice, Recursive and recursively enumerable orders, Trans. Amer. Math. Soc. 83 (1956), 277-300. MR 18, 712. MR 0083454 (18:712a)
  • [17] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)
  • [18] G. E. Sacks, Degrees of unsolvability, Ann. of Math. Studies No. 55, Princeton Univ. Press, Princeton, N. J., 1963. MR 32 #4013. MR 0186554 (32:4013)
  • [19] D. Scott, Algebras of sets binumerable in complete extensions of arithmetic, Proc. Sympos. Pure Math., vol. 5, Amer. Math. Soc., Providence, R. I., 1962, pp. 117-121. MR 25 #4993. MR 0141595 (25:4993)
  • [20] D. Scott and S. Tennenbaum, On the degrees of complete extensions of arithmetic, Notices Amer. Math. Soc. 7 (1960), 242-243. Abstract #568-3.
  • [21] J. R. Shoenfield, The class of recursive functions, Proc. Amer. Math. Soc. 9 (1958), 690-692. MR 0095780 (20:2281)
  • [22] -, Degrees of models, J. Symbolic Logic 25 (1960), 233-237. MR 0139525 (25:2957)
  • [23] -, A theorem on minimal degrees, J. Symbolic Logic 31 (1966), 539-544. MR 0205850 (34:5676)
  • [24] R. I. Soare, Sets with no subset of higher degree, J. Symbolic Logic 34 (1969), 53-56. MR 41 #8228. MR 0263627 (41:8228)
  • [25] A. Tarski, A. Mostowski and R. M. Robinson, Undecidable theories, North-Holland, Amsterdam, 1953. MR 0058532 (15:384h)

Similar Articles

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

Retrieve articles in all journals with MSC: 02F30, 02F35, 02G05


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1972-0316227-0
Keywords: Degree of unsolvability, axiomatizable theory, effectively inseparable theory, Peano arithmetic, $ \Pi _1^0$ classes, recursive trees
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society