A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees
type: Item
instance of: scholarly article
title: A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees
zbMATH Open document ID: 0883.03025
DOI: 10.1016/S0168-0072(96)00031-0
author: Steffen Lempp
author: Manuel Lerman
published in: Annals of Pure and Applied Logic
publication date: 1998-03-23T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D25
zbMATH DE Number: 1067509
zbMATH Keywords: lattice embeddings
zbMATH Keywords: decidability
zbMATH Keywords: poset of recursively enumerable degrees
zbMATH Keywords: critical triples
reviewed by: Xizhong Zheng
MaRDI profile type: Publication
cites work: Lattice embeddings into the recursively enumerable degrees
cites work: Lattice embeddings into the recursively enumerable degrees. II
cites work: Lattice nonembeddings and initial segments of the recursively enumerable degrees
cites work: Lower Bounds for Pairs of Recursively Enumerable Degrees
cites work: Not every finite lattice is embeddable in the recursively enumerable degrees
cites work: Q4044555
cites work: Q3712325
cites work: Q4040892
cites work: Sublattices of the Recursively Enumerable Degrees
cites work: A minimal pair of recursively enumerable degrees
Recommended article: Embedding finite lattices into the ideals of computably enumerable turing degrees
Recommended article: Q4764099
Recommended article: Q5494233
Recommended article: Q3734391
Recommended article: TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES
Recommended article: A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees
Recommended article: A necessary and sufficient condition for embedding ranked finite partial lattices into the computably enumerable degrees
Recommended article: Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree
Recommended article: Lattice Embeddings in the Recursively Enumerable Truth Table Degrees
description: scientific article; zbMATH DE number 1067509