The Journal of Symbolic Logic

Research Article

On the Σ 2-theory of the upper semilattice of Turing degrees

Carl G. Jockusch Jra1 1 and Theodore A. Slamana2 2

a1 Department of Mathematics, University of Illinois, Urbana, Illinois 61801, E-mail: jockusch@symcom.math.uiuc.edu

a2 Department of Mathematics, The University of Chicago, Chicago, Illinois 60637, E-mail: ted@zaphod.uchicago.edu

A first-order sentence Φ is Σ 2 if there is a quantifier-free formula Θ such that Φ has the form . The Σ 2-theory of a structure for a language ℒ is the set of Σ 2-sentences of true in . It was shown independently by Lerman and Shore (see [Le, Theorem VII.4.4]) that the Σ 2-theory of the structure = 〈D, ≤ 〉 is decidable, where D is the set of degrees of unsolvability and ≤ is the standard ordering of D. This result is optimal in the sense that the Σ 3-theory of is undecidable, a result due to J. Schmerl. (For a proof, see [Le, Theorem VII.4.5]. As Lerman has pointed out, this proof should be corrected by defining θσ to be ∀ 1(x) rather than ∀x(ψ(x)σ1(x)).) Nonetheless, in this paper we extend the decidability result of Lerman and Shore by showing that the Σ 2-theory of is decidable, where ⋃ is the least upper bound operator and 0 is the least degree. Of course ⋃ is definable in , but many interesting degree-theoretic results are expressible as Σ 2-sentences in the language of but not as Σ 2-sentences in the language of . For instance, Simpson observed that the Posner-Robinson cupping theorem could be used to show that for any nonzero degrees a, b, there is a degree g such that bag, and bg (see [PR, Corollary 6]). However, the Posner-Robinson technique does not seem to suffice to decide the Σ 2-theory of . We introduce instead a new method for coding a set into the join of two other sets and use it to decide this theory.

(Received March 14 1991)

(Revised March 10 1992)

Footnotes

1   The authors acknowledge the support of NSF Grants DMS-8902641 and also of the congress “Mathematical Logic and its Applications,” held in Nagoya, Japan in 1988, where this work originated.

2   The authors acknowledge the support of NSF Grants DMS-8902437, Presidential Young Investigator Award DMS-8451748 and also of the congress “Mathematical Logic and its Applications,” held in Nagoya, Japan in 1988, where this work originated.