\(\Sigma^ n_ 0\)-equivalence relations (Q793716)

This paper deals with the reducibility pre-order \(\leq_ m\) ranging over equivalence relations on the set of natural numbers, where \({\mathcal R}\leq_ m{\mathcal S}\) if there exists a recursive function f such that, for all x, y: x \({\mathcal R} y\) if and only if f(x) \({\mathcal S} f(y)\). For \(n\geq 1\), \(\Sigma^ 0_ n\)-precomplete equivalence relations are introduced (generalizing a notion due to Ershov). It is shown that every \(\Sigma^ 0_ n\)-precomplete \(\Sigma^ 0_ n\)-equivalence relation is complete with respect of \(\leq_ m\) restricted to \(\Sigma^ 0_ n\)-equivalence relations. Several additional features of \(\Sigma^ 0_ n\)-precomplete equivalence relations are discussed. A representation theorem is also proved: Let T be an r.e. consistent theory which satisfies specific requirements (e.g. T is Peano arithmetic) and for \(n\geq 1\) let \(T^ n\) denote the theory obtained by adding as axioms all \(\Pi_{n-1}\) true sentences; then for every \(\Sigma^ 0_ n\)-equivalence relation \({\mathcal R}\) there is a \(\Sigma_ n\) formula F of T such that for all x, y: x \({\mathcal R} y\) iff \(T^ n\vdash F(\bar x)\leftrightarrow F(\bar y).\)