Lattice nonembeddings and intervals of the recursively enumerable degrees (Q1802183)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lattice nonembeddings and intervals of the recursively enumerable degrees |
scientific article |
Statements
Lattice nonembeddings and intervals of the recursively enumerable degrees (English)
0 references
10 March 1994
0 references
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.
0 references
recursively enumerable degrees
0 references
nonembedding
0 references
critical triple
0 references
0 references