580 -Cardinal arithmetic (9)

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 ${{\mathcal U}}$ is an ultrafilter over a set ${X.}$ We want to define the ultrapower of the universe ${V}$ of sets by ${{\mathcal U}.}$ The basic idea is to consider the product of ${X}$ many copies of the structure ${(V,\in).}$ We want to “amalgamate” them somehow into a new structure ${(\tilde V,\tilde\in).}$ For this, we look for the “typical” properties of the elements ${\{f(x): x\in X\}}$ of each “thread” ${f:X\rightarrow V,}$ and add an element ${\tilde f}$ to ${\tilde V}$ whose properties in ${(\tilde V,\tilde\in)}$ are precisely these typical properties. We use ${{\mathcal U}}$ to make this precise, by saying that a property ${\varphi}$ is typical of the range of ${f}$ iff ${\{x\in X:\varphi(f(x))\}\in{\mathcal U}.}$ 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 ${{\mathcal U}}$ be an ultrafilter over a nonempty set ${X.}$ We define the ultrapower ${(V^X/{\mathcal U},\hat\in)}$ of ${V}$ by ${{\mathcal U}}$ as follows:

For ${f,g:X\rightarrow V,}$ say that

$\displaystyle f=_{\mathcal U} g \mbox{ iff } \{x \in X: f(x)=g(x)\} \in{\mathcal U}.$

This is easily seen to be an equivalence relation. We would like to make the elements of ${V^X/{\mathcal U}}$ to be the equivalence classes of this relation. Unfortunately, these are all proper classes except for the trivial case when ${X}$ 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 ${f}$ with

$\displaystyle [f]:= \{g : X\rightarrow V : g=_{\mathcal U}f \mbox{ and } {\rm rk}(g)\mbox{ is least possible}\}.$

Here, as usual, ${{\rm rk}(g) = {\rm min}\{\alpha : g\in V_{\alpha+1}\} = \sup\{ {\rm rk}(x) +1 : x\in g\}.}$ All the “classes” ${[f]}$ are now sets, and we set ${V^X/{\mathcal U} = \{[f] : f:X\rightarrow V\}.}$

We define ${\hat\in}$ by saying that for ${f,g:X\rightarrow V}$ we have

$\displaystyle [f]\hat\in[g] \mbox{ iff } \{x \in X : f(x)\in g(x)\} \in {\mathcal U}.$

(It is easy to see that ${\hat\in}$ is indeed well defined, i.e., if ${f=_{\mathcal U}f'}$ and ${g=_{\mathcal U}g'}$ then ${\{x\in X : f(x)\in g(x)\} \in {\mathcal U}}$ iff ${\{x\in X : f'(x)\in g'(x)\} \in {\mathcal U}.}$ )

