A nonstandard proof

We’re going to use a nonstandard model of the real numbers to make this work. The construction is a bit wacky: Take a non-principal ultrapower of \mathbb R. Call this the hyperreals. Here’s another way to put it:

A hypernumber a sequence of regular numbers (a_1,a_2,\dots). To make decisions about hypernumbers, we put it to a vote:

Is it true that (3,0,0,\dots)=(0,0,0,\dots)? Well, the first position votes no, because 0\ne 3. The rest of them all vote yes, however, so the vote is infinity to one. They’re equal. Wackier things such as (0,1,0,1,\dots) we wont get into. If you’re interested, look here. (The basic idea is that the ultrafilter decides whether the evens or the odds win in the vote. The ultrafilter always decides which sets are more important. The fact that its non-principal implies that it prefers cofinite  sets to finite ones).

It’s easy to see that the standard real numbers are embedded as hyperreal numbers. If you have a real number x, then (x,x,\dots) is the standard real number embedded in the hyperreals as a hypernumber.

Nonstandard models are fun because now we really do have “infinitesimal numbers.” The hypernumber (1,\frac12,\frac13,\dots) is smaller than every standard positive number (x,x,x,\dots), but its still bigger than (0,0,0,\dots). We can also have infinite numbers (1,2,3,\dots), and even larger infinite numbers (2,3,4,\dots).

Lots of things you can do in the hyperreals are essentially the same in the standard real numbers. Some people call this the “transfer principle.” I never liked that name. All it says is that, in model theoretic terms, the standard real numbers and the hyperreals are “first-order equivalent.” That is, they have the same first order theories. This means that anything you can write down using quantifiers \forall and \exists, where you only quantify over elements (not subsets of elements) is true in one model if and only if it is true in the other.

Anyway, enough logic. Let P be the set of hyperprimes. These are the hypernatural numbers which aren’t hyperdivisible by any hypernatural numbers other than hyper-one and themselves. That sentence was fun.

Let N=(1!,2!,3!,\dots). Note that N is hyperdivisible by every standard natural number. This means that N!+1=(1!+1,2!+1,3!+1,\dots) cannot be divisible by any standard prime. But there does have to be some hyperprime dividing any hypernumber. This is because every standard natural number is divisible by a standard prime. Since divisibility is a first-order property, there must be a hyperprime hyperdividing any hypernatural number. This tells us that P, the set of hyperprimes, contains some nonstandard element.

Now I just want to argue why a set which contains nonstandard elements must have its standard counterpart be infinite. The idea is that, if it were finite, I could define the set by saying n is in P if and only if n=p_1 or n=p_2 or … or n=p_k. I can’t do this if P is infinite, because the sentences I write down must be finite. Then, when I transfer this set to the hyperreal numbers, if it were finite, it would satisfy this property in the hyperreals too. Thus, in the hyperreals, it would only contain the same standard elements.

The fact that P contains a nonstandard hyperprime tells us that there must be infinitely many primes. I left out many details, but hopefully the sketch gives you a reasonable idea of what is going on.

At some level, this is no different from Euclid’s proof, but it just seems so much more badass. I mean, we used the axiom of choice (to construct the non-principal ultrafilter) in a number theory proof. That is decidedly awesome.