Complementation in the Turing degrees

DOI10.2307/2275022zbMath0691.03024OpenAlexW2131652429MaRDI QIDQ3032238

Theodore A. Slaman, J. R. Steel

Publication date: 1989

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

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

zbMATH Keywords

r.e. degreespair of complements

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Cupping with random sets, Minimal complements for degrees below 0′, Intervals containing exactly one c.e. degree, The jump is definable in the structure of the degrees of unsolvability, Strong noncuppability in low computably enumerable degrees, Generic degrees are complemented, \(\Sigma_2\) induction and infinite injury priority arguments. III: Prompt sets, minimal pairs and Shoenfield's conjecture, A single minimal complement for the c.e. degrees, Weak density and cupping in the d-r.e. degrees, Computably enumerable Turing degrees and the meet property, Extensions of embeddings below computably enumerable degrees, A note on the join property, Dynamic notions of genericity and array noncomputability

Cites Work

• On degrees of recursive unsolvability
• The upper semi-lattice of degrees of recursive unsolvability
• The strong anticupping property for recursively enumerable degrees
• The impossibility of finding relative complements for recursively enumerable degrees