Embeddings of \(N_5\) and the contiguous degrees (Q5956887): Difference between revisions

The authors prove the very attractive result that a computably enumerable degree \({\mathbf a}\) is contiguous (meaning that it contains a single c.e. weak truth table degree) iff it is the top of no embedding of the 5-element nonmodular lattice \(N_5\) into the computably enumerable degrees. This extends an earlier result of \textit{R. G. Downey} and \textit{S. Lempp} [J. Symb. Log. 62, 1215-1240 (1997; Zbl 0897.03047)] who showed that a c.e. degree is contiguous iff it is ``locally distributive.'' The proof is akin to the Downey-Lempp proof but with an added layer of nonuniformity. It is very well written.