Π⁰₁ classes and degrees of theories
Carl G. Jockusch, Robert Irving Soare · Transactions of the American Mathematical Society · 1972
Using the methods of recursive function theory we derive several results about the degrees of unsolvability of members of certain Π 1 0 \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, P {\mathbf {P}} . For example: THEOREM 1. If a degree a {\mathbf {a}} contains a complete extension of P {\mathbf {P}} , then every countable partially ordered set can be embedded in the ordering of degrees ⩽ a \leqslant {\mathbf {a}} . (This strengthens a result of Scott and Tennenbaum that no such degree a {\mathbf {a}} is a minimal degree.) THEOREM 2. If T {\mathbf {T}} is an axiomatizable, essentially undecidable theory, and if { a n } \{ {{\mathbf {a}}_n}\} is a countable sequence of nonzero degrees, then T {\mathbf {T}} has continuum many complete extensions whose degrees are pairwise incomparable and incomparable with each a n {{\mathbf {a}}_n} . THEOREM 3. There is a complete extension T