All About Countable Saturation (Ultra Series 7)

Previous: Ultraproducts and Compactness

What is Countable Saturation?

I’ve spent a lot of time in the last posts gushing about how cool and powerful Łoś’s theorem is. But Łoś’s theorem is only the second most powerful property of ultraproducts that I know. The most powerful is what’s known as countable saturation.

Countable saturation is a property of structures, and it’s all about definability and parameters. Here it is in one sentence: M is countably saturated if any set of formulas using countably many parameters which is finitely realized in M is also realized in M.

Said another way, M is countably saturated means that: for any set of formulas X with countably many parameters, if the set of subsets of M defined by finite subsets of X has nonempty intersection, then there’s an object in M that satisfies all of X.

If that was a little too much to parse, don’t worry. We’ll now slowly build up to the definition by discussing definability and parameters.

Definability

Let L be some first-order language, and M be some L-structure. Suppose φ(x) is an L-formula with one free variable, x. We can consider the set of objects in the universe of M that satisfy φ: { m ∈ M | M ⊨ φ(m) }. We say that this is the set defined by φ.

For instance, let L be the language of PA and M be the natural numbers. What are the sets defined by the following formulas?

φ₁(x): x > x
φ₂(x): x = x
φ₃(x): ∃y (y + y + y = x)
φ₄(x): ∃y (x + y = x ⋅ y)
φ₅(x): ∀y ∀z (y ⋅ z = x → (y = 1 ∨ z = 1))

Answers:

φ₁ defines ∅
φ₂ defines ℕ
φ₃ defines 3ℕ
φ₄ defines {0, 2}
φ₅ defines the primes

Many many sets of naturals are definable, including uncomputable sets like the set of Busy Beaver numbers. With the language of PA, we are able to define everything on the arithmetic hierarchy, described here.

We’ll denote the set of all definable subsets of a structure M by writing D(M). So D(ℕ) is the set of all arithmetical sets.

Parameters

That’s definability without parameters. What about definability with parameters? Parameters are like additional constants you tack onto a language that refer to a fixed object of your choice. Let’s illustrate this with another example. Suppose that our language is empty, and our structure M contains three objects.

We don’t have any constants, so we have no way to pick out any object by name. We also don’t have any relations or functions, so we have no way to pick out any object by its properties or relationship to other objects. So take a guess, what is D(M)?

Your first thought may have been that D(M) is empty; after all if you can’t pick out any individual objects in the structure, how can you define any sets of objects? But there are still two sets of objects you can always define: the empty set (defined by any contradiction) and the entire structure (defined by any tautology).

D(M) = {∅, M}

Now, suppose that we have a parameter that refers to one particular object. Let’s say the parameter is a.

We now consider formulas φ(x, a) that depend not just on the free variable x, but also this new parameter. For instance, φ(x, a): x = a. What set does this define?

We’ll write D(M, A) for the set of all subsets of M definable with parameters from A. What is D(M, {a}) in our present example?

Answer:

D(M, {a}) = {∅, {a}, M\{a}, M}

We still can’t get every subset of M, because we have no way to single out the objects besides a. Can we do it with two parameters a and b referring to distinct objects in M?

Yes! We don’t need a parameter for the third object, because we can define it with the formula “x ≠ a ∧ x ≠ b”. And once we’ve defined all singletons, we can use disjunctions to define all two-element sets. So with just two parameters, we get to define every possible subset of M.

D(M, {a,b}) = 𝒫(M)

If our structure had 4 objects instead of 3 we could do it with 3 parameters, and if it had 12 objects we could do it with 11 parameters. In general, any finite structure can be fully defined with some finite number of parameters.

Infinite structures are trickier. How many parameters are necessary to fully define ℕ in the language of PA?

Trick question! This just can’t be done in the language of PA. Adding parameters doesn’t actually let us define anything new, because every object can already be referred to: (0, S0, SS0, SSS0, …). Unlike with finite structures, having a name for every object does not guarantee that every set of objects can be defined (though it does guarantee that every finite set of objects can be defined).

