Array nonrecursive degrees and lattice embeddings of the diamond

MaRDI QIDQ1320968zbMATH OpenFDO

Authors Rodney G. Downey

Publication date 16 February 1995

Published in Illinois Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

\(\Delta_ 2\) degreesarray nonrecursive degreeslattice embeddingrecursively enumerable degreestops of diamonds

Mathematics Subject Classification ID

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

Review text

Exactly which r.e. degrees are tops of diamonds in the \(\Delta_ 2\) degrees (with the least element \textbf{0}) is an important problem. Slaman guessed that all \(\text{low}_ 2\) degrees are bounded by degrees that are not tops of diamonds in the \(\Delta_ 2\) degrees. In this paper, the author answers Slaman's question negatively. To get this result, he proves a more general theorem: If an r.e. degree is array nonrecursive, then it is the top of a diamond in the \(\Delta_ 2\) degrees. (The concept of array nonrecursiveness gives a natural class of degrees that arise from arguments which need `multiple permissions'. It has been shown that this class contains members of low degree, is closed upwards, and contains all \(\text{non-low}_ 2\) r.e. degrees.) The author also gets some results about array nonrecursive degrees.

Recommendations

• Array nonrecursiveness and relative recursive enumerability
• Lattice embeddings and array noncomputable degrees
• D.R.E. Degrees and the Nondiamond Theorem
• scientific article; zbMATH DE number 3845570
• Diamond lattice embedded into d.r.e. degrees

Cited in

(12)

• Dynamic notions of genericity and array noncomputability
• Splitting theorems in recursion theory
• Lattice nonembeddings and intervals of the recursively enumerable degrees
• Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree
• Diamond embeddings into the enumeration degrees
• scientific article; zbMATH DE number 3845570 (Why is no real title available?)
• Lattice embeddings and array noncomputable degrees
• scientific article; zbMATH DE number 841084 (Why is no real title available?)
• Nonlowness is independent from fickleness
• Domination, forcing, array nonrecursiveness and relative recursive enumerability
• Embeddings of N₅ and the contiguous degrees
• Diamond lattice embedded into d.r.e. degrees

This page was built for publication: Array nonrecursive degrees and lattice embeddings of the diamond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1320968)