Infinitely Large Primes (Ultra Series 5)

Previous: Ultraproducts and Łoś’s Theorem

Let’s quickly review what we’ve learned so far.

The hypernaturals, *ℕ, are the ultrapower of ℕ with index set I = ℕ. The first-order language in use here is the language of Peano arithmetic: L = <{0}, {<}, {S,+,⋅}>. Łoś’s theorem from the last post tells us that *ℕ and ℕ are elementarily equivalent. In other words:

For every first-order sentence φ, ℕ ⊨ φ if and only if *ℕ ⊨ φ.

This tells us that *ℕ is not just a model of Peano arithmetic, which is a popular incomplete theory of arithmetic. It’s a model of TRUE arithmetic, the complete set of all first-order truths of arithmetic! Given the insane uncomputability of this theory (If T₀ is a Turing machine, and T_n+1 is a Turing machine with an oracle for T_n‘s halting problem, then true arithmetic is not computable by T_n for any finite n), it’s pretty remarkable that we have an explicit example of one of its nonstandard models!

Review over! Now let’s begin with some basic applications of Łoś’s theorem. We can say that a number x is prime in first-order logic: isPrime(x) can be translated as ∀y ∀z (y⋅z = x → (y = 1 ∨ z = 1)). We can also refer to any finite natural number by applying the successor function enough times to zero (e.g. 2 = S(S(0))). Since “2 is a prime” is first-order expressible and ℕ affirms its truth, so must *ℕ.

But remember that in *ℕ, 2 is the equivalence class of the sequence (2,2,2,2,…). Is it really true that for any a, b ∈ *ℕ, if a⋅b = [2,2,2,2,…] then one of a and b is 2 and the other is 1? This is probably not immediately obvious… What about (2,1,2,1,2,1,…)⋅(1,2,1,2,1,2,…)? Certainly this product is (2,2,2,2,…), but neither (2,1,2,1,2,1,…) nor (1,2,1,2,1,2,…) look very much like (1,1,1,1,…) or (2,2,2,2,…).

In fact they are the same. Let’s prove this very generally. Suppose p is any finite prime number, and consider the hypernatural [p, p, p, …], corresponding to the ordinary natural number p. Consider any two hypernaturals a and b such that a⋅b = p. We can choose representative sequences (a₀, a₁, a₂, …) and (b₀, b₁, b₂, …) such that their product is (p, p, p, …). In other words:

(a₀⋅b₀, a₁⋅b₁, a₂⋅b₂, …) = (p, p, p, …)

Since p is prime, we know that for each k, either (a_k = p and b_k = 1) or (a_k = 1 and b_k = p). Consider the set of indices A = { k ∈ ℕ | a_k = p }. Since each a_k is either 1 or p, the complement ℕ\A is equal to { k ∈ ℕ | a_k = 1 }. Now, since U is an ultrafilter, either A or ℕ\A is in U. In the first case, [a₀, a₁, a₂, …] = [p, p, p, …] = p. And in the second case, [a₀, a₁, a₂, …] = [1, 1, 1, …] = 1. The same argument applies for [b₀, b₁, b₂, …]. So for any two hypernaturals a and b such that a⋅b = p, both a and b are either 1 or p.

Okay, so we’ve proven that 2 is a prime number. That’s a relief! Let’s do something a bit more substantial now.

Consider the following first-order sentence: ∀x ∃y (y > x ∧ isPrime(y)). This sentence says that there are infinitely many primes, and (as first proven by Euclid) ℕ affirms its truth. So *ℕ ⊨ ∀x ∃y (y > x ∧ isPrime(y)).

Okay, so there are infinitely many hypernatural primes. This doesn’t sound so exciting… after all every ordinary prime is a hypernatural prime too, so didn’t we already know this? Sure, but if we look closely at what exactly the sentence says, it turns out that we get a bit more out of it than just that.

∀x ∃y (y > x ∧ isPrime(y)) says that for every number x, there’s a larger prime number y. Applying this in *ℕ, this means that all hypernatural numbers, even the infinitely large ones, have larger primes. Thus there are nonstandard primes in *ℕ, and in fact infinitely many nonstandard primes.

See if you can think of one for yourself before reading on.

.

.

.

Ok, here’s one: P = [2, 3, 5, 7, 11, 13, 17, …]. This sequence is eventually always larger than the sequence of any standard prime p = [p, p, p, p, …], so P is a nonstandard number. And P is also prime! The argument is very similar to the previous argument: take any two hypernaturals a and b such that a⋅b = k. Consider any representative sequences for a and b whose product is the sequence (2, 3, 5, 7, 11, …), and then consider the set of indices at which 1 appears in a’s sequence. If this set is in the ultrafilter, then a = 1 and b = k. If not, then a = k and b = 1.

Now, a challenge for you: construct an infinite ascending sequence of nonstandard primes starting at P.

And another challenge: construct an infinite descending sequence of nonstandard primes starting at P!

Hint for the first challenge: think about the hypernatural [3, 5, 7, 11, 13, 17, …].

Hint for the second challenge: think about the hypernatural [2, 2, 3, 5, 7, 11, …], or [2, 2, 3, 3, 5, 5, 7, 7, …].

While infinite ascending sequences of numbers can exist in ℕ, an infinite descending sequence of numbers can not, so we’ve identified a concrete difference between *ℕ and ℕ. And by Łoś’s theorem, this difference must not be first-order expressible in the language of PA. In other words, “there are no infinitely descending sequences of numbers” cannot be expressed in first-order.

