What’s wrong with this proof that $5$ is prime?

Question

I’m reading How To Prove It and I’m confused as to how the proof of “$x$ is prime” is correct.

I've written proof given below and also my conclusion after substituting in values for $x$, $y$ and $z$:

$5$ is prime. We have $$\stackrel{(x)}{5} = \stackrel{(y)}{1} \times \stackrel{(z)}{5}.$$ Logical form of $x$ is prime: $$x > 1 \land \lnot \exists y\,\exists z\left(x=yz \land y < x \land z < x\right)$$ Plugging in values for $x$, $y$ and $z$: $$5 > 1 \land \lnot \exists1\,\exists 5 \left(5=1\times 5 \land 1 < 5 \land \boldsymbol{5 < 1}\right)$$ But $5<1$ is false.

My conclusion is that $5 < 1$ is false. What’s wrong?

Answer 1

When you want to prove $\neg \exists y\, (\cdots)$, you can't just pick one value for $y$ and plug that in. That's how you prove $\exists y\, (\cdots)$, but the negation changes everything.

What you need to prove is that one can't pick any value for $y$ that makes the "$(\cdots)$" true, or in other words that every possible value for $y$ makes the "$(\cdots)$" false.

What you show here is just that there is one value for $y$ (and $z$) that makes the rest false -- not that every other value makes it false too.

---

Concretely, you want to prove $$\neg\exists y\exists z\,(5=yz \land y < 5 \land z < 5)$$ which is the same as $$\forall y \forall z \, \neg(5=yz \land y < 5 \land z < 5)$$ which is the same as $$\forall y \forall z \, (5\ne yz \lor y \ge 5 \lor z \ge 5)$$

Answer 2

Not quite correct. You cannot just plug in two values for $y$ and $z$ and conclude the proof. You need to go through all combinations of possible $y$ and $z$.

Now, a positive integer $x$ is prime if and only if whenever $x$ is expressed as a product of positive integers: $x=yz$, one of $y$ and $z$ must equal $x$. (You can tweak this definition to admit negative primes and negative $y$ and $z$ if your wish.) This is the same as what your wrote, but turned on its head.

Since one of your requirements is here that $1<y<5$ and $1<z<5$, there are 3 possibilities for each: 2, 3 and 4. Checking these products, we see that none equal 5. Therefore 5 is prime.

Let me throw in a caution. In writing mathematics, you should strive for readability. Expressing properties as long strings of logical symbols is not a very good way to write mathematics, since it requires considerably greater effort to read.

Answer 3

The meaning of your logical form is that, any prime means a natural number greater than one AND it cannot be expressed as a product of two numbers which are less than itself. For example, in your case, 5 is prime since 5>1 AND the only product of two numbers equal to 5 that you can find out is $5*1$. In other words, if $5=xy$, then $x\ge 5$ or $y\ge5$.