The recursively enumerable degrees are dense

DOI10.2307/1970393zbMath0135.00702OpenAlexW2037416374WikidataQ56430703 ScholiaQ56430703MaRDI QIDQ2520837

Gerald E. Sacks

Publication date: 1964

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

mathematical logic

Related Items (82)

A note on the enumeration degrees of 1-generic sets ⋮ An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees ⋮ Completely mitotic r. e. degrees ⋮ Intervals and sublattices of the r.e. weak truth table degrees. I: Density ⋮ Classification of degree classes associated with r.e. subspaces ⋮ Recursively enumerable \(m\)- and \(tt\)-degrees. II: The distribution of singular degrees ⋮ On the problem of the critical bound ⋮ There exists a maximal 3-c.e. enumeration degree ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ Lower bounds on degrees of game-theoretic structures ⋮ Bi-isolation in the d.c.e. degrees ⋮ Degrees of unsolvability of continuous functions ⋮ Non-p-generic and strongly nonbranching degree ⋮ Degrees of Unsolvability: A Tutorial ⋮ On the Degrees of Index Sets ⋮ Metarecursively enumerable sets and their metadegrees ⋮ A limit on relative genericity in the recursively enumerable sets ⋮ European Summer Meeting of the Association for Symbolic Logic (Logic Colloquium '88), Padova, 1988 ⋮ Interpolating \(d\)-r.e. and REA degrees between r.e. degrees ⋮ Initial segments of the degrees of unsolvability Part II: minimal degrees ⋮ Intervals containing exactly one c.e. degree ⋮ Non-p-generic and strongly nonbranching degree ⋮ The Quotient Semilattice of the Recursively Enumerable Degrees Modulo the Cappable Degrees ⋮ Computational processes, observers and Turing incompleteness ⋮ Not every finite lattice is embeddable in the recursively enumerable degrees ⋮ Normalizing notations in the Ershov hierarchy ⋮ Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes ⋮ Isolation from side and cone avoidance in the 2-computably enumerable \textit{wtt}-degrees ⋮ Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees ⋮ On the Degrees of Index Sets. II ⋮ Classes of Polish spaces under effective Borel isomorphism ⋮ The computable Lipschitz degrees of computably enumerable sets are not dense ⋮ There Are No Maximal d.c.e. wtt-degrees ⋮ Lowness, Randomness, and Computable Analysis ⋮ Some Algebraic Properties of Machine Poset of Infinite Words ⋮ Decomposability of low 2-computably enumerable degrees and Turing jumps in the Ershov hierarchy ⋮ Isolated maximal d.r.e. degrees ⋮ The weak density of properly d-r. e. branching degree in the d-r. e. degrees ⋮ Complementing cappable degrees in the difference hierarchy. ⋮ Generalized nonsplitting in the recursively enumerable degrees ⋮ An incomplete set of shortest descriptions ⋮ Isolation from side in 2-computably enumerable degrees ⋮ The Sacks density theorem and Σ₂-bounding ⋮ The d.r.e. degrees are not dense ⋮ On Lachlan's major sub-degree problem ⋮ Weak density and nondensity among transfinite levels of the Ershov hierarchy ⋮ Generic degrees are complemented ⋮ Infima in the d.r.e. degrees ⋮ On Downey's conjecture ⋮ Undecidability and 1-types in the recursively enumerable degrees ⋮ Incomparable prime ideals of recursively enumerable degrees ⋮ The distribution of the generic recursively enumerable degrees ⋮ Recursive isomorphism types of recursive Boolean algebras ⋮ Recursive Boolean algebras with recursive atoms ⋮ Extending the Cooper minimal pair theorem ⋮ A survey of results on the d.c.e. and \(n\)-c.e. degrees ⋮ There are no maximal low d.c.e. degrees ⋮ Completeness in the arithmetical hierarchy and fixed points ⋮ Turing computability: structural theory ⋮ Lattice nonembeddings and intervals of the recursively enumerable degrees ⋮ Elementary differences among jump classes ⋮ ON EXTENSIONS OF EMBEDDINGS INTO THE ENUMERATION DEGREES OF THE ${\Sigma_2^0}$-SETS ⋮ Recursively enumerable sets and degrees ⋮ Splitting and nonsplitting, II: A low₂ c.e. degree above which 0′ is not splittable ⋮ FINDING THE LIMIT OF INCOMPLETENESS I ⋮ Mass problems associated with effectively closed sets ⋮ A non-splitting theorem in the enumeration degrees ⋮ Hypersimple sets with retraceable complements ⋮ Degree Structures: Local and Global Investigations ⋮ The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable ⋮ On Σ₁-Structural Differences Among Finite Levels of the Ershov Hierarchy ⋮ Degrees of monotone complexity ⋮ On the existence of a strong minimal pair ⋮ Automorphisms of the lattice of recursively enumerable sets ⋮ Nonisolated degrees and the jump operator ⋮ The density of the nonbranching degrees ⋮ Definability in the Recursively Enumerable Degrees ⋮ Undecidability and 1-types in intervals of the computably enumerable degrees ⋮ A minimal pair of recursively enumerable degrees ⋮ The density of infima in the recursively enumerable degrees ⋮ Metarecursive sets ⋮ The impossibility of finding relative complements for recursively enumerable degrees

This page was built for publication: The recursively enumerable degrees are dense