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?

Solution 1:

Here is an example although it is more a theorem about $\mathbb{Z}$ than about $\mathbb{N}$. However, it uses the overspill principle for nonstandard models of $\mathbb{Z}$ which is essentially the same as for $\mathbb{N}$. So, I hope it counts.

I show that for any irreducible polynomial $f \in \mathbb{Q}[X]$ with integer coefficients, there are infinitely many primes $p$ such that $f$ splits completely in $\mathbb{Z}/p\mathbb{Z}$. Let $n$ be the degree of $f$ and let $K$ be the splitting field for $f$ over $\mathbb{Q}$. Note that we can write $K=\mathbb{Q}(a_1,...,a_n)$ where $f=(X-a_1)...(X-a_n)$. So, the $a_i$ are all the roots and they must be distinct. (Remember that all irreducible polynomials from $\mathbb{Q}$ are separable.) Choose a primitive Element $b \in K$ so that we can write $K=\mathbb{Q}(b)$. Let $g$ be the minimal polynomial for $b$. We can assume that $g$ has integer coefficients. Now, let $M$ be a nonstandard model for $\mathbb{Z}$ in the language of rings. There is a well-known theorem stating that $g$ has a root modulo $p$ for infinitely many primes $p \in \mathbb{Z}$. Since the statement "$g$ has a root modulo $p$ and $p$ is prime" can be expressed by a first-order formula in the language of rings, it follows by overspill that $g$ has a root modulo a nonstandard prime $p \in M$. So, $g$ has a root in the field $M/pM$. Since $M/pM$ has characteristic $0$, it contains an isomorphic copy of $\mathbb{Q}(b)$. It follows that $f$ splits completely in $M/pM$ and has $n$ distinct roots there. Let $\theta(p)$ be a first order formula stating that $f$ has $n$ distinct roots modulo $p$ and that $p$ is a prime. Then $M \vDash \theta(p)$. Since $p$ is non-standard, underspill gives us the desired result.

There is an easy generalization: You can prove the statement also for finitely many irreducible polynomials $f_1,...,f_n$ from $\mathbb{Q}[X]$ with integer coefficients. The proof is essentially the same as above. Just use the splitting field for the product $\prod_i f_i$.