# Non-standard proofs of standard theorems

In Richard Kaye's book Models of Peano arithmetic, one can read (page 13):

We have proved that any nonstandard $M \models \mathrm{Th}(\mathbb{N})$ has a nonstandard $a \in M \models \theta(a)$ iff there are infinitely many $k \in \mathbb{N}$ satisfying $\mathbb{N} \models \theta(\underline{k})$. This observation is the basis of many elegant "non-standard" proofs of theorems about $\mathbb{N}$.

where $\theta(x)$ is a formula over the language $\mathcal{L}_A= \{0,1,+,\times ,<\}$ with only one free-variable $x$.

Do you know such elegant proofs?

-
Kaye's book also presents several examples. Recently, nonstandard techniques along these lines have been used by Tao and his collaborators in additive combinatorics. – Andrés E. Caicedo Aug 2 '13 at 14:04
(There was an inaccuracy in the previous version of this comment.) The unprovability in $\mathsf{PA}$ of the Paris-Harrington theorem is an example. In general, most independence results that can be established by the method of indicators. Other examples of such independent statements are that Hercules wins all Hercules-Hydra games, or the termination of Goodstein sequences. – Andrés E. Caicedo Aug 2 '13 at 14:39
Most introductory texts in non-standard analysis will also have examples, though some may only give examples in the context of $\mathbb R$ or similar structures, rather than $\mathbb N$. – Andrés E. Caicedo Aug 2 '13 at 14:40
@AndresCaicedo The Wikipedia article for Paris Harrington says that it is itself a statement about unprovability of another theorem, the "strengthened Ramnsey theorem." Do you really mean that the above is used to show that "(SRT is true but unprovable) is unprovable." Or is the Wikipedia page wrong? – Thomas Andrews Aug 2 '13 at 14:43
(@ThomasAndrews I meant the unprovability of the strengthened Ramsey theorem.) – Andrés E. Caicedo Aug 2 '13 at 14:46

Let $M$ be a model of $\text{Th}(\mathbb{N})$ containing an element $a$ which is divisible by every standard number $n \in \mathbb{N}$. (Use compactness to show that such a model $M$ indeed exists.) Now, $a+1$ cannot be divisible by any standard number $n>1$ but there must be a prime $p$ dividing $a$. It follows that $p$ is a nonstandard prime and this implies the infinitude of primes.