Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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. –  Andres 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. –  Andres 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$. –  Andres 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.) –  Andres Caicedo Aug 2 '13 at 14:46

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.