Branching in the enumeration degrees of the \(\Sigma_2^0\) sets
type: Item
instance of: scholarly article
title: Branching in the enumeration degrees of the \(\Sigma_2^0\) sets
zbMATH Open document ID: 0924.03080
DOI: 10.1007/BF02808174
author: André Nies
author: Andrea Sorbi
published in: Israel Journal of Mathematics
publication date: 1999-09-15T00:00:00Z
review text: A set \(A\) is enumeration reducible to a set \(B\) (\(A\leq_e B\)) if there exists an effective procedure for enumerating \(A\), given any enumeration of \(B.A\equiv_e B\) iff \(A\leq_e B \& B\leq_e A\). The \(\equiv_e\)-equivalence classes are called enumeration degrees. This paper proves that any incomplete \(\Sigma^0_2\) enumeration degree \(\mathbf c\) is a branching degree, namely, there exist two \(\Sigma^0_2\) enumeration degrees \(\mathbf a\), \(\mathbf b\) such that \(\mathbf c < \mathbf a \& \mathbf c < \mathbf b \& \mathbf c =\mathbf a\wedge \mathbf b\). This shows another elementary difference between enumeration degrees below \({\mathbf{0}}_{\mathbf e}'\) and the recursively enumerable degrees.
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 1310631
zbMATH Keywords: enumeration degrees
zbMATH Keywords: branching degree
reviewed by: Xizhong Zheng
MaRDI profile type: Publication
cites work: Embedding the diamond in the Σ2 enumeration degrees
cites work: Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense
cites work: Q3487329
cites work: The density of the nonbranching degrees
cites work: Reducibility and Completeness for Sets of Integers
cites work: Lower Bounds for Pairs of Recursively Enumerable Degrees
cites work: Q5670617
cites work: Not every finite lattice is embeddable in the recursively enumerable degrees
cites work: The \(n\)-rea enumeration degrees are dense
cites work: On minimal pairs of enumeration degrees
cites work: Jumps of quasi-minimal enumeration degrees
cites work: Q5573961
cites work: The density of infima in the recursively enumerable degrees
cites work: Q4040892
cites work: Q4348132
full work available at URL: https://doi.org/10.1007/bf02808174
OpenAlex ID: W2004547606
description: scientific article; zbMATH DE number 1310631