But while parameters don’t help with ℕ, they do help with nonstandard models of arithmetic, as these contain objects that can’t be defined with just the symbols in the language. Suppose that K is a parameter that refers to the infinite hypernatural number [0,1,2,3,4,…]. Then { x ∈ *ℕ | x < K } is in D(*ℕ, {K}), but not in D(*ℕ, ∅). We also get { x ∈ *ℕ | x > K ∧ x is prime }, and many other sets.

Finite intersection property

We’re almost ready to define countable saturation. We just need one more concept: the finite intersection property. A set of formulas has the finite intersection property if each of its finite subsets can be realized by some object in M.

Some examples in ℕ:

(i) P = {x < 1, x < 2, x < 3, x < 4, x < 5, x < 6…}
(ii) P = {x > 1, x > 2, x > 3, x > 4, x > 5, x > 6, …}
(iii) P = {∃y (x = y⋅1), ∃y (x = y⋅2), ∃y (x = y⋅3), …}

For each example, we want to verify that for every finite subset of P, we can find an element that satisfies everything in that finite subset.

For instance, to show that (i) really has the finite intersection property, we think about any finite set of formulas in P, such as {x < 12, x < 33, x < 59, x < 64}. What’s an x that satisfies all of these? Obviously anything less than 12 will work, so we can take x = 11. In general, for any finite set F we can just look at the minimum n for which the sentence “x < n” appears in F and then set x = n – 1. More simply, we can just always set x = 0 and this will satisfy every finite subset.

For (ii), we can take any finite set F and find the maximum n for which the sentence x > n appears in F. Then set x = n + 1.

Figure out (iii) for yourself!

There’s an important difference you may have noticed between (i) and (ii)/(iii). Namely, in (i) we have a number (x = 0) that satisfies all of P. But in (ii) no element of c will satisfy all of P, and the same goes for (iii). (For (ii) this would correspond to an infinitely large number, and for (iii) a number that’s a multiple of every standard natural number. Notice that elements like this do exist in *ℕ!)

What this shows is that a set having the finite intersection property does not guarantee that all formulas in it can be simultaneously satisfied by a single element. That is, unless the structure in question is countably saturated!

Countable saturation

And we’ve arrived! Consider any countable set of parameters A, and then any set of formulas using these parameters. Countable saturation of M means that any such set with the finite intersection property will necessarily be satisfied by some object in M.

So for instance, if M is countably saturated, then the fact that {x is a multiple of 2, x is a multiple of 3, x is a multiple of 4, …} has the finite intersection property implies that there’s an object in M that’s a multiple of 2, 3, 4, 5, and all the rest.

Similarly, in a countably saturated model M, {x > 1, x > 2, x > 3, …} having the finite intersection property implies that there’s an object in M that’s bigger than 1, 2, 3, and every other finite number.

Clearly, ℕ isn’t countably saturated. But *ℕ is! So is *ℝ, and *ℤ! And in fact, as long as your ultraproduct is over models with a countable language and has index set ℕ, it will always be countably saturated! This is the big result we’ve been building up to.

For any countable language L and set of L-structures (M₁, M₂, M₃, …),
∏(M_i)_i∈ℕ/U is countably saturated

Let’s prove it!

The Proof

Here’s our setup:

L is a countable language
(M₁, M₂, M₃, …) is a family of L-structures
U is a free ultrafilter on ℕ
M = is the ultraproduct ∏(M_i)_i∈ℕ/U
A is a countable subset of M
L_A is the language L with an added constant for every a ∈ A
P(x) is a countable set of L_A-formulas

Suppose that P(x) is finitely realizable in M. We want to show that it’s also realizable in M. We’ll do this by explicitly constructing the element of M that realizes P(x). Since P(x) is countable, we can choose some enumeration of its formulas: P(x) = {φ₁(x), φ₂(x), φ₃(x), …}.

Begin by writing out the sequence of all of our component models.