This illustrates another usage of Łoś’s theorem: rather than starting with a first-order sentence that’s true of ℕ and using it to learn about *ℕ, we can start with some facts about *ℕ to learn about limitations of first-order logic!

Alright, what else? Suppose we have a hypernatural number k that has a sequence (k₀, k₁, k₂, …) such that some formula φ(x) holds of cofinitely many elements of the sequence. Then φ(x) also holds of k. This gives us some hypernatural numbers with awfully strange properties.

Consider the hypernatural E = [1, 2, 4, 8, 16, 32, 64, …]. Now consider the formulas that say “x is divisible by 2”, “x is divisible by 4”, “x is divisible by 8”, “x is divisible by 16”, and so on. Each of these formulas holds true of all but some initial segment of the sequence (1, 2, 4, 8, 16, 32, 64, …). This means that each of these sentences hold true of E. In other words, E is divisible by 2, by 4, by 8, by 16, by 32, and so on forever. In other words, E can be divided by 2 forever!

But how exactly does this work? The sequence (1, 2, 4, 8, 16, 32, 64, …) starts with a 1. So how could we divide it by 2? The key is to remember that hypernaturals are equivalence classes of sequences, not sequences. So any time we run into trouble with a particular sequence, we can jump to an equivalent sequence that solves our problem. To divide (1, 2, 4, 8, 16, 32, 64, …) by 2, we jump to the equivalent sequence (2, 2, 4, 8, 16, 32, 64, …), which is still a representative of E. Now we can divide by 2: E/2 = [1, 1, 2, 4, 8, 16, 32, …]. To divide by 2 again, we jump to the sequence (2, 2, 2, 4, 8, 16, 32, …). Then we get E/4 = [1, 1, 1, 2, 4, 8, 16, …]. We can keep doing this as many times as we like, and thus E is infinitely even! (Notice: another infinitely descending sequence of numbers.)

We can use a similar trick to construct a number that’s divisible by every standard natural number: simply consider M = [0!, 1!, 2!, 3!, 4!, 5!, …]. For any standard natural number n, the set of indices at which the sequence (0!, 1!, 2!, 3!, 4!, 5!, …) can be divided by n is cofinite. So M can be divided by n as well!

This lets us run a kind of fun argument. Remember how Euclid’s original proof of the infinitude of primes went? Imagine that there are finitely many primes. Then we can take their product and add 1, and we’ve constructed a new prime. Well, in *ℕ we can find multiples of infinite sets of numbers! One multiple of all standard prime numbers is [2, 2⋅3, 2⋅3⋅5, 2⋅3⋅5⋅7, 2⋅3⋅5⋅7⋅11, …] = [2, 6, 30, 210, 2310, …]. This is divisible by each standard prime, and is also not twice-divisible by any prime (e.g. you can’t divide it by 4). (Interestingly, it’s not the product of all finite primes; because it’s also divisible by some infinite primes! See if you can think of one such infinite factor.) Now add 1 to get X = [3, 7, 31, 211, 2311, …]. X cannot be divisible by any standard prime, meaning that it’s either divisible by a nonstandard prime, or is itself a nonstandard prime. So just as Euclid’s original proof showed that there can’t be only finitely many primes, this proves that there can’t be only finitely large primes.

Alright, let’s get a little more wild. In ℕ we know that for any number x, there’s a number y that’s divisible by all positive numbers up to and including x (for instance, y = x!). In other words, ℕ ⊨ ∀x ∃y ∀z ((z ≠ 0 ∧ z ≤ x) → (y div by z)), where “y div by z” is shorthand for ∃u (z⋅u = y). In other words, ℕ affirms that for every initial segment S with maximum element x, there’s a number that’s divisible by everything in S (for shorthand we can call this number “a multiple of S”).

Invoke Łoś: anything true in ℕ must also be true in *ℕ. This means that every initial segment of hypernaturals with a maximum element has a multiple! (See if you can do better: can you also prove that every initial segment of hypernaturals with a max has a product? What about initial segments without maximum elements?) For instance, there’s a number that’s divisible by every hypernatural number up to and including the hypernatural K = [0,1,2,3,4,5,…].

What other first-order properties does ℕ have? Here’s one: ℕ is not dense. We can express this by saying ¬(∀x ∀z (x < z → ∃y (x < y ∧ y < z)). We can do better: ℕ affirms that ∀x ¬∃y (x < y ∧ y < S(x)). In other words, for any number x, x and its successor are counterexamples to density (they’re distinct numbers that have nothing between them).

So this must be true of hypernaturals as well! For any hypernatural, say K = [0,1,2,3,4,5,…], there’s no hypernatural between it and its successor K+1 = [1,2,3,4,5,6,…].

However, even though the hypernaturals are not dense, they do contain a dense subset! In fact, we can say something even stronger: no segment of the hypernaturals are dense, but nonetheless *ℕ has a dense subset!

Here’s a rough sketch for how to construct this dense subset. Take any nonstandard hypernatural, say K = [0, 1, 2, 3, 4, 5, …]. For any nonzero finite m, we can construct a hypernatural K_m a finite distance from K, such that K’ is divisible by m. Now we can construct n⋅K_m, and then (n/m)⋅K_m. The set { (n/m)⋅K_m | n, m ∈ ℕ } is a subset of the hypernaturals, and it has the order type of the positive rationals!

What other unusual hypernatural numbers can you discover?

Next, we will prove the compactness theorem using ultraproducts. It’s definitely the prettiest proof of compactness out there, so stay tuned!

Ultraproducts and Compactness