Verification: Translating a mathematical problem into symbolic logic

Question

May you tell me if my translation to symbolic logic is correct?

Thank you so much! Here is the problem:

To check that a given integer $n > 1$ is a prime, prove that it is enough to show that $n$ is not divisible by any prime $p$ with $p \le \sqrt{n}$.

$$\forall p \in P ~\forall n \in N ~(p \nmid n \land p\le \sqrt{n} \land n>1 \rightarrow n \in P )$$

Answer 1

I would put the quantifier for the $p$ on the inside, since that is much more readable. Also when it says ít is not divisible by any prime $p$', they mean: there is not some prime $p$ bla bla bla...

So:

$$\forall n \in N ((\neg \exists p \in P (p \mid n \land p\le \sqrt{n}) \land n>1) \rightarrow n \in P )$$

You could bring the quantifier out, but it would become a lot less readable. Here is what would happen:

$$\forall n \in N ((\neg \exists p \in P (p \mid n \land p\le \sqrt{n}) \land n>1) \rightarrow n \in P ) \Leftrightarrow$$

$$\forall n \in N ((\forall p \in P \neg (p \mid n \land p\le \sqrt{n}) \land n>1) \rightarrow n \in P ) \Leftrightarrow$$

$$\forall n \in N (\forall p \in P (\neg (p \mid n \land p\le \sqrt{n}) \land n>1) \rightarrow n \in P ) \Leftrightarrow$$

$$\forall n \in N \exists p \in P (\neg (p \mid n \land p\le \sqrt{n}) \land n>1) \rightarrow n \in P )$$

As you can see, the only reason the quantifier 'stayed' what it was is because it first changed by bringing it outside the negation, and later it changed again by bringing it outside the conditional of which it was the antecedent. Indeed, in the end, this resulting statement is hardly comprehensible, so I would leave it inside right where it was.

Moreover, to be more inline with the text of this exercise, I would do:

$$\forall n \in N (n > 1 \rightarrow (\neg \exists p \in P (p \mid n \land p\le \sqrt{n}) \rightarrow n \in P ))$$

And finally, notice that for any $n > 1$, n is a prime if and only if it there is no prime $p \leq \sqrt{x}$ that divides $n$, so:

$$\forall n \in N (n > 1 \rightarrow (\neg \exists p \in P (p \mid n \land p\le \sqrt{n}) \leftrightarrow n \in P ))$$

Or even more readable:

$$\forall n \in N (n > 1 \rightarrow (n \in P \leftrightarrow \neg \exists p \in P (p \mid n \land p\le \sqrt{n}) ))$$

In fact, now that you have a quantifier on one side of a biconditional, trying to get it out will be seven more messy and, in the end, incomprehensible. Leave it in!

Answer 2

No, it is not correct, because your formula reads: "for all prime numbers $p$ and for all natural numbers $n$ the following is true: if $p \nmid n$ and $p \le \sqrt n$ and $n >1$ then $n$ is prime", which is obviously false (just take $p=2$ and $n=9$).

I suggest the following:

$$\forall n \in \Bbb N \Bigg( \Big( \exists p \in P \ \big( (p \mid n) \land (p \le \sqrt n) \land (n > 1) \big) \Big) \to n \notin P \Bigg) .$$

In plain language: "for all natural numbers $n$ the following is true: if there exist a prime number $p$ such that $p \mid n$ and $p \le \sqrt n$ and if $n > 1$, then $n$ is not prime".