a1 Department of Mathematics, University of Illinois, Urbana, Illinois 61801, E-mail: firstname.lastname@example.org
a2 Department of Mathematics, The University of Chicago, Chicago, Illinois 60637, E-mail: email@example.com
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 ∀xσ 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 b ≤ a ⋃ g, and b ⋠ g (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)
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.