Embedding Finite Lattices into the Ideals of Computably Enumerable Turing Degrees

We show that the lattice L20 is not embeddable into the lattice of ideals of computably enumerable Turing degrees (J). We define a structure called a pseudolattice that generalizes the notion of a lattice, and show that there is a 112 necessary and sufficient condition for embedding a finite pseudolattice into J. ?1. The Lattice Embedding Problem. The problem of determining which finite lattices are embeddable into the upper semilattice of computably enumerable Turing degrees (M) has been studied intensively for over thirty years. A solution to the embedding problem would be an important step toward a decision procedure for the V3-theory of A. Calhoun began the investigation of embeddings into the lattice of ideals of computably enumerable Turing degrees (J) in [2], where he gave a sufficient condition for embedding a finite lattice into J. Clearly, any lattice that is embeddable into M is embeddable into 9J. However, the embedding problem for 9J is not the same as the embedding problem for A. While Lachlan and Soare [5] showed that the lattice S8 is not embeddable into A, Calhoun showed that S8 is embeddable into 'J. In fact, S8 is embeddable into any nontrivial initial segment of 'J as was shown by Weber [9]. Weber also gave a sufficient condition for embedding a finite lattice into any nontrivial initial segment of J. Until the present work, no finite lattice was known not to be embeddable into >J. For Q, Ambos-Spies and Lerman [1] generalized Lachlan and Soare's proof for S8 to obtain a non-embeddability condition, NEC. Until 1997 all finite lattices that were known not to be embeddable into % satisfied NEC. Lattices that satisfy NEC contain a critical triple: pairwise incomparable elements a, b, and c such that a V b = a V c and b A c < a. (Downey introduced the term critical triple in [3]. Weinstein independently gave an equivalent definition in [10].) For lattices that satisfy NEC, the combination of the critical triple with an infimum results in an obstruction to constructing an embedding into S. Since this type of obstruction can be overcome in constructing an embedding into J, some computability theorists (including the authors) were led to think that every finite lattice might be embeddable into J. However, we show that this is not the case. Lempp and Lerman [6] constructed a finite lattice, L20, without critical triple that cannot be embedded into A. We show that L20 is also not embeddable into ,J. The proof is based on the proof in [6]. However, we organize the proof in a Received May 1, 2000; accepted September 4, 2000. tResearch partially supported by NSF grant DMS-9625445. ( 2001, Association for Symbolic Logic 1791 0022-4812/01/6604-0017/$2.20 This content downloaded from 157.55.39.72 on Wed, 14 Sep 2016 04:17:11 UTC All use subject to http://about.jstor.org/terms 1792 WILLIAM C. CALHOUN AND MANUEL LERMAN