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

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.