The impossibility of finding relative complements for recursively enumerable degrees

DOI10.2307/2270459zbMath0156.01001OpenAlexW1986222532WikidataQ56430700 ScholiaQ56430700MaRDI QIDQ5537366

Alistair H. Lachlan

Publication date: 1966

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2270459

zbMATH Keywords

mathematical logic

Related Items

The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ Minimal upper bounds for arithmetical degrees ⋮ Generalized nonsplitting in the recursively enumerable degrees ⋮ The decision problem for recursively enumerable degrees ⋮ Complementation in the Turing degrees ⋮ Recursively enumerable sets and degrees ⋮ Degree Structures: Local and Global Investigations ⋮ The upper semilattice of degrees ≤ 0′ is complemented ⋮ Minimal complementation below uniform upper bounds for the arithmetical degrees ⋮ Definability in the Recursively Enumerable Degrees

Cites Work

• The recursively enumerable degrees are dense
• Recursively enumerable sets of positive integers and their decision problems