Prove that divisibility between two natural numbers is not definable in arithmetic

Question

Prove that there is no formula $\varphi(v,u)$ so that $(\mathbb N; 0, 1, +) \models \varphi[x,y]$ iff $x$ divides $y$.

Here is what I have so far: assume on the contrary that we do have such $\varphi$. Then my class has proven during class that $(\mathbb N; 0,1,+,<,\text{div}_1,\text{div}_2,\dots)$ admits a quantifier elimination, where $\text{div}_k(a)$ iff $k$ divides $a$. Thus, by our assumption, we have that $(\mathbb N; 0, 1, +, <)$ admits a quantifier elimination. If we can show a formula in $(\mathbb N; 0, 1, +, <)$ that does not admit a quantifier elimination, we will be done.

My friend was also suggesting that we could instead try to extend our model to $\mathbb Z$ and consider what's called a Presburger arithmetic; however, I am not sure how that would go about.

I would be grateful for your guidance.

Answer 1

We can do this by showing that the resulting theory is Peano Arithmetic and thus incomplete, while Presburger Arithmetic is complete.

We'll do this by showing that we can define multiplication if we are given access to a divisibility predicate. We can do this because we can express the concept of the square of one number dividing another. We can square numbers because $x(x+1) = \text{LCM}(x, x+1)$ and that gives us enough to get the ball rolling.

Let $L(x, y, z)$ be the relation LCM. It is defined as follows:

$L(x, y, z)$ is $(x\mid z) \land (y \mid z) \land [\forall k]((x \mid k) \land (y \mid k) \to (z \mid k))$

Let $G(x, y, z)$ be the relation GCD. It is defined as follows:

$G(x, y, z)$ is $z \mid x \land z \mid y \land [\forall k](k \mid x \land k \mid y \to z \mid k)$

Let $x \mid^2 y$ be the relation "divides twice". It is defined as follows:

$x \mid^2 y$ is defined as $[\exists k](L(x, x+ 1, x+k) \land (k \mid y))$

Let $R(x, y, z)$ be the product relation.

The product of $x$ and $y$ is the least multiple of the least common multiple such that $\text{GCD}(x, y)$ divides it twice.

It is defined as the conjunction of the following.

1. $(x \mid z)$
2. $(y \mid z)$
3. $[\exists k](G(x, y, k) \land k \mid^2 z)$
4. $[\forall w](x \mid w \land y \mid w \land [\exists k](G(x, y, k) \land k \mid^2 w) \to w \mid z) $

This shows that multiplication is definable.

Therefore, Presburger Arithmetic + divisibility is equivalent to Peano Arithmetic and thus incomplete. However, Presburger Arithmetic is complete, which is a contradiction.