Lattice nonembeddings and intervals of the recursively enumerable degrees
type: Item
instance of: scholarly article
title: Lattice nonembeddings and intervals of the recursively enumerable degrees
zbMATH Open document ID: 0782.03020
DOI: 10.1016/0168-0072(93)90220-8
published in: Annals of Pure and Applied Logic
publication date: 1994-03-10T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D25
zbMATH DE Number: 219148
zbMATH Keywords: recursively enumerable degrees
zbMATH Keywords: nonembedding
zbMATH Keywords: critical triple
author: Peter A. Cholak
author: Rodney G. Downey
reviewed by: Leon Harkleroad
MaRDI profile type: Publication
full work available at URL: 0168-0072(93)90220-8
OpenAlex ID: W2061274683
cites work: Lattice embeddings into the recursively enumerable degrees
cites work: Lattice embeddings into the recursively enumerable degrees. II
cites work: Q3197813
cites work: Lattice nonembeddings and initial segments of the recursively enumerable degrees
cites work: There is no plus-capping degree
cites work: The density of the nonbranching degrees
cites work: TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
cites work: Pseudo Jump Operators. I: The R. E. Case
cites work: The upper semi-lattice of degrees of recursive unsolvability
cites work: Lower Bounds for Pairs of Recursively Enumerable Degrees
cites work: Q5670617
cites work: Not every finite lattice is embeddable in the recursively enumerable degrees
cites work: Q3232283
cites work: Recursively enumerable sets of positive integers and their decision problems
cites work: The recursively enumerable degrees are dense
cites work: Q5586291
cites work: The density of infima in the recursively enumerable degrees
cites work: On degrees of recursive unsolvability
cites work: Recursively enumerable sets and degrees
cites work: Sublattices of the Recursively Enumerable Degrees
cites work: A minimal pair of recursively enumerable degrees
Recommended article: Lattice nonembeddings and initial segments of the recursively enumerable degrees
Recommended article: Lattice embeddings into the recursively enumerable degrees
Recommended article: Lattice embeddings into the recursively enumerable degrees. II
Recommended article: Q4205432
Recommended article: Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree
Recommended article: Lattice embeddings and array noncomputable degrees
Recommended article: Array nonrecursive degrees and lattice embeddings of the diamond
Recommended article: The intervals of the lattice of recursively enumerable sets determined by major subsets
Recommended article: Embedding finite lattices into the Σ20 enumeration degrees
Recommended article: On lattice embeddings of a lattice into its intervals
description: scientific article; zbMATH DE number 219148