A non-splitting theorem in the enumeration degrees (Q1032639): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.apal.2009.01.009 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2132253471 / rank | |||
Normal rank |
Revision as of 23:39, 19 March 2024
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