Is there an non provable sentence from Peano Arithmetic?

Question

I'm trying to deduce the following sentence using only Peano Axioms:

"There exist infinite prime numbers"

Since PA is known to be incomplete, its possible there is no such proof supporting the sentence from PA's axioms.

How can I tell if the sentence is indeed unprovable?

Answer 1

The proof of Euclid's theorem asserting that there are infinitely many prime numbers is proved from first-order Peano axioms into :

• S.C.Kleene, Introduction to Metamathematics (1952) , *161, page 191-92.

Here is a sketch of the proof.

Definitions [page 191]:

i) $a|b$ [read $a$ divides $b$] is an abbreviation for : $\exists c \ (a \times c = b)$.

ii) $Pr(a)$ [read "$a$ is prime"] is : $a > 1 \land \lnot \exists c \ ( 1 < c < a \land c|a)$.

Using them, Euclid's theorem is :

$\exists b \ (Pr(b) \land b > a)$ ["for any number $a$, there is a prime greater than $a$"].

The result needs a preliminary Lemma [page 192]:

*157. $\exists d \ [d > 0 \land \forall b \ (0 < b \le a) \to b|d)]$ (Existence of common multiples of $1, \ldots, a$.)

The proof of the Lemma is by induction on $a$ : it is needed because in the system there is no term to express the function $a!$.