(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 $\mbox{\L o\'s,}$ is that this definition indeed captures the typical properties of each thread in the sense described above:

Lemma 2 ( $\mbox{\bf \L o\'s}$ ) Let ${\varphi(x_1,\dots,x_n)}$ be a formula in the language of set theory, and let ${f_1,\dots,f_n:X\rightarrow V.}$ Then ${V^X/{\mathcal U} \models \varphi([f_1],\dots,[f_n])}$ iff ${\{x\in X: \varphi(f_1(x),\dots,f_n(x)\} \in{\mathcal U}.}$

Proof: We argue by induction in the complexity of ${\varphi.}$

If ${\varphi}$ is atomic, the result holds by definition.
Assume the result for ${\phi,\psi.}$ Suppose that ${\varphi \equiv \phi\land\psi.}$ Then the result also holds for ${\varphi,}$ since ${{\mathcal U}}$ is both upwards closed and closed under intersections.
Assume the result holds for ${\phi.}$ Suppose that ${\varphi \equiv \lnot \phi.}$ Then the result also holds for ${\varphi,}$ since for any ${Y \subseteq X,}$ either ${Y\in{\mathcal U}}$ or else ${X\setminus Y \in{\mathcal U}.}$
Finally, assume the result holds for ${\phi(x,x_1,\dots,x_n)}$ and ${\varphi \equiv \exists x\,\phi(x,x_1,\dots,x_n).}$ Let ${f_1,\dots,f_n:X \rightarrow V.}$ Then we have, by definition, that ${V^X/{\mathcal U} \models \varphi([f_1],\dots,[f_n])}$ iff there is some ${g:X\rightarrow V}$ such that ${V^X/{\mathcal U} \models \phi([g],[f_1],\dots,[f_n]).}$ This is equivalent, by assumption, to the statement that there is some ${g:X \rightarrow V}$ such that ${\{x\in X : \phi(g(x),f_1(x),\dots,f_n(x))\} \in {\mathcal U}.}$ But this last statement is equivalent to ${\{x \in X : \varphi(f_1(x),\dots,f_n(x))\} \in {\mathcal U}:}$ In one direction, note that ${\{x \in X : \phi(g(x),\vec f(x))\} \subseteq \{x\in X : \varphi(\vec f(x))\}}$ for any ${g.}$ In the other, for each ${x}$ such that ${\varphi(\vec f(x))}$ holds pick a witness ${\iota_x.}$ Define a function ${g:X \rightarrow V}$ by ${g(x)=\iota_x}$ if ${\varphi(\vec f(x))}$ holds, and ${g(x)=0}$ otherwise. Then ${\{x \in X : \varphi(\vec f(x))\} =\{ x \in X : \phi(g(x),\vec f(x))\},}$ and we are done.

This completes the proof. $\Box$

Corollary 3 ${V^X/{\mathcal U}\equiv V.}$ In particular, ${V^X/{\mathcal U}}$ is a (proper class) model of set theory. ${\Box}$

We arrive at the first connection between the ultrapower construction and measurable cardinals. By Corollary 3, if ${{\mathcal U}}$ is an ultrafilter over ${X,}$ then ${V^X/{\mathcal U}}$ satisfies the axiom of foundation, and therefore it “believes” that ${\hat\in}$ is a well-founded relation. However, this may actually be false in ${V,}$ since a witnessing ${\hat\in}$ -decreasing sequence may fail to be an element of ${V^X/{\mathcal U}.}$

Recall that, by Homework problem 10, if a nonprincipal ultrafilter is ${\sigma}$ -complete, then there is a measurable cardinal.

Theorem 4 Let ${{\mathcal U}}$ be an ultrafilter over a set ${X,}$ and form the ultrapower ${(V^X/{\mathcal U},\hat\in).}$ Then ${\hat\in}$ is well-founded iff ${{\mathcal U}}$ is ${\sigma}$ -complete.

Proof: Suppose first that ${{\mathcal U}}$ is ${\sigma}$ -complete. If there is a ${\hat\in}$ -decreasing sequence ${([f_n] : n\in\omega),}$ let ${A_n=\{x\in X : f_{n+1}(x) \in f_n(x)\}.}$ Then ${A_n\in {\mathcal U}}$ for all ${n}$ and therefore ${\bigcap_nA_n\ne \emptyset}$ (since it is in fact an element of ${{\mathcal U}.}$ ) If ${x}$ is in this intersection, then ${(f_n(x) : n<\omega)}$ is an ${\in}$ -decreasing sequence of sets, contradiction. (This is just the proof of Lemma 14 in lecture II.6.)

Suppose now that ${{\mathcal U}}$ is not ${\sigma}$ -complete. Then there is a sequence ${(X_n : n\in \omega)}$ of sets not in ${{\mathcal U}}$ whose union is in ${{\mathcal U}.}$ We may assume that the sets ${X_n}$ are pairwise disjoint and that their union is in fact all of ${X.}$ Define ${g_n:X \rightarrow V}$ by ${g_n(x)=\max(m-n,0),}$ where ${m}$ is the unique number such that ${x\in X_m.}$ Then ${\{x\in X : g_{n+1}(x) \in g_n(x)\} = \bigcup_{m>n} X_m \in{\mathcal U},}$ since ${\bigcup_{m\le n}X_m}$ is a finite union of sets not in ${{\mathcal U}}$ and is therefore not in ${{\mathcal U}.}$

This shows that ${([g_n]: n\in \omega)}$ is a ${\hat\in}$ -decreasing sequence of elements of ${V^X/{\mathcal U}.}$ $\Box$

Lemma 5 Let ${{\mathcal U}}$ be an ultrafilter over a set ${X,}$ and let ${f:X \rightarrow V.}$ Then ${\{[g]:[g]\hat\in[f]\}}$ is a set.

Proof: Let ${\hat f = \{[g] : [g]\hat\in[f]\}.}$ If ${\{x : f(x)=0\} \in {\mathcal U},}$ then ${\hat f=\emptyset.}$ Otherwise, given ${[g]\hat\in[f]}$ let ${g':X\rightarrow V}$ be given by ${g'(x)=g(x)}$ if ${g(x)\in f(x)}$ and ${g'(x)=0}$ otherwise. Then ${g'=_{\mathcal U}g}$ and if ${Y= \{x : f(x) \ne \emptyset\}}$ then ${g'(x)=0}$ outside of ${Y}$ and the restriction of ${g'}$ to ${Y}$ is in ${\prod_{x\in Y}f(x).}$ Since the map that assigns to ${g'}$ its restriction to ${Y}$ is injective, it follows that ${\hat f}$ injects into the set ${\prod_{x\in Y}f(x)}$ and is therefore a set. $\Box$

Suppose that ${{\mathcal U}}$ is a ${\sigma}$ -complete ultrafilter over a set ${X}$ (for example, ${{\mathcal U}}$ could be principal). Then ${(V^X/{\mathcal U},\hat\in)}$ 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 ${(V^X/{\mathcal U},\hat\in)}$ with an isomorphic, transitive structure ${M}$ :

Lemma 6 (Mostowski) Suppose ${(A,E)}$ is a (possibly proper class) structure where ${E\subseteq A\times A}$ and the following conditions hold:

${(A,E) \models}$ Extensionality, i.e., for any ${a,b \in A,}$ ${a=b}$ iff ${\forall c\in A\,(cEa\Leftrightarrow cEb).}$

${E}$ is set-like, i.e., for all ${a\in A,}$ ${\hat a=\{b\in A: bEa}\}$ is a set.

${E}$ is well-founded (in ${V}$ ).

Then there is a unique (possibly proper) class ${M}$ that is transitive (i.e., for all ${a\in M,}$ ${a\subseteq M}$ ), and a unique isomorphism ${\pi:(A,E) \rightarrow (M,\in).}$

The unique ${M}$ as in Lemma 6 is the Mostowski (or transitive) collapse of ${A}$ and the unique ${\pi}$ is the Mostowski collapsing function.

Proof: Notice first that the ${E}$ -rank of any ${a\in A}$ is defined. As usual,

$\displaystyle |a|_E=\sup\{|b|_E+1: bEa\};$

that ${E}$ is set-like is used to justify that ${|a|_E}$ is an ordinal if ${|b|_E}$ is an ordinal for all ${bEa.}$ Hence, if ${|a|_E}$ is not defined, then ${|b|_E}$ is not defined for some ${bEa,}$ and we obtain an ${E}$ -decreasing sequence, against well-foundedness. This is just as the argument following Definition 15 in lecture II.6.

Now define ${\pi:A \rightarrow V}$ by ${\pi(a)=\{\pi(b) : bEa\}.}$ This is well-defined since otherwise, one immediately arrives at a contradiction by considering an ${a}$ of least ${E}$ -rank for which ${\pi(a)}$ is undefined.

Let ${M=\pi[A].}$ Notice that for any ${a,b\in A,}$ if ${aEb}$ then ${\pi(a)\in \pi(b).}$ Also, ${M}$ is transitive, by definition and, by induction on ${|a|_E,}$ ${{\rm rk}(\pi(a))=|a|_E}$ for any ${a\in A.}$

It follows that ${\pi}$ is injective. Otherwise, ${\pi(a)=\pi(b)}$ for some ${a\ne b.}$ By extensionality, there is some ${c}$ such that exactly one of ${cEa}$ and ${cEb}$ holds. Without loss, say that ${cEa.}$ Then there is some ${d}$ such that ${\pi(c)=\pi(d)}$ and ${dEb.}$ We thus arrive at a contradiction by considering the least possible rank of an ${x\in M}$ with more than one preimage under ${\pi.}$

This implies that ${\pi}$ is an isomorphism, since if ${\pi(a) \in \pi(b)}$ then there is some ${cEb}$ such that ${\pi(a)=\pi(c).}$ But then ${a=c}$ so ${aE b.}$

Finally, suppose that ${M'}$ is some transitive class and ${\pi'}$ is a map such that ${\pi':(A,E) \rightarrow (M',\in)}$ is an isomorphism. By considering again a possible counterexample of least ${E}$ -rank, it follows that ${\pi'(a)=\pi(a)}$ for all ${a\in A.}$ This shows that ${M}$ and ${\pi}$ are unique, and we are done. $\Box$

Hence, if ${{\mathcal U}}$ is ${\sigma}$ -complete, there is a transitive structure isomorphic to ${V^X/{\mathcal U}.}$ We denote this structure by ${{\rm Ult}(V,{\mathcal U}).}$ (Sometimes, ${V^X/{\mathcal U}}$ is denoted ${{\rm Ult}^*(V,{\mathcal U}).}$ )

Since ${{\rm Ult}(V,{\mathcal U})}$ is transitive and a model of set theory, there is certain resemblance between ${V}$ and ${{\rm Ult}(V,{\mathcal U}).}$ In the background, we are using that ${\Delta_1}$ formulas are absolute between transitive structures that satisfy a modicum of set theory. For example, if ${x\in{\rm Ult}(V,{\mathcal U})}$ and ${{\rm Ult}(V,{\mathcal U}) \models ``x}$ is a function”, then ${x}$ is indeed a function. Similarly, since each element of ${V_\omega}$ is (easily) definable, then ${V_\omega\subseteq {\rm Ult}(V,{\mathcal U}).}$

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 ${t.}$ Continuing with the motivation indicated at the beginning of the lecture, it should be clear that if ${c_t:X\rightarrow V}$ denotes the function constantly equal to ${t,}$ then the typical properties of the elements in the range of ${c_t}$ are just the properties of ${t,}$ and it is natural to consider the following map:

Definition 7 Let ${{\mathcal U}}$ be an ultrafilter over a set ${X}$ and, for each ${t\in V,}$ denote by ${c_t:X\rightarrow V}$ the map constantly equal to ${t.}$ The map

$\displaystyle i_{\mathcal U}:V \rightarrow V^X/{\mathcal U}$

is defined by ${i_{\mathcal U}(t)=[c_t].}$

The map ${i_{\mathcal U}}$ is an example of a family of class functions very important in the study of large cardinals.

Definition 8 An elementary embedding ${j:{\mathcal M} \rightarrow {\mathcal N}}$ between two structures (in the same language ${{\mathcal L}}$ ) is a function ${j}$ from the universe of ${{\mathcal M}}$ to the universe of ${{\mathcal N}}$ such that for any formula ${\varphi(x_1,\dots,x_n)}$ in language ${{\mathcal L}}$ and any ${a_1,\dots,a_n \in {\mathcal M},}$

$\displaystyle {\mathcal M} \models \varphi(a_1,\dots,a_n) \mbox{ iff } {\mathcal N} \models \varphi(j(a_1),\dots,j(a_n)).$

Lemma 9 For any ultrafilter ${{\mathcal U}}$ over a set ${X,}$ the map ${i_{\mathcal U}:V \rightarrow V^X/{\mathcal U}}$ is an elementary embedding.

Proof: This is an immediate corollary of $\mbox{\L o\'s}$ ‘s Lemma 2: Given any formula ${\varphi(\vec x)}$ and elements ${\vec a\in V,}$ we have that ${\varphi(\vec a)}$ holds iff ${\{x\in X : \varphi(\vec a)\} \in {\mathcal U}}$ since this set is either ${X}$ if ${\varphi(\vec a)}$ holds, or ${\emptyset}$ otherwise.

But ${\{x : \varphi(a_1,\dots,a_n)\}=\{x : \varphi(c_{a_1}(x),\dots,c_{a_n}(x))\},}$ and $\mbox{\L o\'s}$ ‘s lemma concludes the proof. $\Box$

Let ${{\mathcal U}}$ be an ultrafilter over a set ${X,}$ and let ${\kappa}$ be its additivity, i.e., ${\kappa}$ is the least cardinal such that ${{\mathcal U}}$ is not closed under intersections of length ${\kappa.}$

We can then define, by means of a projection, a nonprincipal ultrafilter ${{\mathcal W}}$ over ${\kappa}$ as follows: There is a sequence ${(X_\alpha: \alpha<\kappa)}$ of sets not in ${{\mathcal U}}$ whose union is in ${{\mathcal U}.}$ We can modify this sequence slightly, if necessary, so they are pairwise disjoint and their union is ${X;}$ this uses that ${{\mathcal U}}$ is ${\kappa}$ -complete.

Now set, for ${A \subseteq \kappa,}$

$\displaystyle A\in{\mathcal W} \mbox{ iff } \bigcup_{\alpha\in A} X_\alpha \in {\mathcal U}.$

This is clearly an ultrafilter, and it is nonprincipal since otherwise one of the sets ${X_\alpha}$ would be in ${{\mathcal U}.}$ (This is just like the projection used to define ${\mu}$ from ${\lambda}$ in the remark before Theorem 2 from last lecture.)

Define ${k:V^\kappa/{\mathcal W}\rightarrow V^X/{\mathcal U}}$ by setting ${k([f]_{\mathcal W})=[g_f]_{\mathcal U}}$ where ${g_f:X \rightarrow V}$ is the function given by ${g_f(x)=f(\alpha)}$ for all ${x\in X_\alpha}$ and all ${\alpha \in \kappa.}$ Here, I have added subscripts to the classes ${[\cdot]}$ to clarify with respect to which ultrafilter they are being formed.

It follows from the definition of ${{\mathcal W}}$ that ${k}$ is well defined.

It is also immediate from the definition that whenever we have ${{\rm Ult}^*(V,{\mathcal W}) \models [f_1]\hat\in[f_2],}$ then ${{\rm Ult}^*(V,{\mathcal U}) \models k([f_1])\hat\in k([f_2]),}$ so ${k}$ is an embedding.

Lemma 10 With notation as above, ${k}$ is elementary and the diagram commutes, i.e., ${k\circ i_{\mathcal W}=i_{\mathcal U}.}$

Proof: Given any ${x}$ and ${A,}$ let ${c_X^A}$ denote the constant function with domain ${A}$ and value ${x.}$ Then ${k\circ i_{\mathcal W}(x)=k(i_{\mathcal W}(x))=k([c^\kappa_x]_{\mathcal W})=[c^X_x]_{\mathcal U}=i_{\mathcal U}(x),}$ by definition of ${k.}$ This proves commutativity.

Elementarity is also straightforward: Using notation as above, suppose that

$\displaystyle {\rm Ult}^*(V,{\mathcal U}) \models \exists x\,\varphi(x,[g_{f_1}],\dots,[g_{f_n}])$

for some formula ${\varphi(x,x_1,\dots,x_n).}$ Let ${f:X \rightarrow V}$ be a witness, in the sense that if

$\displaystyle Y_f=\{a \in X : \forall\alpha<\kappa\,(a \in X_\alpha \rightarrow \varphi(f(a),f_1(\alpha),\dots,f_n(\alpha)))\},$

then ${Y_f \in{\mathcal U}.}$ Pick an ${a_\alpha \in X_\alpha\cap Y_f}$ for each ${\alpha<\kappa}$ such that ${X_\alpha\cap Y_f \ne \emptyset,}$ and define a function ${g:X \rightarrow V}$ by ${g(a)=f(a_\alpha)}$ where ${\alpha}$ is such that ${a\in X_\alpha}$ and ${X_\alpha\cap Y_f\ne \emptyset.}$ If ${a_\alpha}$ is not defined, set ${g(a)=0.}$

Then ${g=g_h}$ for some ${h:\kappa \rightarrow V,}$ and ${Y_g \in{\mathcal U},}$ where ${Y_g}$ is defined using ${g}$ exactly as ${Y_f}$ was defined from ${f.}$

By definition of ${{\mathcal W},}$

$\displaystyle {\rm Ult}^*(V,{\mathcal W}) \models \varphi([h],[f_1],\dots,[f_n]),$

and the elementarity of ${k}$ follows from the Tarski-Vaught criterion. $\Box$

Consider again the case where ${{\mathcal U}}$ is ${\sigma}$ -complete, so ${{\rm Ult}(V,{\mathcal U})}$ is defined. Let ${j=\pi\circ i_{\mathcal U},}$ so ${j:V \rightarrow{\rm Ult}(V,{\mathcal U})}$ is an elementary embedding.

Suppose that ${{\mathcal U}}$ is principal, say ${{\mathcal U}=\{Y \subseteq X : x_0 \in Y\}}$ for some fixed ${x_0 \in X.}$ Then, for any function ${f:X \rightarrow V,}$ we have ${[f]=[c_{f(x_0)}].}$ Also, by induction on the ${\hat\in}$ -rank of ${f,}$ we have that ${\pi([f])=f(x_0),}$ since ${\pi([f])=\{\pi[g]:gEf\} = \{g(x_0) : g(x_0)\in f(x_0)\}=f(x_0).}$ But then, with ${j}$ as above, ${j(t)=\pi\circ i_{\mathcal U}(t)=\pi([c_t])=t}$ and we have that ${j}$ is the identity.

If, on the other hand, (there is a measurable cardinal and) ${{\mathcal U}}$ is nonprincipal, then ${j}$ is not the identity. We say that ${j}$ is non-trivial. Now we can deduce information about ${V}$ by using that there are two sources of resemblance between ${V}$ and ${{\rm Ult}(V,{\mathcal U})}$ : The latter is transitive, and ${j}$ is an elementary embedding.

Note that by elementarity, ${j(\alpha)}$ is an ordinal for all ordinals ${\alpha.}$ Hence, ${j:{\sf ORD}\rightarrow{\sf ORD}}$ is order preserving, and it follows that ${j(\alpha)\ge\alpha}$ for all ${\alpha.}$

Corollary 11 (Scott) If there is a measurable cardinal, then there is a nontrivial elementary embedding ${j:V \rightarrow M}$ from ${V}$ into some transitive class ${M.}$

Proof: Let ${\kappa}$ be measurable and let ${{\mathcal U}}$ be a ${\kappa}$ -complete nonprincipal ultrafilter over ${\kappa.}$ Let ${j:V \rightarrow{\rm Ult}(V,{\mathcal U})}$ be as above. I will show that ${j}$ is not the identity by arguing that, in fact, ${j(\kappa)>\kappa.}$

For this, notice that in ${V^\kappa/{\mathcal U}}$ we have ${[c_\alpha] \hat\in [{\rm id}] \hat\in [c_\kappa]}$ for all ${\alpha<\kappa,}$ where ${{\rm id}}$ is the identity map from ${\kappa}$ to itself. This uses that bounded subsets of ${\kappa}$ are not in ${{\mathcal U},}$ a consequence of ${\kappa}$ -completeness and ${{\mathcal U}}$ being nonprincipal.

Then, in ${{\rm Ult}(V,{\mathcal U}),}$ ${\alpha \le j(\alpha)<\pi([{\rm id}])<j(\kappa)}$ for all ${\alpha<\kappa.}$ Hence, ${\pi([{\rm id}]) \ge \kappa}$ and ${\kappa<j(\kappa).}$ $\Box$

The fact that some ordinal is moved is not an artifact of the proof but a general fact about elementary embeddings.

Lemma 12 Suppose ${M}$ is a transitive class and ${j:V \rightarrow M}$ is elementary. If ${j={\rm id}}$ is the identity map from ${V}$ to itself, then ${M=V.}$ If ${j}$ is non-trivial, then there is an ordinal ${\alpha}$ such that ${j(\alpha) \ne \alpha.}$

Note that it is not automatic that the fact that ${j}$ is the identity implies that ${M=V.}$ For example, consider a countable elementary substructure of ${L_{\omega_1},}$ and let ${M}$ be its transitive collapse. By the condensation lemma, ${M=L_\alpha}$ for some countable ${\alpha}$ and we have ${L_\alpha\prec L_{\omega_1}.}$

Proof: ${j(V)=j(\bigcup_\alpha V_\alpha) \supseteq \bigcup_\alpha j(V_\alpha).}$ If ${j}$ is the identity, then ${j(V_\alpha)=V_\alpha}$ for all ${\alpha,}$ and ${M \supseteq V.}$

Suppose now that ${j}$ is not the identity, so there is some ${x}$ such that ${j(x) \ne x.}$ Pick such a set ${x}$ of least possible rank. Since ${y\in x}$ implies that ${{\rm rk}(y)<{\rm rk}(x),}$ it follows that ${j(y)=y,}$ so ${x\subseteq j(x),}$ and there must be some ${y\in j(x)\setminus x.}$ Assume now that ${j}$ is the identity on the ordinals. Since ${{\rm rk}(t)}$ is an ordinal for all ${t,}$ it follows that ${{\rm rk}(j(x))=j({\rm rk}(x))={\rm rk}(x).}$ Thus ${{\rm rk}(y)<{\rm rk}(x)}$ and ${y=j(y).}$ Since ${y\in j(x)}$ then ${j(y)\in j(x)}$ and, by elementarity, ${y\in x,}$ contradiction. $\Box$

Definition 13 Let ${j:V \rightarrow M}$ be a non-trivial elementary embedding from ${V}$ into some transitive class ${M.}$ (We will simply say that ${j:V \rightarrow M}$ is a nontrivial elementary embedding, or even, that ${j:V \rightarrow M}$ is elementary.)

The smallest ${\alpha}$ such that ${j(\alpha)>\alpha}$ is called the critical point of ${j,}$ and denoted ${{\rm cp}(j)}$ or ${{\rm crit}(j).}$

Lemma 14 Let ${j:V \rightarrow M}$ be elementary. Then ${\kappa={\rm cp}(j)}$ is a strongly inaccessible cardinal.

It follows from the lemma that the existence of elementary embeddings is not provable in ${{\sf ZFC}.}$ The argument to follow should probably remind the reader of Theorem 2 from last lecture.

Proof: ${\kappa}$ is a regular cardinal. Suppose that ${f:\alpha\rightarrow\kappa}$ where ${\alpha<\kappa.}$ Then, by elementarity, ${j(f):j(\alpha)\rightarrow j(\kappa).}$ But ${j(\alpha)=\alpha}$ since ${\alpha<\kappa,}$ and ${j(f)(\beta)=j(f)(j(\beta))=j(f(\beta))=f(\beta)}$ for all ${\beta<\alpha}$ since both ${\beta}$ and ${f(\beta)}$ are smaller than ${\kappa.}$ This shows that ${j(f)=f.}$ In particular, ${\sup f[\alpha]=sup j(f)[\alpha],}$ so it is an ordinal fixed by ${j,}$ and ${f}$ is not cofinal in ${\kappa.}$

${\kappa}$ is uncountable. This is because ${\omega}$ and each natural number are definable, so they are fixed by ${j.}$

${\kappa}$ is limit. Otherwise, ${\kappa=\lambda^+}$ for some ${\lambda,}$ but ${j(\kappa)=(j(\lambda)^+)^M,}$ the ordinal that, from the point of view of ${M,}$ is the successor of ${j(\lambda).}$ Since ${M\subseteq V,}$ ${(j(\lambda)^+)^M \le j(\lambda)^+.}$ Since ${\lambda<\kappa,}$ ${j(\lambda)=\lambda,}$ and it follows that ${j(\kappa) \le \lambda^+=\kappa,}$ contradicting that ${\kappa<j(\kappa).}$

In fact, ${\kappa}$ is strong limit. Suppose otherwise, and let ${\rho<\kappa}$ be such that ${2^\rho\ge\kappa.}$ So we can find ${A\subseteq{\mathcal P}(\rho)}$ and a bijection ${f:A\rightarrow\kappa.}$

Note that ${j(A)\subseteq {\mathcal P}^M(j(\rho))={\mathcal P}^M(\rho)\subseteq{\mathcal P}(\rho).}$ Suppose that ${x\in j(A).}$ Then ${x\subseteq\rho}$ and ${j(x)\subseteq\rho}$ and for any ${\beta<\rho,}$ ${\beta\in x}$ iff ${j(\beta)=\beta\in j(x),}$ so ${x=j(x).}$ It follows that ${x\in A}$ and ${j(A)\subseteq A.}$ On the other hand, if ${y\in A,}$ then ${y=j(y)\in j(A),}$ and we have shown that ${j(A)=A}$ .

Also, ${j(f)(x)=j(f)(j(x))=j(f(x))=f(x)}$ for any ${x\in A,}$ since ${f(x)<kappa.}$ It follows that ${j(f)=f,}$ and we have shown that ${\kappa={\rm ran}(f)}$ is fixed by ${j,}$ contradiction. $\Box$

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 ${j:V \rightarrow M}$ be elementary and let ${\kappa={\rm cp}(j).}$ Then ${\kappa}$ is the ${\kappa}$ -th strongly inaccessible cardinal.

Proof: ${\kappa}$ is strongly inaccessible in ${V}$ by Lemma 14 and therefore in ${M}$ since ${M\subseteq V.}$ It follows that, for any ${\alpha<\kappa,}$ there is in ${M}$ some inaccessible larger than ${\alpha}$ and below ${j(\kappa),}$ namely, ${\kappa.}$ By elementarity, the inaccessible cardinals below ${\kappa}$ are unbounded in ${\kappa.}$ $\Box$

The argument gives much more. For example, ${\kappa}$ is inaccessible and limit of inaccessible cardinals, so the same proof shows that ${\kappa}$ is limit of inaccessible cardinals that are themselves the limit of inaccessible cardinals that are limit of inaccessible cardinals $\dots$ Even more is true, i.e., we can diagonalize and continue. This requires a new key idea.

Theorem 16 (Keisler) If ${j:V \rightarrow M}$ is elementary, then ${\kappa={\rm cp}(j)}$ is measurable.

Proof: Let

$\displaystyle {\mathcal U}=\{X\subseteq\kappa : \kappa\in j(X)\}.$

Then ${{\mathcal U}}$ is a nonprincipal ultrafilter over ${\kappa}$ :

If ${X\subseteq Y\subseteq \kappa}$ and ${X\in{\mathcal U}}$ then ${Y\in{\mathcal U}}$ since ${j(X)\subseteq j(Y).}$
${{\mathcal U}}$ is closed under intersections since ${j(A\cap B)=j(A)\cap j(B).}$
${\emptyset=j(\emptyset),}$ so ${\emptyset\notin{\mathcal U}.}$
If ${A\subseteq\kappa}$ then ${j(\kappa)=j(A)\cup j(\kappa\setminus A),}$ so either ${A}$ or ${\kappa\setminus A}$ is in ${{\mathcal U}.}$
If ${\alpha<\kappa,}$ then ${\kappa \notin \{\alpha\} = j(\{\alpha\})}$ so ${{\mathcal U}}$ is nonprincipal.

In fact, ${{\mathcal U}}$ is ${kappa}$ -complete: Let ${\gamma<\kappa}$ and let ${f:\gamma \rightarrow {\mathcal U}.}$ Then ${j(\bigcap_{\alpha<\gamma}f(\alpha))=\bigcap_{\alpha<j(\gamma)}j(f)(\alpha).}$ But ${\gamma=j(\gamma)}$ and therefore ${j(f)(\alpha)=j(f)(j(\alpha)=j(f(\alpha))}$ for all such ${\alpha.}$ It follows that ${\kappa \in j(\bigcap_{\alpha<\gamma}f(\alpha)).}$ $\Box$

The ultrafilter found by Keisler is particularly nice, since it is normal: Using the same notation as above, suppose that ${(X_\alpha:\alpha<\kappa)}$ is a sequence of elements of ${{\mathcal U}.}$ Let ${f:\kappa \rightarrow {\mathcal U}}$ be the map ${f(\alpha)=X_\alpha.}$ Recall that ${\bigtriangleup_\alpha X_\alpha=\{\beta<\kappa : \forall\alpha<\beta\, (\beta \in X_\alpha)\}.}$ Then ${\kappa\in j(\bigtriangleup_\alpha X_\alpha)}$ iff for all ${\alpha<\kappa,}$ ${\kappa\in j(f)(\alpha).}$ But ${j(f)(\alpha)=j(f(\alpha))=j(X_\alpha),}$ and we are done.

Notice that ${{\mathcal U}}$ extends the club filter. This follows either from general arguments about normal filters, or simply by noticing that if ${C\subseteq \kappa}$ is club, then ${\kappa \in j(C)}$ because ${j(C)\ cap \kappa=C}$ is unbounded in ${\kappa}$ and ${j(C)}$ is closed.

(To see that if ${{\mathcal F}}$ is a normal filter on ${\kappa,}$ that contains the cobounded sets then it is ${\kappa}$ -complete, given ${\gamma<\kappa}$ and a sequence ${(X_\alpha : \alpha<\gamma),}$ extend it to a ${\kappa}$ -sequence by setting ${X_\alpha=\kappa}$ for all ${\alpha\ge\gamma,}$ and notice that ${\bigtriangleup_{\alpha<\kappa} X_\alpha=A\cup\bigcap_{\alpha<\gamma}X_\alpha,}$ where ${A\subseteq \gamma.}$ Since ${\kappa \setminus A \in{\mathcal F},}$ it follows that ${\bigcap_{\alpha<\gamma} X_\alpha \in{\mathcal F}}$ as claimed.)

Corollary 17 If ${\kappa}$ is measurable, then there is a nonprincipal normal ultrafilter on ${\kappa}$ (extending the filter of cobounded sets). ${\Box}$

Recall:

Definition 18 A cardinal ${\kappa}$ of uncountable cofinality is Mahlo iff the set of inaccessible cardinals below ${\kappa}$ is stationary.

It follows from the definition that if ${\kappa}$ is Mahlo then it is regular: Suppose that ${X\subseteq\kappa}$ is unbounded and ${|X|<\kappa.}$ Let ${C}$ be the club of limit points of ${X\setminus|X|.}$ Then ${C}$ contains no inaccessible cardinals, in fact, it contains no regular cardinals, contradiction. It also follows that ${\kappa}$ is strong limit, since it is a limit of strong limit (in fact, inaccessible) cardinals. Thus, ${\kappa}$ is the ${\kappa}$ -th inaccessible, and an easy diagonal argument shows it is limit of inaccessible cardinals that are limit of inaccessible cardinals, etc.

Corollary 19 If ${\kappa}$ is measurable then it is the ${\kappa}$ -th Mahlo cardinal.

Proof: If ${j:V\rightarrow M}$ is elementary and ${{\rm cp}(j)=\kappa,}$ then ${\kappa\in j(C)}$ for any club ${C\subseteq\kappa.}$ It follows by elementarity that ${C}$ contains an inaccessible cardinal. Hence, ${\kappa}$ is Mahlo. By elementarity, ${C}$ contains a Mahlo cardinal, etc. $\Box$

Stronger conclusions can be derived by taking ${j:V\rightarrow{\rm Ult}(V,{\mathcal U}),}$ where ${{\mathcal U}}$ is normal. This is because of the following observation:

Lemma 20 Let ${{\mathcal U}}$ be a nonprincipal ${\kappa}$ -complete ultrafilter over the measurable cardinal ${\kappa.}$ Then the following are equivalent:

${{\mathcal U}}$ is normal.

Whenever ${X\in{\mathcal U}}$ and ${f:X \rightarrow \kappa}$ is regressive, then there is ${\xi<\kappa}$ such that ${\{\alpha<\kappa: f(\alpha)=\xi\} \in {\mathcal U}.}$

${\pi([{\rm id}])=\kappa}$ where ${[\cdot]}$ denotes (Scott) classes in ${V^\kappa/{\mathcal U}.}$

Proof: From normality of ${{\mathcal U}}$ we get a version of Fodor’s lemma just as before, so 1 implies 2.

2 implies 3, since 2 says that if ${[f]\hat\in[{\rm id}]}$ then ${[f]=[c_\xi]}$ for some ${\xi<\kappa.}$

3 implies 1, because given any ${X\subseteq\kappa,}$ we have that ${\kappa\in i_{\mathcal U}(X)}$ iff ${[{\rm id}]\hat\in[c_X]}$ iff ${\{\alpha<\kappa : {\rm id}(\alpha)\in c_X(\alpha)\} \in {\mathcal U}}$ iff ${X\in{\mathcal U},}$ so ${{\mathcal U}}$ is the ultrafilter derived from the embedding ${j:V \rightarrow{\rm Ult}(V,{\mathcal U}),}$ which is normal by the remark following Keisler's Theorem 16. $\Box$

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 ${{\mathcal U}}$ be a ${\kappa}$ -complete nonpricipal ultrafilter over the measurable cardinal ${\kappa,}$ and let ${j:V \rightarrow{\rm Ult}(V,{\mathcal U})}$ be the corresponding ultrapower embedding. To ease notation, write ${M}$ instead of ${{\rm Ult}(V,{\mathcal U}).}$ Then:

${{\rm cp}(j)=\kappa.}$

${{}^\kappa M \subseteq M,}$ ${V_{\kappa+1}\subset M,}$ and ${(\kappa^+)^M=\kappa^+.}$

${{}^{\kappa^+}M \not\subseteq M.}$

${{\mathcal U} \notin M}$ so ${V_{\kappa+2} \not \subset M.}$

${2^\kappa \le(2^\kappa)^M<j(\kappa)<(2^\kappa)^+.}$

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 ${V}$ and ${M={\rm Ult}(V,{\mathcal U}),}$ ${M}$ is not closed under ${\kappa^+}$ -sequences and does not contain ${V_{\kappa+2},}$ and ${j(\kappa)}$ 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 ${V_{\kappa+2}\subset M}$ for some elementary ${j:V\to M}$ with ${{\rm cp}(j)=\kappa,}$ then $\kappa$ is measurable in $M$ and therefore there is a normal ultrafilter ${{\mathcal V}}$ over $\kappa$ that concentrates on measurable cardinals, i.e., ${\{\alpha<\kappa : \alpha}$ is measurable ${\}\in{\mathcal V}.}$ ) The modern template for defining large cardinals stipulates the existence of embeddings ${j:V \rightarrow M}$ with large resemblance between ${V}$ and ${M}$ and stronger “correctness'' of ${j.}$ It is natural to wonder how much resemblance can be asked. Kunen showed, for example, that ${M=V}$ is impossible.

Proof: We already know from Corollary 11 that ${{\rm cp}(j) \le \kappa.}$ If ${\alpha={\rm cp}(j)<\kappa,}$ let ${f:\kappa \rightarrow V}$ be such that ${\pi([f])=\alpha.}$ Then ${\{\beta<\kappa : f(\beta) < c_\alpha(\beta)\} = \{\beta : f(\beta) < \alpha)\} \in {\mathcal U}.}$ By ${\kappa}$ -completeness, ${f=_{\mathcal U}c_\beta}$ for some ${\beta<\alpha}$ , so ${j(\beta)=\pi([f])=\alpha,}$ and ${{\rm cp}(j) \le \beta,}$ contradiction. This proves 1.

If ${A\in V_\kappa,}$ then an easy argument as in the proof of Lemma 14 gives that ${A=j(A),}$ so ${V_\kappa=V_\kappa^M.}$ If ${A \subseteq V_\kappa,}$ then it follows that ${A=j(A) \cap V_\kappa}$ and therefore ${V_{\kappa+1}=V_{\kappa+1}^M \in M.}$

Note that any well-ordering of ${\kappa}$ is a subset of ${\kappa\times\kappa}$ and can be identified with a subset of ${\kappa.}$ Since ${V_{\kappa+1}\in M,}$ all these subsets are in ${M,}$ and ${M}$ computes ${\kappa^+}$ correctly.

To show that ${{}^\kappa M \subset M,}$ suppose more generally that ${j[x]:=\{ j(a) :a \in x\} \in M}$ for some ${x}$ and that ${y \subseteq M,}$ where ${|y|\le|x|,}$ and conclude that ${y\in M.}$ This gives the result, since ${j[\kappa]=\kappa.}$

To see the claim, say ${y=\{\pi([f_z]) : z\in x\}}$ and let ${h:j[x]\rightarrow y}$ be the map ${h(j(z))=\pi([f_z]).}$ It is easy to see that ${h}$ is well defined. If ${h\in M,}$ then ${y\in M}$ also, since ${y={\rm ran}(h).}$ To see that ${h\in M,}$ we find some ${F}$ such that ${h=\pi([F]).}$ To do this, note that since ${j[x]\in M,}$ there is some ${f}$ such that ${\pi([f])=j[x],}$ and set ${F:\kappa \rightarrow V}$ to be the function such that, for all ${\alpha<\kappa,}$ ${F(\alpha):f(\alpha) \rightarrow V}$ is the map ${F(\alpha)(z)=f_z(\alpha),}$ whenever this makes sense, and ${F(\alpha)=\emptyset}$ otherwise. It is easy to check that, indeed, ${\pi([F])=h.}$ This proves 2.

On the other hand, ${j[\kappa^+] \notin M,}$ which proves 3. To see this, note that if ${\pi([f])<j(\kappa^+),}$ then ${f=_{\mathcal U}f'}$ for some ${f':\kappa \rightarrow \kappa^+.}$ By regularity of ${\kappa^+,}$ ${f'}$ is bounded, so there is some ${\alpha<\kappa^+}$ such that ${\pi([f])j(\kappa)}$ and ${j(\kappa)>\kappa}$ is a limit cardinal of ${M,}$ so in fact ${j(\kappa)>\kappa^+,}$ since ${\kappa^+=(\kappa^+)^M.}$ Hence, ${j(\kappa^+)>\kappa^+.}$ We are done, since ${j(\kappa^+)}$ is regular from the point of view of ${M,}$ by elementarity.

Now we prove 5: First, ${{\mathcal P}(\kappa)={\mathcal P}^M(\kappa).}$ Since ${M\subseteq V,}$ it follows that ${2^\kappa\le(2^\kappa)^M.}$ Since ${j(\kappa)}$ is, from the point of view of ${M,}$ a strong limit cardinal larger than ${\kappa,}$ we must have ${(2^\kappa)^M<j(\kappa).}$ On the other hand, if ${\pi([f])<j(\kappa),}$ then ${f=_{\mathcal U}f'}$ for some ${f':\kappa \rightarrow \kappa,}$ and there are only ${|{}^\kappa \kappa|=2^\kappa}$ many such functions ${f',}$ so only ${2^\kappa}$ many ordinals below ${j(\kappa).}$ Therefore, ${j(\kappa)<(2^\kappa)^+,}$ and 5 follows.

This gives us 4: Since ${{}^\kappa M\subset M,}$ we have ${{}^\kappa\kappa=({}^\kappa\kappa)^M.}$ If ${{\mathcal U}\in M,}$ then we could correctly compute, in ${M,}$ the value of ${j(\kappa),}$ which would prove that ${(2^\kappa)^M<j(\kappa)<((2^\kappa)^+)^M,}$ contradicting the fact that ${j(\kappa)}$ is a cardinal in ${M.}$ $\Box$

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.

This entry was posted on Saturday, March 7th, 2009 at 9:22 am and is filed under 580: Topics in set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to 580 -Cardinal arithmetic (9)

580 -Cardinal arithmetic (10) « Teaching page says:

March 9, 2009 at 7:39 pm

[…] 580 -Cardinal arithmetic (10) Let me begin with a couple of comments that may help clarify some of the results from last lecture. […]

Reply
580 -Cardinal arithmetic (11) « Teaching page says:

March 12, 2009 at 10:55 am

[…] 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 […]

Reply
580 -Cardinal arithmetic (10) « A kind of library says:

January 20, 2013 at 9:46 am

[…] Let me begin with a couple of comments that may help clarify some of the results from last lecture. […]

Reply
580 -Cardinal arithmetic (11) | A kind of library says:

August 5, 2020 at 12:18 pm

[…] 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 […]

Reply

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library