Low level nondefinability results: domination and recursive enumeration (Q2869914)

This study was motivated by a suggestion of \textit{W. Miller} and \textit{D. A. Martin} [Z. Math. Logik Grundlagen Math. 14, 159--166 (1968; Zbl 0216.29102)]. Recall that, for Turing degrees \(a\) and \(b\), \(a \mathrm{REA} b\) means \(a\) is r.e. in \(b\) and \(a \geq b\). A degree \(a\) is array nonrecursive (ANR) iff every \(b \geq a\) bears REA to another degree [\textit{M. Cai}, J. Symb. Log. 77, No. 1, 21--32 (2012; Zbl 1269.03044)]; otherwise it is array recursive (AR).NEWLINENEWLINEAmong the paper's many results: In the language \((\leq, \mathrm{REA})\) with the Turing degrees as universe, none of the classes of RE degrees, arithmetic degrees, or ANR degrees is definable by a \(\Sigma_1\) or \(\Pi_1\) formula. The jump operation is definable in that language by a \(\Pi_1\) formula but not by a \(\Sigma_1\) formula. Even with a parameter \(c\) added to the language, neither AR nor the hyperimmune-free degrees are definable by a \(\Sigma_1\) formula. The arithmetic degrees are neither \(\Sigma_1\) nor \(\Pi_1\) definable in the language \((\leq, \mathrm{jump})\) and are neither \(\Sigma_2\) nor \(\Pi_2\) definable in the language \((\leq)\). Neither the ANR degrees nor the hyperimmune degrees are definable by a \(\Sigma_1\) formula in the language \((\leq, c)\) nor by a \(\Sigma_0\) formula in \((\leq, \mathrm{jump}, c)\). The \(\Sigma_1\) theory of degrees in \((\leq, \mathrm{REA})\) is decidable.NEWLINENEWLINESeveral open questions are cited. Can the hyperimmune degrees be defined by a \(\Sigma_1\) formula in \((\leq, \mathrm{REA})\)? Which degrees \(> 0'\) are jumps of hyperimmune-free degrees? If we replace REA in the language by the broader relation of relative recursive enumerability, which analogues of the paper's results still hold?