A Survey of Non-RE Degrees ≤ O'
David B. Posner · Cambridge University Press eBooks · 1980
INTRODUCTION Most of the research on the degrees below O' has focused on the r.e. degrees. In part, this is a result of the origins of degree theory in logic where it was hoped that degrees of unsolvability would serve as a useful classification of the complexity of axiomatizable theories. Since we will be concentrating on the non-r.e.degrees below O', it seems appropriate to begin with an example which illustrates that non-r.e. degrees below O' also arise naturally in logic. Complete Theories and Degrees Below O' Let T be some essentially undecidable axiomatizable first-order theory (e.g., first-order Peano arithmetic or Zermelo-Fraenkel set theory). Since T is essentially undecidable, no complete extension of T is r.e. How constructive can complete extensions of T be? Consider the following construction of a complete extension of T. Fix some effective listing u 0 , u 1 , … of the sentences of the language of T and let v 0 , v 1 , … be an effective listing of T. Our construction takes place in stages. At stage s we effectively define a set of sentences C s which is, in effect, a finite approximation to a complete extension of T. More precisely, we require that for each i < s either u i or ∼u i is in C s and we require that no outright contradiction, i.e., u&∼u for some sentence u, be derivable from C s ∪ {v i : i ≤ s} by a proof with Godel number ≤ s. Since no complete extension of T is r.e. it is not possible to define (effectively) C s as described above in such a way that C s ⊆ C s+1 for a11 s.