Lattice nonembeddings and intervals of the recursively enumerable degrees
The elements \(x\), \(y\), \(z\) of an upper semilattice are said to form a critical triple if (1) the join of \(x\) and \(y\) equals that of \(y\) and \(z\), (2) \(x\not\leq y\), and (3) \(w\leq y\) when \(w\leq x\), \(z\). For example, in the five-element nondistributive modular lattice \(M_ 5\), the three intermediate elements constitute a critical triple. This paper is devoted to establishing the following theorem: Given r.e. degrees \({\mathbf b}\) and \({\mathbf c}\) with \({\mathbf b}>{\mathbf c}\), there exists an r.e. degree \({\mathbf a}\) with \({\mathbf b}>{\mathbf a}>{\mathbf c}\) such that there are no critical triples in the interval \([{\mathbf c},{\mathbf a}]\) (and thus, in particular, \(M_ 5\) cannot be embedded into \([{\mathbf c},{\mathbf a}]\)). The result, proved by a \(\text{\textbf{0}}'''\)-priority argument, is advanced by the authors as evidence for Downey's conjectured relationship between embeddability and critical triples.
scientific article; zbMATH DE number 219148
scientific article