A minimal pair of recursively enumerable degrees

DOI10.2307/2269807zbMath0143.25402OpenAlexW2051601785WikidataQ56430706 ScholiaQ56430706MaRDI QIDQ5519131

C. E. M. Yates

Publication date: 1966

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

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

zbMATH Keywords

mathematical logic

Related Items (44)

Decomposition and infima in the computably enumerable degrees ⋮ 2000 Annual Meeting of the Association for Symbolic Logic ⋮ Structural interactions of the recursively enumerable T- and W-degrees ⋮ On Pairs of Recursively Enumerable Degrees ⋮ An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees ⋮ Classification of degree classes associated with r.e. subspaces ⋮ THE n-r.e. DEGREES: UNDECIDABILITY AND Σ₁ SUBSTRUCTURES ⋮ The discontinuity of splitting in the recursively enumerable degrees ⋮ A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees ⋮ On the Degrees of Index Sets ⋮ Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree ⋮ Decomposition of Recursively Enumerable Degrees ⋮ An extended Lachlan splitting theorem ⋮ Intervals containing exactly one c.e. degree ⋮ The Quotient Semilattice of the Recursively Enumerable Degrees Modulo the Cappable Degrees ⋮ Cupping and noncapping in the r.e. weak truth table and turing degrees ⋮ Infima in the recursively enumerable weak truth table degrees ⋮ Not every finite lattice is embeddable in the recursively enumerable degrees ⋮ Towards characterizing the \(> \omega^2\)-fickle recursively enumerable Turing degrees ⋮ Some results about the R.E. degrees ⋮ Elementary differences between the degrees of unsolvability and degrees of compressibility ⋮ Many-one reductions and the category of multivalued functions ⋮ Complementing cappable degrees in the difference hierarchy. ⋮ Branching Degrees above low Degrees ⋮ On Lachlan's major sub-degree problem ⋮ The decision problem for recursively enumerable degrees ⋮ A hierarchy for the plus cupping Turing degrees ⋮ Infima in the d.r.e. degrees ⋮ Undecidability and 1-types in the recursively enumerable degrees ⋮ Incomparable prime ideals of recursively enumerable degrees ⋮ Extending the Cooper minimal pair theorem ⋮ \(\Sigma_2\) induction and infinite injury priority arguments. III: Prompt sets, minimal pairs and Shoenfield's conjecture ⋮ A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees preserving greatest element ⋮ Lattice nonembeddings and intervals of the recursively enumerable degrees ⋮ Recursively enumerable sets and degrees ⋮ Cupping and Diamond Embeddings: A Unifying Approach ⋮ The recursively enumerable degrees have infinitely many one-types ⋮ Degree Structures: Local and Global Investigations ⋮ The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable ⋮ A necessary and sufficient condition for embedding ranked finite partial lattices into the computably enumerable degrees ⋮ On the existence of a strong minimal pair ⋮ Definability in the Recursively Enumerable Degrees ⋮ Cappable recursively enumerable degrees and Post's program ⋮ The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical

Cites Work

• The recursively enumerable degrees are dense
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Degrees of Unsolvability. (AM-55)
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: A minimal pair of recursively enumerable degrees