Branching in the \({\Sigma^0_2}\)-enumeration degrees: a new perspective (Q938234)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Branching in the \({\Sigma^0_2}\)-enumeration degrees: a new perspective |
scientific article |
Statements
Branching in the \({\Sigma^0_2}\)-enumeration degrees: a new perspective (English)
0 references
18 August 2008
0 references
A 1999 paper by \textit{A. Nies} and \textit{A. Sorbi} [Isr. J. Math. 110, 29--59 (1999; Zbl 0924.03080)] showed that every incomplete \(\Sigma_2^0\) enumeration degree can be written as the meet of two incomparable \(\Sigma_2^0\) e-degrees. The present paper arrives at this result by a different route, via the following theorem: For every e-incomplete \(\Sigma_2^0\) set~\(A\), there exists a noncomputable \(\Delta_2^0\) set~\(X\) such that any set simultaneously e-reducible to~\(A\) and Turing reducible to~\(X\) must be computable.
0 references
enumeration reducibility
0 references
semirecursive set
0 references
branching element
0 references
0 references