Translating statement into predicate logic

Question

P(x,y) = def "x divides y"

Statement: "There is no largest prime number"

UoD: Z+

How do we translate this into logic?

I'm thinking between these two options:

$$∀x∃y[y>x \land ∀z(P(z,y) → ( z=1 \lor z=y))]$$

$$∀x∃y[y>x \land ∀z(( z=1 \lor z=y) → P(z,y))]$$

Answer 1

Definitely not the second statement: that one says that 1 and y divide y … which is true for any number, not just prime numbers.

The first one is right: it says that the only two numbers dividing y are 1 and y itself…. and that indeed makes y a prime number (and we don’t have to worry about y being 1, since the domain is positive integers, and so if the y is greater than x, we already have that y is greater than 1

Answer 2

Consider the statement $\forall z((z = 1 \lor z = y) \to P(z, y))$. Note that in general, $(A \lor B) \to C$ is logically equivalent to $(A \to C) \land (B \to C)$. So we can rewrite $(z = 1 \lor z = y) \to P(z, y)$ as $(z = 1 \to P(z, y)) \land (z = y) \to P(z, y))$.

Now in general, $\forall z (Q(z) \land R(z))$ is logically equivalent to $\forall z Q(z) \land \forall z R(z)$. So we can rewrite $\forall z ((z = 1 \to P(z, y)) \land (z = y \to P(z, y))$ as $\forall z (z = 1 \to P(z, y)) \land \forall z (z = y \to P(z, y))$.

Now in general, $\forall x (x = w \to Q(x))$ is logically equivalent to $Q(w)$. So we can rewrite $\forall z (z = 1 \to P(z, y))$ as $P(1, y)$, and we can rewrite $\forall z (z = y \to P(z, y))$ as $P(y, y)$.

So the statement is logically equivalent to $P(1, y) \land P(y, y)$. Note that both $P(1, y)$ and $P(y, y)$ are always true.

So the statement $\forall x \exists y (y > x \land \forall z((z = 1 \lor z = y) \to P(z, y)))$ is logically equivalent to $\forall x \exists y (y > x)$. This is trivial.

By contrast, note that the statement "$w$ is prime" can be expressed as $w \neq 1 \land \forall z (P(z, w) \to z = 1 \lor z = w))$. So the first definition is logically equivalent to saying there are arbitrarily large primes.