Not every finite lattice is embeddable in the recursively enumerable degrees

DOI10.1016/0001-8708(80)90027-4zbMath0439.03024OpenAlexW2088993859WikidataQ56430701 ScholiaQ56430701MaRDI QIDQ1142206

Robert I. Soare, Alistair H. Lachlan

Publication date: 1980

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0001-8708(80)90027-4

zbMATH Keywords

embeddabilityfinite latticedegrees of unsolvabilityrecursively enumerable degrees

Mathematics Subject Classification ID

Structure and representation theory of distributive lattices (06D05) Structure theory of lattices (06B05) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (21)

Embedding finite lattices into the Σ₂⁰ enumeration degrees ⋮ A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees ⋮ Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree ⋮ Initial segments of the lattice of ideals of r.e. degrees ⋮ Towards characterizing the \(> \omega^2\)-fickle recursively enumerable Turing degrees ⋮ Embedding finite lattices into the ideals of computably enumerable turing degrees ⋮ TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES ⋮ Generalized nonsplitting in the recursively enumerable degrees ⋮ A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ Infima in the d.r.e. degrees ⋮ A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees preserving greatest element ⋮ Embeddings of \(N_5\) and the contiguous degrees ⋮ Lattice nonembeddings and intervals of the recursively enumerable degrees ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Lattice embeddings into the recursively enumerable degrees. II ⋮ Degree Structures: Local and Global Investigations ⋮ Branching in the enumeration degrees of the \(\Sigma_2^0\) sets ⋮ A necessary and sufficient condition for embedding ranked finite partial lattices into the computably enumerable degrees ⋮ The density of the nonbranching degrees ⋮ Definability in the Recursively Enumerable Degrees ⋮ The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On degrees of recursive unsolvability
• First-order theory of the degrees of recursive unsolvability
• The recursively enumerable degrees are dense
• Initial segments of the degrees of unsolvability
• Interpolation and embedding in the recursively enumerable degrees
• On the degrees less than 0'
• The upper semi-lattice of degrees of recursive unsolvability
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• The decision problem for recursively enumerable degrees
• Countable initial segments of the degrees of unsolvability
• Recursively enumerable sets and degrees
• A minimal pair of recursively enumerable degrees
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Distributive Initial Segments of the Degrees of Unsolvability
• Sublattices of the Recursively Enumerable Degrees
• On Suborderings of Degrees of Recursive Unsolvability
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Not every finite lattice is embeddable in the recursively enumerable degrees