A non-splitting theorem in the enumeration degrees (Q1032639)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A non-splitting theorem in the enumeration degrees
scientific article

    Statements

    A non-splitting theorem in the enumeration degrees (English)
    0 references
    26 October 2009
    0 references
    In an upper semilattice \(\langle D, <, \cup ,\rangle\) we say that a pair of elements \textbf{u} and \textbf{v} form a splitting of the element \textbf{a} if \({\mathbf u < \mathbf a}\) and \({\mathbf v < \mathbf a}\) but \({\mathbf u \cup \mathbf v = \mathbf a.}\) A set \(\mathbb{A}\) is enumeration reducible to a set \(\mathbb{B}\) if there is a c.e. set \(\Phi\) such that: \[ {\mathbf n \in \mathbb{A} \Leftrightarrow \exists \mathbf u(\langle \mathbf n,\mathbf u \rangle \in \Phi \, \& \, D_{\mathbf u} \subseteq \mathbb B)}, \] where \(D_{\mathbf u}\) denotes the finite set with canonical index \textbf{u}. The following statement is proved in the paper under review by adapting the non-splitting techniques from the c.e. Turing degrees to the enumeration degrees. Theorem. There is a \(\Sigma_2^0\)-enumeration degree \(\mathbf a< \mathbf 0'_e\) such that \(\mathbf 0'_e\) cannot be split in the enumeration degrees above the degree \textbf{a}. This result is an analog of Harrington's well-known non-splitting theorem for the \(\Sigma_2^0\)- enumeration degrees
    0 references
    enumeration reducibility
    0 references
    \(\Sigma_2^0\) e-degrees
    0 references
    e-degrees
    0 references
    non-splitting
    0 references

    Identifiers