The upper semilattice of degrees ≤ 0′ is complemented

DOI10.2307/2273220zbMath0517.03015OpenAlexW2022731330MaRDI QIDQ3665088

David B. Posner

Publication date: 1981

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

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

zbMATH Keywords

joincomplementdegrees of unsolvabilityjump operation

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (10)

Embedding the Diamond Lattice in the Recursively Enumerable Truth-Table Degrees ⋮ Complementing below recursively enumerable degrees ⋮ Minimal complements for degrees below 0′ ⋮ Complements for enumeration \(\Pi_1^0\)-degrees ⋮ Complementing cappable degrees in the difference hierarchy. ⋮ Jump inversions inside effectively closed sets and applications to randomness ⋮ Generic degrees are complemented ⋮ Cupping and noncupping in the enumeration degrees of \(\Sigma_ 2^ 0\) sets ⋮ T-Degrees, Jump Classes, and Strong Reducibilities ⋮ Two Theorems on Truth Table Degrees

Cites Work

• On degrees of unsolvability
• Degrees joining to 0′
• Minimal degrees and the jump operator
• Simple Proofs of Some Theorems on High Degrees of Unsolvability
• The impossibility of finding relative complements for recursively enumerable degrees
• Degrees in Which the Recursive Sets are Uniformly Recursive

This page was built for publication: The upper semilattice of degrees ≤ 0′ is complemented