A note on definability in fragments of arithmetic with free unary predicates (Q365661)

For a signature \(\sigma\), a \(\Pi^1_n\)-\(\sigma\)-formula is a second-order \(\sigma\)-formula of the form \(\forall X_1\exists X_2\dots\varphi\) with \(n-1\) alternating quantifiers, where all second-order variables are unary, and \(\varphi\) has no second-order quantifiers. The paper presents several results on \(\Pi^1_n\)-\(\sigma\) definability over the set of natural numbers \(\omega\), where \(\sigma\) is one of \(\{+\}\), \(\{\times\}\), \(\{+,\times\}\). \textit{J. Y. Halpern} [J. Symb. Log. 56, No. 2, 637--642 (1991; Zbl 0738.03017)] proved that the set of \(\Pi^1_1\)-\(\{+\}\) sentences true in \((\omega,+)\) is \(\Pi^1_1\)-complete. The main result of the paper is a direct proof of Halpern's result with some generalizations. The author shows that there is a \(\{+,U\}\)-sentence \(\Psi\), such that for any expansion \(B=(\omega,+,U^B)\), \(B\models\Psi\) iff \(\Psi_\times\) defines multiplication in \(B\), where \(\Psi_\times\) is a \(\{+,U\}\)-formula defining multiplication in \((\omega, +,\{n^2:n\in\omega\})\). This is used to prove that there is an effective translation from \(\Pi^1_n\)-\(\{+,\times\}\)-formulas to \(\Pi^1_n\)-\(\{+\}\)-formulas and this allows him to show that the set of \(\Pi^1_n\)-\(\{+\}\) sentences true in \((\omega, +)\) is \(\Pi^1_n\)-complete and that each \(\Pi^1_n\)-set is definable by a \(\Pi^1_n\)-\(\{+\}\)-formula. There are also analogous results concerning \(\Pi^1_n\)-\(\{\times\}\) completeness and definability in \((\omega, \times)\). One of the corollaries is that there are no unary predicates \(P_1,\dots, P_n\) such that \(+\) is definable in \((\omega, s, P_1,\dots, P_n)\), where \(s\) is the successor function. The paper includes a list of interesting open problems.