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

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.