First order logic for proving a prime number

623 Views Asked by At

The first order logic representation from a solution that I saw for showing that a positive $x$ is prime is

$$ \forall x \ \operatorname{prime}(x) \iff \forall y,z \ \ x = y*z \implies y = 1 \ \lor z = 1 $$

I don't think this is entirely correct because it doesn't account for x=1. A $z \neq y$ is needed.

My other question is could ($\forall y,z \ \ x = y*z \implies y = 1 \ \lor z = 1$) be written as $$ \forall y,z \ \ x = y*z \land (y = 1 \ \lor z = 1) $$ This seems to also work, but I'm not very experienced with logic representation.

1

There are 1 best solutions below

5
On BEST ANSWER

First of all, I presume that all numbers here are natural numbers, i.e. it's assumed that all $x,y,z\in\mathbb{N}$.

(1) You're right: this condition does make $x=1$ "prime", which it isn't. Something is missing here and needs to be corrected. We can't just require, though, that $x\ne y$, because it could be that $y=x$ and $z=1$. We need to be a little more careful and require that either $y$ or $z$ isn't equal to $x$. Another solution could be to specifically exclude $x=1$ by literally saying that $x\ne1$. So we can do things like: $$\forall x \; \operatorname{prime}(x) \iff (x\ne1) \land (\forall y,z : [x=y\cdot z \implies y=1 \lor z=1])$$ or $$\forall x \; \operatorname{prime}(x) \iff \forall y,z : [x = y\cdot z \implies (y=1 \lor z=1) \land (y\ne x \lor z\ne x)]$$ (although the latter can be simplified, I guess).

(2) Your proposed definition doesn't work. You're saying that for any two integers $y$ and $z$, the previously chosen number $x$ is their product, $x=y\cdot z$, which can't be true. For example, imagine $x=10$. That definition says that $10=y\cdot z$ for any two integers $y$ and $z$