Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Here is an example: We use the nonstandard method outlined by Kaye in order to prove the infinitude of primes.

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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