We’re going to now start a step-by-step process of eliminating models.

Step 1: Remove all models that don’t realize φ₁.

For illustration purposes, let’s suppose that all models except M₃ and M₇ realize φ₁.

All remaining models realize φ₁.

Step 2: Remove M₁, as well as all models that don’t realize φ₁∧φ₂.

We’ll suppose that of the remaining models, only M₅ doesn’t realize φ₁∧φ₂. So we remove M₁ and M₅.

We’re now left with a set of models that all realize φ₁∧φ₂.

Step 3: Remove M₂, as well as all models that don’t realize φ₁∧φ₂∧φ₃.

This time we remove M₆ and M₁₀, in addition to M₂.

Step 4: Remove M₃, as well as all models that don’t realize φ₁∧φ₂∧φ₃∧φ₄.

M₃ had already been removed, so we don’t do anything with it, but we now also remove M₉.

Continue doing this process forever, so that there’s a “Step N” for every natural number N. We end up with something like this:

There’s something really important that we should notice about each of these sets of models: they’re all U-large. In other words, if at any stage we consider the set of indices of the models that remain, this set will be in U. This follows from finite realizability, by the following argument:

Suppose we consider the set of models that remain after four steps. We know that φ₁∧φ₂∧φ₃∧φ₄ is realizable in M. By Los’s theorem, this means that that the set of component models that realize φ₁∧φ₂∧φ₃∧φ₄ must be U-large. And the set of models remaining after Step 4 is exactly the set of component models that realize φ₁∧φ₂∧φ₃∧φ₄, excluding M₁, M₂, M₃, and M₄. So the remaining models form a U-large set minus a finite number of elements, which is still U-large!

Of course, the choice of “four” here was totally arbitrary. For any finite N, the set of models remaining after Step N is the set of models that realize φ₁∧…∧φ_N (a U-large set), minus the models M₁ through M_N (a finite set). So these are always U-large!

Ok, we’re basically done with the proof now. All that’s left is to use our image to construct an element of M that realizes all of P(x). This construction is extremely simple! Here’s what we do:

For each model, go as many steps as you can before that model is crossed out. Visually, this is just going down each column and circling the model at the step before it is crossed out.

Look closely at the circled models. M₄ is circled after Step 3, which means that it contains an element that realizes φ₁∧φ₂∧φ₃. M₈ is circled after Step 6, so it contains an element realizes φ₁∧…∧φ₆. And so on. For each circled model, we just pick out the element that realizes as many of the “φ”s as is promised to us by the diagram. Let’s call these elements a₁, a₂, a₃, and so on.

Note that M₃ and M₇ were ruled out in Step 1. This was because they didn’t even realize φ₁. These models are useless for our purposes (they aren’t able to realize any of the φs), so we just choose any arbitrary element from them. M₁₁ wasn’t ruled out in any of the first six steps, so we can’t be sure from the diagram exactly how many of the φs it can realize. But we know that at the very latest, it’ll be removed at Step 12.

Anyway, we now have our sequence:

(a₁, a₂, a₃, a₄, …)

The equivalence class of this sequence is an element of M, and it realizes all of P(x)! Why?

Well, let’s think about which elements of the sequence (a₁, a₂, a₃, …) realize φ₁. a₁ clearly does, as we chose it for that purpose. What about a₂? It was chosen to realize φ₁∧φ₂, so of course it also realizes φ₁. a₃ doesn’t realize φ₁, because M₃ didn’t contain any element that realized φ₁. a₄ realizes φ₁ because it realizes φ₁∧φ₂∧φ₃∧φ₄. And so on. In general, a_k realizes φ₁ for every k that’s the index of one of the structures in Step 1 (a U-large set!)

It might be helpful to keep in mind that when we circled a model in row k, the element we chose from that model realizes the conditions in all the earlier rows. We can visualize this as follows:

Now we can easily see which elements realize each formula:

