All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate (Q2266708)

The study of representability in arithmetic goes back to Gödel who showed in 1931 that the exponential function can be first-order defined in the structure \(<{\mathbb{N}},+,\circ,=>\) where \({\mathbb{N}}\) denotes the set of non-negative integers; he actually proved that inductive definitions - which in fact are not first order definitions but second-order definitions - can be translated as first-order formulas of the language \(\{+,\circ,=\}.\) A natural problem related to Gödel's result is to determine families of arithmetical relations and functions from which \(+\), \(\circ\) and \(=\) are first-order definable; such families will be called synonymous with \(\{+,\circ,=\}\). Robinson (1949) showed that \(\{\) S,\(| \}\) (where \(|\) stands for the divisibility relation) is synonymous with \(\{+,\circ,=\}\). She asked whether \(\{+,\perp \}\), and \(\{\) S,\(\perp \}\) are synonymous (where \(\perp\) stands for the relation of coprimeness, i.e. \(\{(x,y)\in {\mathbb{N}}^ 2|\) x and y are relatively prime\(\})\). The synonymy of \(\{+,\circ,=\}\) with \(\{+,\perp \}\) has been proved independently by Robinson (unpublished), \textit{A. Woods} [Thesis, Univ. Manchester (1981)] and the author. The synonymy of \(\{+,\circ,=\}\) and \(\{\) S,\(\perp \}\) is still open. The interest of this last problem has been emphasized by Wood's thesis, where it is demonstrated that the synonymy of \(\{+,\circ,=\}\) and \(\{\) S,\(\perp \}\) is equivalent to the following conjecture: Is there an integer k such that, for all x and y, the equality \(x=y\) holds if and only if \((x+i)\) and \((y+i)\) have the same prime divisors for \(i=0,1,2,...,k.\) Woods also proved in this thesis that \(\{\leq,\perp \}\) is synonymous with \(\{+,\circ,=\}\); we have shown that \(\{EXP_ p,S,\perp \}\) (where \(EXP_ p\) denotes the function \(x\mapsto p^ x\) for any fixed prime p) is also synonymous with \(\{+,\circ,=\}.\) We show in this paper that all recursive relations and functions over the set of powers of primes are \(\{\) S,\(\perp \}\)-definable in \({\mathbb{N}}\); in particular, this is true for the restriction to that set of the order relation and of the exponentiation \((x,y)\mapsto x^ y\). The techniques used are coding devices based on \(\alpha)\) the existence of prime(s) dividing \(x^ n-1\) (resp. \(x^ n+1)\) but no \(x^ m-1\) (resp. \(x^ m+1)\) for \(0<m<n\) (result due to Zsigmondy (1892) and Birkhoff-Vandiver (1904)); \(\beta)\) the existence of prime solutions of certain congruence systems (a result combining the chinese remainders theorem and Dirichlet's theorem). This permits to develop a sort of finite set theory over the structure \(<{\mathbb{N}},S,\perp >\). Device \(\alpha)\) gives convenient codes for finite subsets of \({\mathbb{N}}\) and device \(\beta)\) provides sorts of choice functions.