Array nonrecursive degrees and lattice embeddings of the diamond (Q1320968): Difference between revisions

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.