## $\Pi ^{0}_{1}$ classes and degrees of theories

HTML articles powered by AMS MathViewer

- by Carl G. Jockusch and Robert I. Soare PDF
- Trans. Amer. Math. Soc.
**173**(1972), 33-56 Request permission

## 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

- A. Ehrenfeucht,
*Separable theories*, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.**9**(1961), 17–19. MR**131978** - William Feller,
*An introduction to probability theory and its applications. Vol. II*, John Wiley & Sons, Inc., New York-London-Sydney, 1966. MR**0210154** - Richard Friedberg,
*A criterion for completeness of degrees of unsolvability*, J. Symbolic Logic**22**(1957), 159–160. MR**98025**, DOI 10.2307/2964177 - Harvey M. Friedman,
*Borel sets and hyperdegrees*, J. Symbolic Logic**38**(1973), 405–409. MR**335248**, DOI 10.2307/2273034 - William 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**0210570** - Leon Henkin,
*The completeness of the first-order functional calculus*, J. Symbolic Logic**14**(1949), 159–166. MR**33781**, DOI 10.2307/2267044 - A. Janiczak,
*Undecidability of some simple formalized theories*, Fund. Math.**40**(1953), 131–139. MR**60439**, DOI 10.4064/fm-40-1-131-139 - Carl G. Jockusch Jr.,
*Uniformly introreducible sets*, J. Symbolic Logic**33**(1968), 521–536. MR**237330**, DOI 10.2307/2271359 - C. G. Jockusch Jr. and T. G. McLaughlin,
*Countable retracing functions and $\Pi _{2}{}^{0}$ predicates*, Pacific J. Math.**30**(1969), 67–93. MR**269508**, DOI 10.2140/pjm.1969.30.67 - 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,
*Degrees of members of $\Pi ^{0}_{1}$ classes*, Pacific J. Math.**40**(1972), 605–616. MR**309722**, DOI 10.2140/pjm.1972.40.605 - Stephen Cole Kleene,
*Introduction to metamathematics*, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR**0051790** - Webb Miller and D. A. Martin,
*The degrees of hyperimmune sets*, Z. Math. Logik Grundlagen Math.**14**(1968), 159–166. MR**228341**, DOI 10.1002/malq.19680140704 - Emil L. Post,
*Recursively enumerable sets of positive integers and their decision problems*, Bull. Amer. Math. Soc.**50**(1944), 284–316. MR**10514**, DOI 10.1090/S0002-9904-1944-08111-1 - Marian Boykan Pour-El and Saul Kripke,
*Deduction-preserving “recursive isomorphisms” between theories*, Fund. Math.**61**(1967), 141–163. MR**252226**, DOI 10.4064/fm-61-2-141-163 - H. G. Rice,
*Recursive and recursively enumerable orders*, Trans. Amer. Math. Soc.**83**(1956), 277–300. MR**83454**, DOI 10.1090/S0002-9947-1956-0083454-0 - Hartley Rogers Jr.,
*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462** - Gerald E. Sacks,
*Degrees of unsolvability*, Princeton University Press, Princeton, N.J., 1963. MR**0186554** - Dana Scott,
*Algebras of sets binumerable in complete extensions of arithmetic*, Proc. Sympos. Pure Math., Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 117–121. MR**0141595**
D. Scott and S. Tennenbaum, - J. R. Shoenfield,
*The class of recursive functions*, Proc. Amer. Math. Soc.**9**(1958), 690–692. MR**95780**, DOI 10.1090/S0002-9939-1958-0095780-7 - J. R. Shoenfield,
*Degrees of models*, J. Symbolic Logic**25**(1960), 233–237. MR**139525**, DOI 10.2307/2964680 - J. R. Shoenfield,
*A theorem on minimal degrees*, J. Symbolic Logic**31**(1966), 539–544. MR**205850**, DOI 10.2307/2269688 - Robert I. Soare,
*Sets with no subset of higher degree*, J. Symbolic Logic**34**(1969), 53–56. MR**263627**, DOI 10.2307/2270981 - Alfred Tarski,
*Undecidable theories*, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1953. In collaboration with Andrzej Mostowski and Raphael M. Robinson. MR**0058532**

*On the degrees of complete extensions of arithmetic*, Notices Amer. Math. Soc.

**7**(1960), 242-243. Abstract #568-3.

## Additional Information

- © Copyright 1972 American Mathematical Society
- 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