The \(n\)-r.e. degrees: undecidability and \(\Sigma_1\) substructures (Q2909622)

A recursive function \(f(x,s)\) approximates the set \(A\) if for all \(x\), \(f(x,0)=0\), \(\lim_s f(x,s) \in \{0,1\}\), and \(\lim_s f(x,s) = 1\) if and only if \(x \in A\). The \(n\)-r.e.~sets are those which have a recursive approximation with at most \(n\) changes of value for each \(x\). Thus, the \(1\)-r.e.~sets are the familiar recursively enumerable sets. The \(n\)-r.e.~sets are also called \(n\)-c.e.~in the literature, and arise from the \(n\)-trial predicates of \textit{H. Putnam} [``Trial and error predicates and the solution to a problem of Mostowski'', J. Symb. Log. 30, 49--57 (1965; Zbl 0193.30102)]. This paper addresses the global properties of \(\mathcal D_n\), the Turing degrees of the \(n\)-r.e.~sets, showing that the structure of each \(\mathcal D_n\) is very complicated. In particular, the authors prove (1) for every \(n\) the theory of \(\mathcal D_n\) is undecidable, and (2) if \(n<m\) then \(\mathcal D_n\) is not a \(\Sigma_1\)-substructure of \(\mathcal D_m\).