Realizes φ₁: a₁, a₂, a₄, a₅, a₆, a₈, a₉, a₁₀, a₁₁, a₁₂, …
Realizes φ₂: a₂, a₄, a₆, a₈, a₉, a₁₀, a₁₁, a₁₂, …
Realizes φ₃: a₄, a₈, a₁₀, a₁₁, a₁₂, …
Realizes φ₄: a₄, a₈, a₁₁, a₁₂, …
Realizes φ₅: a₈, a₁₁, …
Realizes φ₆: a₈, a₁₁, …
Realizes φ₇: a₁₁, …

(Bonus question: is it possible for more elements to realize φ₅ than those I’ve written? Which elements? And if so, why does that not affect the proof?)

Remember how we showed that the set of models in each row was U-large? Well each of these sets of elements is U-large for the exact same reason! One more application of Łoś’s theorem and we’re done: every φ(x) in P(x) is realized by a U-large set of elements of the sequence (a₁, a₂, a₃, …) , so every φ(x) in P(x) is realized by the element of M that is the equivalence class of this sequence: [a₁, a₂, a₃, …].

And that’s the proof!

Hypernatural Saturation

Countable saturation is an enormously powerful tool for probing the structure of ultraproducts. Let’s see some applications.

We can use countable saturation to prove that there’s a number that’s a multiple of every finite number. We can also use it to prove that there’s a number that’s above every finite number. But we already knew all this. The real power of countable saturation shines through when we use parameters.

Take any countable set of parameters {K₁, K₂, K₃, …}, and choose them to refer to distinct hypernaturals. Now consider the set of sentences {x is divisible by K₁, x is divisible by K₂, x is divisible by K₃, …}. This set of sentences has the finite intersection property. Why? Because finite products always exist. Applying countable saturation, we can conclude that there’s a number that’s divisible by K₁, K₂, K₃, and all the rest!

In other words, every countable set of hypernaturals has a multiple! This is significantly stronger than what we knew before. For one thing, it implies that there are uncountably many hypernatural primes! Suppose that there were countably many hypernatural primes. Collect them in a set P, and find a multiple N of everything in P. Now simply add 1 to N. N+1 is not divisible by any primes. It’s also larger than everything in P (use Łoś to prove this), meaning that it isn’t itself a prime. But by Łoś’s theorem, every hypernatural is either prime or composite! Contradiction.

We can also now show that *N has uncountable cofinality. In other words, every countable set of hypernaturals can be upper bounded. Let {K₁, K₂, K₃, …} be any countable set of hypernaturals. Now consider the set of formulas {x > K₁, x > K₂, x > K₃, …}. Every finite subset can be satisfied; simply take the largest K_n that appears in the subset and add one. Thus there’s some x that’s above the entire set {K₁, K₂, K₃, …}. So every countable set of hypernaturals has an upper bound, meaning that any subset of *ℕ that has no upper bound must be uncountable.

We can get uncountable coinitiality of the infinite hypernaturals by a similar argument. Let {K₁, K₂, K₃, …} be any countable set of infinite hypernaturals and consider the set of formulas {x > 0, x < K₁, x > 1, x < K₂, x > 2, x < K₃, x > 3, …}. Fill out the rest of the argument for yourself!

Uncountable coinitiality of the infinites is a big deal! For one thing, it implies that every infinite hypernatural K is above uncountably many other hypernaturals (as otherwise the set of infinite hypernaturals below K would be a countable coinitial set of infinites). This in turn implies that distances between hypernaturals are either finite or uncountable. They cannot be countably infinite!

Why? Well, ∀x ∀y (x < y → ∃z (z + x = y)) is a sentence of TA that says essentially that for any two numbers x < y, the difference y – x exists as a number. And since we now know that all hypernaturals are either finitely large or uncountably large, we can conclude that differences must be as well!

Applying countable saturation more generally

