Array nonrecursive degrees and lattice embeddings of the diamond
type: Item
instance of: scholarly article
title: Array nonrecursive degrees and lattice embeddings of the diamond
zbMATH Open document ID: 0806.03030
published in: Illinois Journal of Mathematics
publication date: 1995-02-16T00:00:00Z
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.
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 561218
zbMATH Keywords: lattice embedding
zbMATH Keywords: recursively enumerable degrees
zbMATH Keywords: tops of diamonds
zbMATH Keywords: \(\Delta_ 2\) degrees
zbMATH Keywords: array nonrecursive degrees
author: Rodney G. Downey
reviewed by: Lei Qian
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 561218