Let $ be the restriction of usual order relation to integers which are primes or squares of primes, and let ⊥ denote the coprimeness predicate. The elementary theory of $\langle\mathbb{N};\bot, , is undecidable. Now denote by $ the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure $\langle\mathbb{N};\bot, . Furthermore, the structures $\langle\mathbb{N};\mid, and $\langle\mathbb{N};=,+,x\rangle$ are interdefinable.

Let M be a first-order structure; we denote by DEF(M) the set of all first-order definable relations and functions within M. Let π be any one-to-one function from N into the set of prime integers. Let ∣ and $\bullet$ be respectively the divisibility relation and multiplication as function. We show that the sets DEF(N,π,∣) and $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ are equal. However there exists function π such that the set DEF(N,π,∣), or, equivalently, $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ is not equal to $\mathrm{DEF}(\mathbb{N},+,\bullet)$ . Nevertheless, in all cases (...) there is an $\{\pi,\bullet\}$ -definable and hence also {π,∣}-definable structure over N which is isomorphic to $\langle\mathbb{N},+,\bullet\rangle$ . Hence theories TH(N,π,∣) and $\mathrm{TH}(\mathbb{N},\pi,\bullet)$ are undecidable. The binary relation of equipotence between two positive integers saying that they have equal number of prime divisors is not definable within the divisibility lattice over positive integers. We prove it first by comparing the lower bound of the computational complexity of the additive theory of positive integers and of the upper bound of the computational complexity of the theory of the mentioned lattice. The last section provides a self-contained alternative proof of this latter result based on a decision method linked to an elimination of quantifiers via specific tables. (shrink)

In this paper we give a positive answer to Julia Robinson's question whether the definability of + and · from S and ∣ that she proved in the case of positive integers is extendible to arbitrary integers (cf. [JR, p. 102]).

Using coding devices based on a theorem due to Zsigmondy, Birkhoff and Vandiver, we first define in terms of successor S and coprimeness predicate $\perp$ a full arithmetic over the set of powers of some fixed prime, then we define in the same terms a restriction of the exponentiation. Hence we prove the main result insuring that all arithmetical relations and functions over prime powers and their opposite are $\{S, \perp\}$ -definable over Z. Applications to definability over Z and N (...) are stated as corollaries of the main theorem. (shrink)