Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
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?)


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: http://dx.doi.org/10.1090/S0002-9947-1972-0316227-0
PII: S 0002-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