2. The ultrapower construction
The study of ultrapowers originates in model theory, although it has found applications both in algebra and in analysis. However, it is accurate to say that it is mainly exploited in set theory. Here I present the basic idea, showing its close connection to the study of measurable cardinals, defined last lecture.
Suppose first that is an ultrafilter over a set We want to define the ultrapower of the universe of sets by The basic idea is to consider the product of many copies of the structure We want to “amalgamate” them somehow into a new structure For this, we look for the “typical” properties of the elements of each “thread” and add an element to whose properties in are precisely these typical properties. We use to make this precise, by saying that a property is typical of the range of iff This leads us to the following definition, due to Dana Scott, that adapts the ultrapower construction to the context of proper classes:
Definition 1 Let be an ultrafilter over a nonempty set We define the ultrapower of by as follows:
For say that
This is easily seen to be an equivalence relation. We would like to make the elements of to be the equivalence classes of this relation. Unfortunately, these are all proper classes except for the trivial case when is a singleton, so we cannot within the context of our formal theory form the collection of all equivalence classes.
Scott’s trick solves this problem by replacing the class of with
Here, as usual, All the “classes” are now sets, and we set
We define by saying that for we have
(It is easy to see that is indeed well defined, i.e., if and then iff )
(The ultrapower construction is more general than as just defined; what I have presented is the particular case of interest to us.) The remarkable observation, due to is that this definition indeed captures the typical properties of each thread in the sense described above:
Lemma 2 () Let be a formula in the language of set theory, and let Then iff
Proof: We argue by induction in the complexity of
- If is atomic, the result holds by definition.
- Assume the result for Suppose that Then the result also holds for since is both upwards closed and closed under intersections.
- Assume the result holds for Suppose that Then the result also holds for since for any either or else
- Finally, assume the result holds for and Let Then we have, by definition, that iff there is some such that This is equivalent, by assumption, to the statement that there is some such that But this last statement is equivalent to In one direction, note that for any In the other, for each such that holds pick a witness Define a function by if holds, and otherwise. Then and we are done.
This completes the proof.
Corollary 3 In particular, is a (proper class) model of set theory.
We arrive at the first connection between the ultrapower construction and measurable cardinals. By Corollary 3, if is an ultrafilter over then satisfies the axiom of foundation, and therefore it “believes” that is a well-founded relation. However, this may actually be false in since a witnessing -decreasing sequence may fail to be an element of
Recall that, by Homework problem 10, if a nonprincipal ultrafilter is -complete, then there is a measurable cardinal.
Theorem 4 Let be an ultrafilter over a set and form the ultrapower Then is well-founded iff is -complete.
Proof: Suppose first that is -complete. If there is a -decreasing sequence let Then for all and therefore (since it is in fact an element of ) If is in this intersection, then is an -decreasing sequence of sets, contradiction. (This is just the proof of Lemma 14 in lecture II.6.)
Suppose now that is not -complete. Then there is a sequence of sets not in whose union is in We may assume that the sets are pairwise disjoint and that their union is in fact all of Define by where is the unique number such that Then since is a finite union of sets not in and is therefore not in
This shows that is a -decreasing sequence of elements of
Lemma 5 Let be an ultrafilter over a set and let Then is a set.
Proof: Let If then Otherwise, given let be given by if and otherwise. Then and if then outside of and the restriction of to is in Since the map that assigns to its restriction to is injective, it follows that injects into the set and is therefore a set.
Suppose that is a -complete ultrafilter over a set (for example, could be principal). Then is a well-founded structure by Theorem 4. Lemma 5 says that it is also set-like. Under these conditions, we can apply Mostowski’s collapsing lemma and replace with an isomorphic, transitive structure :
Lemma 6 (Mostowski) Suppose is a (possibly proper class) structure where and the following conditions hold:
- Extensionality, i.e., for any iff
- is set-like, i.e., for all is a set.
- is well-founded (in ).
Then there is a unique (possibly proper) class that is transitive (i.e., for all ), and a unique isomorphism
The unique as in Lemma 6 is the Mostowski (or transitive) collapse of and the unique is the Mostowski collapsing function.
Proof: Notice first that the -rank of any is defined. As usual,
that is set-like is used to justify that is an ordinal if is an ordinal for all Hence, if is not defined, then is not defined for some and we obtain an -decreasing sequence, against well-foundedness. This is just as the argument following Definition 15 in lecture II.6.
Now define by This is well-defined since otherwise, one immediately arrives at a contradiction by considering an of least -rank for which is undefined.
Let Notice that for any if then Also, is transitive, by definition and, by induction on for any
It follows that is injective. Otherwise, for some By extensionality, there is some such that exactly one of and holds. Without loss, say that Then there is some such that and We thus arrive at a contradiction by considering the least possible rank of an with more than one preimage under
This implies that is an isomorphism, since if then there is some such that But then so
Finally, suppose that is some transitive class and is a map such that is an isomorphism. By considering again a possible counterexample of least -rank, it follows that for all This shows that and are unique, and we are done.
Hence, if is -complete, there is a transitive structure isomorphic to We denote this structure by (Sometimes, is denoted )
Since is transitive and a model of set theory, there is certain resemblance between and In the background, we are using that formulas are absolute between transitive structures that satisfy a modicum of set theory. For example, if and is a function”, then is indeed a function. Similarly, since each element of is (easily) definable, then
It would take us too long to give a detailed presentation of absoluteness, and it is a standard part of any introductory course, so I will take it for granted. See for example Chapter IV of Kenneth Kunen, Set Theory: An introduction to independence proofs, North-Holland (1980).
Consider now an arbitrary set Continuing with the motivation indicated at the beginning of the lecture, it should be clear that if denotes the function constantly equal to then the typical properties of the elements in the range of are just the properties of and it is natural to consider the following map:
Definition 7 Let be an ultrafilter over a set and, for each denote by the map constantly equal to The map
is defined by
The map is an example of a family of class functions very important in the study of large cardinals.
Definition 8 An elementary embedding between two structures (in the same language ) is a function from the universe of to the universe of such that for any formula in language and any
Lemma 9 For any ultrafilter over a set the map is an elementary embedding.
Proof: This is an immediate corollary of ‘s Lemma 2: Given any formula and elements we have that holds iff since this set is either if holds, or otherwise.
But and ‘s lemma concludes the proof.
Let be an ultrafilter over a set and let be its additivity, i.e., is the least cardinal such that is not closed under intersections of length
We can then define, by means of a projection, a nonprincipal ultrafilter over as follows: There is a sequence of sets not in whose union is in We can modify this sequence slightly, if necessary, so they are pairwise disjoint and their union is this uses that is -complete.
Now set, for
This is clearly an ultrafilter, and it is nonprincipal since otherwise one of the sets would be in (This is just like the projection used to define from in the remark before Theorem 2 from last lecture.)
Define by setting where is the function given by for all and all Here, I have added subscripts to the classes to clarify with respect to which ultrafilter they are being formed.
It follows from the definition of that is well defined.
It is also immediate from the definition that whenever we have then so is an embedding.
Lemma 10 With notation as above, is elementary and the diagram commutes, i.e.,
Proof: Given any and let denote the constant function with domain and value Then by definition of This proves commutativity.
Elementarity is also straightforward: Using notation as above, suppose that
for some formula Let be a witness, in the sense that if
then Pick an for each such that and define a function by where is such that and If is not defined, set
Then for some and where is defined using exactly as was defined from
By definition of
and the elementarity of follows from the Tarski-Vaught criterion.
Consider again the case where is -complete, so is defined. Let so is an elementary embedding.
Suppose that is principal, say for some fixed Then, for any function we have Also, by induction on the -rank of we have that since But then, with as above, and we have that is the identity.
If, on the other hand, (there is a measurable cardinal and) is nonprincipal, then is not the identity. We say that is non-trivial. Now we can deduce information about by using that there are two sources of resemblance between and : The latter is transitive, and is an elementary embedding.
Note that by elementarity, is an ordinal for all ordinals Hence, is order preserving, and it follows that for all
Corollary 11 (Scott) If there is a measurable cardinal, then there is a nontrivial elementary embedding from into some transitive class
Proof: Let be measurable and let be a -complete nonprincipal ultrafilter over Let be as above. I will show that is not the identity by arguing that, in fact,
For this, notice that in we have for all where is the identity map from to itself. This uses that bounded subsets of are not in a consequence of -completeness and being nonprincipal.
Then, in for all Hence, and
The fact that some ordinal is moved is not an artifact of the proof but a general fact about elementary embeddings.
Lemma 12 Suppose is a transitive class and is elementary. If is the identity map from to itself, then If is non-trivial, then there is an ordinal such that
Note that it is not automatic that the fact that is the identity implies that For example, consider a countable elementary substructure of and let be its transitive collapse. By the condensation lemma, for some countable and we have
Proof: If is the identity, then for all and
Suppose now that is not the identity, so there is some such that Pick such a set of least possible rank. Since implies that it follows that so and there must be some Assume now that is the identity on the ordinals. Since is an ordinal for all it follows that Thus and Since then and, by elementarity, contradiction.
Definition 13 Let be a non-trivial elementary embedding from into some transitive class (We will simply say that is a nontrivial elementary embedding, or even, that is elementary.)
The smallest such that is called the critical point of and denoted or
Lemma 14 Let be elementary. Then is a strongly inaccessible cardinal.
It follows from the lemma that the existence of elementary embeddings is not provable in The argument to follow should probably remind the reader of Theorem 2 from last lecture.
Proof: is a regular cardinal. Suppose that where Then, by elementarity, But since and for all since both and are smaller than This shows that In particular, so it is an ordinal fixed by and is not cofinal in
is uncountable. This is because and each natural number are definable, so they are fixed by
is limit. Otherwise, for some but the ordinal that, from the point of view of is the successor of Since Since and it follows that contradicting that
In fact, is strong limit. Suppose otherwise, and let be such that So we can find and a bijection
Note that Suppose that Then and and for any iff so It follows that and On the other hand, if then and we have shown that .
Also, for any since It follows that and we have shown that is fixed by contradiction.
This is how things stood up for a while: We have shown that the critical point of any embedding is inaccessible, and that any measurable is inaccessible.
Now the key idea of reflection shows up, and we can prove significantly more.
Theorem 15 Let be elementary and let Then is the -th strongly inaccessible cardinal.
Proof: is strongly inaccessible in by Lemma 14 and therefore in since It follows that, for any there is in some inaccessible larger than and below namely, By elementarity, the inaccessible cardinals below are unbounded in
The argument gives much more. For example, is inaccessible and limit of inaccessible cardinals, so the same proof shows that is limit of inaccessible cardinals that are themselves the limit of inaccessible cardinals that are limit of inaccessible cardinals Even more is true, i.e., we can diagonalize and continue. This requires a new key idea.
Then is a nonprincipal ultrafilter over :
- If and then since
- is closed under intersections since
- If then so either or is in
- If then so is nonprincipal.
In fact, is -complete: Let and let Then But and therefore for all such It follows that
The ultrafilter found by Keisler is particularly nice, since it is normal: Using the same notation as above, suppose that is a sequence of elements of Let be the map Recall that Then iff for all But and we are done.
Notice that extends the club filter. This follows either from general arguments about normal filters, or simply by noticing that if is club, then because is unbounded in and is closed.
(To see that if is a normal filter on that contains the cobounded sets then it is -complete, given and a sequence extend it to a -sequence by setting for all and notice that where Since it follows that as claimed.)
Corollary 17 If is measurable, then there is a nonprincipal normal ultrafilter on (extending the filter of cobounded sets).
Definition 18 A cardinal of uncountable cofinality is Mahlo iff the set of inaccessible cardinals below is stationary.
It follows from the definition that if is Mahlo then it is regular: Suppose that is unbounded and Let be the club of limit points of Then contains no inaccessible cardinals, in fact, it contains no regular cardinals, contradiction. It also follows that is strong limit, since it is a limit of strong limit (in fact, inaccessible) cardinals. Thus, is the -th inaccessible, and an easy diagonal argument shows it is limit of inaccessible cardinals that are limit of inaccessible cardinals, etc.
Corollary 19 If is measurable then it is the -th Mahlo cardinal.
Proof: If is elementary and then for any club It follows by elementarity that contains an inaccessible cardinal. Hence, is Mahlo. By elementarity, contains a Mahlo cardinal, etc.
Stronger conclusions can be derived by taking where is normal. This is because of the following observation:
Lemma 20 Let be a nonprincipal -complete ultrafilter over the measurable cardinal Then the following are equivalent:
- is normal.
- Whenever and is regressive, then there is such that
- where denotes (Scott) classes in
Proof: From normality of we get a version of Fodor’s lemma just as before, so 1 implies 2.
2 implies 3, since 2 says that if then for some
3 implies 1, because given any we have that iff iff iff so is the ultrafilter derived from the embedding which is normal by the remark following Keisler's Theorem 16.
I close with a list of structural fact about (well-founded) ultrapower embeddings; I concentrate on the particular case of ultrafilters over cardinals, although essentially this suffices by Lemma 10:
Lemma 21 Let be a -complete nonpricipal ultrafilter over the measurable cardinal and let be the corresponding ultrapower embedding. To ease notation, write instead of Then:
This result indicates that there are limits to the embeddings that can be represented by means of ultrapowers. For example, even though there is a great deal of resemblance between and is not closed under -sequences and does not contain and is not really a cardinal. Any embedding with these additional properties would necessarily capture stronger large cardinal properties and would produce stronger reflection arguments than those one can do in our setting. (For example, if for some elementary with then is measurable in and therefore there is a normal ultrafilter over that concentrates on measurable cardinals, i.e., is measurable) The modern template for defining large cardinals stipulates the existence of embeddings with large resemblance between and and stronger “correctness'' of It is natural to wonder how much resemblance can be asked. Kunen showed, for example, that is impossible.
Proof: We already know from Corollary 11 that If let be such that Then By -completeness, for some , so and contradiction. This proves 1.
If then an easy argument as in the proof of Lemma 14 gives that so If then it follows that and therefore
Note that any well-ordering of is a subset of and can be identified with a subset of Since all these subsets are in and computes correctly.
To show that suppose more generally that for some and that where and conclude that This gives the result, since
To see the claim, say and let be the map It is easy to see that is well defined. If then also, since To see that we find some such that To do this, note that since there is some such that and set to be the function such that, for all is the map whenever this makes sense, and otherwise. It is easy to check that, indeed, This proves 2.
On the other hand, which proves 3. To see this, note that if then for some By regularity of is bounded, so there is some such that and is a limit cardinal of so in fact since Hence, We are done, since is regular from the point of view of by elementarity.
Now we prove 5: First, Since it follows that Since is, from the point of view of a strong limit cardinal larger than we must have On the other hand, if then for some and there are only many such functions so only many ordinals below Therefore, and 5 follows.
This gives us 4: Since we have If then we could correctly compute, in the value of which would prove that contradicting the fact that is a cardinal in
The results in this lecture are all classical, although I don't remember ever seen Lemma 10 (and its preceding remarks) explicitly stated. It is certainly part of the folklore. A good reference is Akihiro Kanamori, The Higher Infinite, Springer (1994). For the few model-theoretic results we need, any standard reference would work, for example, Chen-Chung Chang, H. Jerome Keisler, Model theory, North-Holland (1990).
Typeset using LaTeX2WP. Here is a printable version of (an almost final draft of) this post.
[…] 580 -Cardinal arithmetic (10) Let me begin with a couple of comments that may help clarify some of the results from last lecture. […]
[…] is defined by a straightforward generalization of Definition 1 from lecture II.9: For set iff Let be the equivalence class of under this equivalence relation. Now we do not […]
[…] Let me begin with a couple of comments that may help clarify some of the results from last lecture. […]
[…] is defined by a straightforward generalization of Definition 1 from lecture II.9: For set iff Let be the equivalence class of under this equivalence relation. Now we do not […]