A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees (Q1368585): Difference between revisions

It is a long standing open question, which finite partial lattices can be embedded into \(E\), the poset of recursively enumerable degrees. The most general results for the lattice setting were obtained by \textit{K. Ambos-Spies} and \textit{M. Lerman} [``Lattice embeddings into the recursively enumerable degrees. I, II'', J. Symb. Logic 51, 257-272 (1986; Zbl 0633.03037) and ibid. 54, 735-760 (1989; Zbl 0687.03022)]. They presented a sufficient condition, NEC, for nonembeddability, and a sufficient condition, NE, for embeddability. Although many people had conjectured that these conditions are, in fact, complementary, they were unable to prove this. The present paper shows that this conjecture is not true by exhibiting a nonembeddable 20-element lattice, \(L_{20}\), which fails to have critical triples (the pairwise-incomparable triples \(a,b,c\) with \(a\vee b= a\vee c\) and \(b\wedge c\leq a)\), hence fails to satisfy NEC, because every lattice which satisfies NEC has a critical triple. This contradicts also Downey's conjecture that a finite lattice is embeddable into every nontrivial interval of \(E\) iff it has no critical triple.