0

I have to formalize the following mathematical statement in a predicate logic in a language L = {+, *, 0, 1, <} :

"There are infinitely many prime numbers"

I have found the following formalization but it is not clear to me why there is a necesity to embed another variable $d$ inside the formula. Formalization is the following:

$(\forall x)(\exists y)[x < y \land (\forall d)((\exists p)(p * d = y)\rightarrow (d = 1 \vee d = y))]$

Is it possible to write instead this? If not, why?:

$(\forall x)(\exists y)[x < y \land ((\exists p)(p * x = y)\rightarrow (x = 1 \vee x = y))]$

TKN
  • 757
  • 1
    Start formalizing the property "$n$ is prime". – Mauro ALLEGRANZA Feb 03 '20 at 13:32
  • Well I know that I can formalize the property "n is prime" the following way: $(\forall d)((\exists p)(p*d = y)\rightarrow (d=y \vee d=1))$ . Is that correct? – TKN Feb 03 '20 at 13:36
  • I would like to know especially, if I can write this: $(\forall x)(\exists y)[x < y \land ((\exists p)(p * x = y)\rightarrow (x = 1 \vee x = y))]$ instead of this: $(\forall x)(\exists y)[x < y \land (\forall d)((\exists p)(p * d = y)\rightarrow (d = 1 \vee d = y))]$ . If not, why? – TKN Feb 03 '20 at 16:03
  • 1
    IMO, what you are trying to write is $\forall x \exists y (x < y \land \text {Prime}(y))$. – Mauro ALLEGRANZA Feb 03 '20 at 16:12
  • If,so, you have to replace the predicate $\text {Prime}(y)$ with the formula : $\forall n,m (y=n \cdot m \to (n=1 \lor n=y))$. – Mauro ALLEGRANZA Feb 03 '20 at 16:14
  • Is there a way to explain, why we have to create another variable $d$ instead of using already used variable $x$? Both variables have the quantifier $\forall$ and therefore it seems to me that it is not necessary to create another variable $d$ and instead I could use $x$. – TKN Feb 03 '20 at 16:41

0 Answers0