Let L be any countable language and (M_i)_i∈ℕ be any countable sequence of L-structures. We know that the ultraproduct M = ∏(M_i)_i∈ℕ/U is countably saturated. Let’s further assume that M is infinite. Consider any countable set {K₀, K₁, K₂, …} of objects in M, and apply countable saturation to the set of sentences {x ≠ K₀, x ≠ K₁, x ≠ K₂, …} to prove that there’s some object in M outside of this set.

But the countable set {K₀, K₁, K₂, …} was fully arbitrary! What this means is that any infinite ultraproduct M must be uncountable! We know that there are finite ultraproducts over countable languages (like the ultrapower of ℤ₃, say). So any ultraproducts over a countable language with index set ℕ must be either finite or uncountable. (Exercise: where in the argument did we use the assumption that M is infinite?)

I hope that this next (and final) result blows your mind. It turns out that the continuum hypothesis (ℵ₁ = 2^ℵ₀) has some huge implications on ultraproduct-related matters. I tend to assume that CH is false, which makes the upcoming result a little less exciting to me, but nonetheless I hope it knocks your socks off.

Continuum hypothesis and isomorphic ultrapowers

Fix some countable language L. Suppose that M₁ and M₂ are elementarily equivalent L-structures, and that |M₁| = |M₂| = ℵ₀. If the continuum hypothesis is true, then the ultrapowers of M₁ and M₂ are isomorphic! For example, if ℕ is the standard model of arithmetic, and ℕ’ is some nonstandard countable model of true arithmetic, then *ℕ = *(ℕ’).

The proof of this is pretty nice, but to get there I need to introduce a few more notions.

So far we’ve just talked about countable saturation. But there’s a more general notion of K-saturation for any cardinal K. A structure M is K-saturated if any set of formulas using less than K parameters that’s finitely realizable in M is also realizable in M. So in a slightly annoying terminological quirk, countable saturation is actually ℵ₁-saturation, as “fewer than ℵ₁ parameters” is the same as “countably many parameters”.

A structure M is called saturated if it’s |M|-saturated. These structures are “as saturated as possible”. Nothing can be K-saturated for a cardinal K larger than or equal to its own size (to prove this, add a parameter for every object in the structure and declare x to differ from each of them).

Saturation is a really strong constraint on a structure. It turns out that if two structures are elementarily equivalent, the same size, and saturated, then they are necessarily isomorphic. This means that for instance there’s at most one saturated countable model of true arithmetic (up to isomorphism). The same holds for saturated models of any cardinality of Tarskian geometry, the theory of real closed fields, and any other complete theory.

And now we’re ready for the proof!

Assume that M₁ and M₂ are elementarily equivalent structures in a countable language, and that |M₁| = |M₂| = ℵ₀. Take each of their ultrapowers with index set ℕ and arbitrary ultrafilters, and call them *M₁ and *M₂. What size are these structures? Since they’re ultraproducts, they’re both ℵ₁-saturated, which means that they cannot be countable. And they’re not finite, so they must be uncountable.

Furthermore, |*M₁| ≤ |M₁^ℕ|, as the elements of *M₁ are just equivalence classes on M₁^ℕ. So |*M₁| ≤ |M₁^ℕ| = ℵ₀^ℵ₀ = 2^ℵ₀. Assuming the continuum hypothesis, 2^ℵ₀ = ℵ₁. So ℵ₀ < |M₁| ≤ ℵ₁, meaning that |*M₁| = ℵ₁. But remember that *M₁ is ℵ₁-saturated! So it’s as saturated as can be! Thus we can say that *M₁ is saturated. The exact same argument goes for *M₂. So *M₁ and *M₂ are saturated elementarily equivalent structures, and they’re both cardinality ℵ₁. So they’re isomorphic!

Thus the continuum hypothesis tells us that ultrapowers erase differences between elementarily equivalent countable structures. Even though countable nonstandard models of TA look so different from the standard model, their ultraproducts are isomorphic. In particular, addition and multiplication are computable on ℕ and uncomputable on any nonstandard countable model of arithmetic. So according to CH, computable and uncomputable structures can have the same ultrapower!