Abstract

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