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
    0 references
    0 references
    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

    Identifiers