Write formally: The biggest prime number does not exist. Assume that all variables are positive integers.

This is my attempt to solve this problem.

Let $\pi(x) = \mbox{x is prime}$. Then, $$\pi(x) = (\forall a)(a|x \Rightarrow (a=1 \lor a=x)) \land x \ne 1$$ And so, the solution will be: $$(\forall p)(\pi(p)) (\exists P)(\pi(P) \land P > p)$$
What do you think of this solution? Is it good?

  • $\begingroup$ It is okay. But if you want to be pedantic, you should actually use the existence quantifier. $\endgroup$ – user251257 Nov 24 '17 at 23:45
  • $\begingroup$ Where? And why? $\endgroup$ – Aemilius Nov 24 '17 at 23:46
  • 1
    $\begingroup$ I meant: $\lnot \exists p (\pi(p) \land \forall \tilde p (\pi(\tilde p) \implies \tilde p \le p)$. It is just being pedantic only. Because you have applied some (equivalent) reformulation already. $\endgroup$ – user251257 Nov 24 '17 at 23:49
  • 1
    $\begingroup$ Is $(\forall p)(A)(\exists P)(B)$ a well-formed formula? Should it rather be $(\forall p)(A\rightarrow ((\exists P)B)$ or similar? $\endgroup$ – ziggurism Nov 24 '17 at 23:58
  • 1
    $\begingroup$ Your formulation lacks an implication: for every $p$, if $p$ is prime, then there exists $P$... Alternatively, drop $\pi(p)$ altogether: for all $p$ there exists a larger $P$ that is prime. $\endgroup$ – Fabio Somenzi Nov 25 '17 at 0:00

(A) Your suggested solution is not a well-formed formula. You mean, I think,

$$(\forall p)[\pi(p) \to (\exists q)(\pi(q) \land q > p)]$$

which says, assuming you are quantifying over numbers, for any number, if it is prime, there exists a number which is prime and bigger than it. You missed the crucial conditional. (Also, don't mix lower case and upper case variables when the same type of variable is in question -- in fact, the syntax of your language will normally fix that the first-order variables are all lower case.)

(B) But even corrected, this is strictly speaking at best a translation of "for any prime, there is a larger one", not of "the biggest prime doesn't exist". Those two claims are logically equivalent --- but just because claims are equivalent doesn't mean you ought to render them the same way into logical notation. (Compare: "snow is white" and "it isn't the case that it isn't the case that snow is white" are equivalent -- it doesn't mean that you should render them the same way!)

Standardly we translate existence claims using the existential quantifier (the clue is in the name), and so negations of existence claims with a negated existential quantifier. So we really want a translation starting '$\neg(\exists p)$'.

This, then, is better:

$$\neg(\exists p)[\pi(p) \land (\forall q)(q > p \to \neg\pi(q))]$$

There doesn't exist a prime number such that any number larger than it is not prime.

(C) A bonus exercise: in your favourite proof system for FOL, show those two wffs are inter-derivable!


What I'm getting at is that they want you to prove that there are an infinite number of primes. We can simply prove this using Euclid's theorem which is a proof by contradiction and it goes like this:

Assume a finite amount of primes: $P_1, P_2, P_3 ..., P_n$

Now lets multiply all of the primes together, we get: $P_1 \cdot P_2 \cdot P_3... \cdot P_n$

If we add $1$ to this product, we get a number that is not divisible by any of the factors which we assumed to be the entirety of the prime numbers. Thus we can conclude that $P_1 \cdot P_2 \cdot P_3... \cdot P_n + 1$ is also a prime number. This goes against the initial notion that we had already multiplied all the prime numbers together. We have reached a contradiction, therefore there can't be a finite amount of prime numbers; there is no greatest prime.

  • 2
    $\begingroup$ I think "write formally" just means "translate into standard first-order notation" (with an appropriate translation key). $\endgroup$ – Peter Smith Nov 25 '17 at 0:06
  • $\begingroup$ @PeterSmith Ohhh that would make sense. Thanks for the clarification. $\endgroup$ – Badr B Nov 25 '17 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.