The recursively enumerable degrees are dense

From MaRDI portal
Publication:2520837

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




Related Items

A note on the enumeration degrees of 1-generic setsAn Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple DegreesCompletely mitotic r. e. degreesIntervals and sublattices of the r.e. weak truth table degrees. I: DensityClassification of degree classes associated with r.e. subspacesRecursively enumerable \(m\)- and \(tt\)-degrees. II: The distribution of singular degreesOn the problem of the critical boundThere exists a maximal 3-c.e. enumeration degreeThe ∀∃-theory of ℛ(≤,∨,∧) is undecidableLower bounds on degrees of game-theoretic structuresBi-isolation in the d.c.e. degreesDegrees of unsolvability of continuous functionsNon-p-generic and strongly nonbranching degreeDegrees of Unsolvability: A TutorialOn the Degrees of Index SetsMetarecursively enumerable sets and their metadegreesA limit on relative genericity in the recursively enumerable setsEuropean Summer Meeting of the Association for Symbolic Logic (Logic Colloquium '88), Padova, 1988Interpolating \(d\)-r.e. and REA degrees between r.e. degreesInitial segments of the degrees of unsolvability Part II: minimal degreesIntervals containing exactly one c.e. degreeNon-p-generic and strongly nonbranching degreeThe Quotient Semilattice of the Recursively Enumerable Degrees Modulo the Cappable DegreesComputational processes, observers and Turing incompletenessNot every finite lattice is embeddable in the recursively enumerable degreesNormalizing notations in the Ershov hierarchyCoding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classesIsolation from side and cone avoidance in the 2-computably enumerable \textit{wtt}-degreesMinimal Weak Truth Table Degrees and Computably Enumerable Turing DegreesOn the Degrees of Index Sets. IIClasses of Polish spaces under effective Borel isomorphismThe computable Lipschitz degrees of computably enumerable sets are not denseThere Are No Maximal d.c.e. wtt-degreesLowness, Randomness, and Computable AnalysisSome Algebraic Properties of Machine Poset of Infinite WordsDecomposability of low 2-computably enumerable degrees and Turing jumps in the Ershov hierarchyIsolated maximal d.r.e. degreesThe weak density of properly d-r. e. branching degree in the d-r. e. degreesComplementing cappable degrees in the difference hierarchy.Generalized nonsplitting in the recursively enumerable degreesAn incomplete set of shortest descriptionsIsolation from side in 2-computably enumerable degreesThe Sacks density theorem and Σ2-boundingThe d.r.e. degrees are not denseOn Lachlan's major sub-degree problemWeak density and nondensity among transfinite levels of the Ershov hierarchyGeneric degrees are complementedInfima in the d.r.e. degreesOn Downey's conjectureUndecidability and 1-types in the recursively enumerable degreesIncomparable prime ideals of recursively enumerable degreesThe distribution of the generic recursively enumerable degreesRecursive isomorphism types of recursive Boolean algebrasRecursive Boolean algebras with recursive atomsExtending the Cooper minimal pair theoremA survey of results on the d.c.e. and \(n\)-c.e. degreesThere are no maximal low d.c.e. degreesCompleteness in the arithmetical hierarchy and fixed pointsTuring computability: structural theoryLattice nonembeddings and intervals of the recursively enumerable degreesElementary differences among jump classesON EXTENSIONS OF EMBEDDINGS INTO THE ENUMERATION DEGREES OF THE ${\Sigma_2^0}$-SETSRecursively enumerable sets and degreesSplitting and nonsplitting, II: A low2 c.e. degree above which 0′ is not splittableFINDING THE LIMIT OF INCOMPLETENESS IMass problems associated with effectively closed setsA non-splitting theorem in the enumeration degreesHypersimple sets with retraceable complementsDegree Structures: Local and Global InvestigationsThe $\Pi _3$-theory of the computably enumerable Turing degrees is undecidableOn Σ1-Structural Differences Among Finite Levels of the Ershov HierarchyDegrees of monotone complexityOn the existence of a strong minimal pairAutomorphisms of the lattice of recursively enumerable setsNonisolated degrees and the jump operatorThe density of the nonbranching degreesDefinability in the Recursively Enumerable DegreesUndecidability and 1-types in intervals of the computably enumerable degreesA minimal pair of recursively enumerable degreesThe density of infima in the recursively enumerable degreesMetarecursive setsThe impossibility of finding relative complements for recursively enumerable degrees