A Theorem of Gaifman and Rowbottom

This semester, I plan on trying to work my through Paul Larson’s “The Stationary Tower”. Before tackling that, I decided to just read through some of my notes on ultrapowers, extenders, and elementary embeddings in order to refresh my memory a little bit. While doing this, I came across the following result:


Theorem (Gaifman and Rowbottom):

If there exists a measurable cardinal, then \mathcal{P}(\omega)^L is uncountable.


Now, we certainly know that this result holds (and more) in the presence of 0^\sharp, which is a strictly weaker assumption. That is, “0^\sharp exists” gives us that the uncountable cardinals (in V) form a closed unbounded class of indiscernibles for L, which immediately gives us that L thinks each of these uncountable cardinals is strongly inaccessible. From this it follows that, in particular, \mathcal{P}(\omega)^L is countable. The proof that 0^\sharp gives us this closed unbounded class of indiscernibles be found in Devlin’s “Constructibility” I believe.

However, what’s nice about the above theorem is that the proof is a little more straightforward, and it goes through the machinery of linear iterations. While developing this machinery, we end up proving a special case of the shift lemma, and utilize the technique of comparing iterations. Both of these, in more complicated forms, come up when working with mice, as does the notion of iterability. The idea here is that measurable cardinals allows us to get our hands dirty with many of the basic notions that are important to inner model theory, but without many of the (extremely) technical difficulties.

For those reasons, I want to work through the proof of the Gaifman-Rowbottom theorem in this post. We will begin with the basics of linear iterations, but I will mostly only sketch arguments or provide a references as needed. As usual with this sort of thing, we will be working in Kelley-Morse. Let’s begin by reviewing a few basic properties of measurable cardinals (the proof of the theorem below can be found in Kanamori’s “The Higher Infinite”).


Theorem: Let \kappa be a measurable cardinal, \mathcal{U} be the witnessing ultrafilter, and j:V \rightarrow M be the elementary embedding induced by \mathcal{U}. The following hold:

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

2) {}^{\kappa^+}M\not\subseteq M.

3) \mathcal{U}\notin M, and so V_{\kappa+2}\not\subseteq M.

4) 2^\kappa\leq (2^\kappa)^M <j(\kappa)<2^{\kappa^+}.


Note that conditions 2 and 3 motivate the notions of \lambda-supercompact and \alpha-strong cardinals respectively.

Let \kappa be a measurable cardinal, \mathcal{U} be the witnessing ultrafilter, and j:V \rightarrow M be the ultrapower embedding given by \mathcal{U}. The above theorem tells us that \mathcal{U}\notin M, so \mathcal{U} does not witness that \kappa is measurable in M. By elementarity however, j(\mathcal{U}) witnesses that j(\kappa) is measurable in M. That is M\modelsj(\mathcal{U}) is a \kappa-complete, non-principal ultrafilter over j(\kappa)“. So, we can perform the ultrapower construction inside M with respect to j(\kappa) and j(\mathcal{U}). It turns out that this ultrapower is well-founded, since well-foundedness is absolute between inner models of ZFC (in fact ZF – powerset + collection), and M thinks that the resulting ultrapower is well-founded. So, we may identify this ultrapower with its transitive collapse. Let’s denote this model by M_2,  M by M_1, and V by M_0. Let i_{0,1} denote the ultrapower embedding i_{0,1}: M_0 \rightarrow M_1, and i_{1,2} the ultrapower embedding i_{1,2}: M_1 \rightarrow M_2.

Again, we can repeat this construction inside M_2, and end up with a model M_3, and an ultrapower embedding i_{2,3}: M_2\rightarrow M_3. Continuing in this matter, we end up with sequences \langle M_n : n<\omega \rangle and \langle i_{n,m} : n\leq m <\omega\rangle of ultrapowers and their associated elementary embeddings with the following properties.

1) M_0=V, M_1=\mathrm{Ult}(V, \mathcal{U}), and i_{0,1}:M_0\rightarrow M_1 is the induced ultrapower embedding from V to \mathrm{Ult}(V, \mathcal{U}).

2) For n\leq m\leq k <\omega, i_{n,m}: M_n \rightarrow M_m is an elementary embedding, and i_{n,k}=i_{m,k}\circ i_{n,m}.

3) For n<\omega, M_{n+1}=\mathrm{Ult}(M_n, i_{0,n}(\mathcal{U})), and i_{n,n+1}:M_n\rightarrow M_{n+1} is the induced ultrapower embedding.

At this point, we have a directed system of elementary embeddings, and so we may take the direct limit of this system (if it exists), and end up with a model M_\omega and elementary embeddings i_{n,\omega}: M_n \rightarrow M_\omega. Provided that this model is well-founded, we can identify M_\omega with its transitive collapse, and continue on in this manner, taking ultrapowers at successor stages and direct limits at limit stages, provided that each of the models involved is well-founded. As we noted above, we can rule out ill-foundedness occurring at successor stages, but the absoluteness of well-foundedness, which means we only need to make sure limit stages are well-founded. Another thing to note is that, in order to iterate the ultrapower construction through successor stages, we can work in some H_\theta such that H_\theta\models “ZFC – powerset + collection + \mathcal{U} is a \kappa-complete, non-principal ultrafilter on \kappa + V_{\kappa+1} exists” (collection turns out to be stronger than replacement without the powerset axiom). We will denote this theory by \mathcal{T}_\kappa for the sake of brevity, and note that we may assume that \kappa and \mathcal{U} are a part of our language. We will make use of this later. At this point, we will note that not only do direct limits exist, but they are “unique” in some sense.


Theorem (Existence): Let \langle M_\alpha : \alpha<\gamma \rangle and \langle i_{\alpha, \beta} : \alpha\leq\beta < \gamma \rangle be a directed system of elementary embeddings. Then, there exists some M_\gamma  model in the language of set theory and maps \langle i_{\alpha,\gamma}: \alpha<\gamma \rangle such that

1) Each i_{\alpha,\gamma}: M_\alpha \rightarrow M_\gamma.

2) If \alpha\leq\beta <\gamma, then i_{\alpha,\gamma}= i_{\beta,\gamma}\circ i_{\alpha,\beta}.

3) For each x\in M_\gamma, there is some \alpha<\gamma with x\in\mathrm{ran}(i_{\alpha,\gamma}).

That is, the direct limit of the above system exists.



We begin by constructing the model M_\gamma. We say that f is a thread if it is a function in V with domain \gamma\backslash\beta_f for some \beta_f<\gamma such that for all \alpha<\beta\in\mathrm{dom}(f),we have that f(\alpha)\in M_\alpha and i_{\alpha,\beta}(f(\alpha))=f(\beta). In other words, we may think of f as a thread that runs through \prod_{\beta_f<\alpha<\gamma}M_\alpha in manner that is compatible with the elementary embeddings we are given. Note that one value of f determines the rest of the values of f in its domain. We now define an equivalence relation on threads:


f\sim g \Leftrightarrow (\forall\beta\in\mathrm{dom}(f)\cap\mathrm{dom}(g))(f(\beta)=g(\beta))\Leftrightarrow(\exists\beta)(f(\beta)=g(\beta))

Now, since our system may be a system of (proper) class models, we may use Scott’s trick here. We now define a binary relation on the equivalence classes of threads as follows:


[f]\hat\in[g]\Leftrightarrow (\forall\beta\in\mathrm{dom}(f)\cap\mathrm{dom}(g))(f(\beta)\in(\beta))


Setting \hat M_\gamma equal to the set of threads, we see that our desired model is (\hat M_\gamma;\hat\in). In particular, note that even if \hat M_\gamma is a proper class, the relation \hat\in is still set-like. From this construction, we can see what we want our embeddings to look like. In particular we define \hat i_{\alpha,\gamma} : M_\alpha\rightarrow \hat M_\gamma by the mapping x\mapsto f such that f(\beta)=i_{\alpha,\beta}(x). That this construction satisfies the three desired properties follows from construction.


Theorem (Uniqueness): Let \langle M_\alpha : \alpha<\gamma \rangle and \langle i_{\alpha, \beta} : \alpha\leq\beta < \gamma \rangle be a directed system of elementary embeddings with direct limit M_\gamma. Let i_{\alpha, \gamma}:M_\alpha\rightarrow M_\gamma be the associated elementary embeddings. Furthermore, suppose that there is some model N_\gamma and elementary embeddings j_{\alpha, \gamma}: M_\alpha \rightarrow N_\gamma satisfying j_{\alpha, \gamma}=j_{\beta, \gamma}\circ i_{\alpha, \beta} for \alpha\leq\beta<\gamma. Then, there exists an elementary embedding g: M_\gamma\rightarrow N_\gamma such that j_{\alpha, \gamma}=g\circ i_{\alpha,\gamma}.


Both of the above theorems are proved in the introduction of “The Higher Infinite” and are fairly routine. We will now isolate the notion of linear iterability.


Definition: Let \kappa be a measurable cardinal, and \mathcal{U} be the witnessing measure, and let M\models \mathcal{T}_\kappa. For an ordinal \gamma, we say that the sequences \langle M_\alpha : \alpha<\gamma \rangle, \langle i_{\alpha, \beta} : \alpha\leq\beta <\gamma \rangle, and \langle \mathcal{U}_\alpha : \alpha<\gamma\rangle is a linear iteration of M by \mathcal{U} of length \gamma if the following hold:

1) \langle M_\alpha : \alpha<\gamma \rangle, and \langle i_{\alpha, \beta} : \alpha\leq\beta <\gamma \rangle form a directed system of elementary embeddings.

2) M_0=M, for \alpha<\gamma, M_{\alpha+1}=\mathrm{Ult}(M_\alpha, i_{0,\alpha}(\mathcal{U})), and if \beta<\gamma is a limit ordinal, then M_\beta is the direct limit of the directed system \langle M_\alpha : \alpha<\beta \rangle, and \langle i_{\alpha, \delta} : \alpha\leq\delta <\beta \rangle.

3) For an ordinal \alpha<\gamma, the map i_{\alpha, \alpha+1}: M_\alpha \rightarrow M_{\alpha+1} is the induced ultrapower embedding, and for ordinals \alpha\leq\beta<\gamma with \beta limit, the maps i_{\alpha,\beta}: M_\alpha\rightarrow M_\beta are the direct limit maps defined earlier.

4) For \alpha<\gamma, \mathcal{U}_\alpha=i_{0,\alpha}(\mathcal{U}).

5) For \alpha<\gamma, each M_\alpha is well-founded, and has been identified with its transitive collapse.

We say that M is \gamma-linearly iterable by \mathcal{U} and its images if there exists a linear iteration of M by \mathcal{U} of length \gamma. We say that M is linearly iterable by \mathcal{U} and its images if it is \gamma-linearly iterable for each ordinal \gamma.


At this point, I am going to state (without proof) the two theorems that we need to prove the Gaifman-Rowbottom theorem, and then work through the proof of that theorem. I want to delay the proofs regarding linear iterability to the next post because I don’t want this post to get too long, and this seems like a nice division (maybe). Plus, I want to mention something about mice for L[x] for a real x, and a discussion of linear iterability seems like a good transition. We’ll see if that actually works out.


Theorem (Gaifman): Let \kappa be a cardinal such that there is a \kappa-complete, non-principal ultrafilter \mathcal{U} on \kappa, and let \mathfrak{M}=(M;\in;\mathcal{U};\kappa)\models\mathcal{T}_\kappa. Then, \mathfrak M is linearly iterable by \mathcal{U} and its images.


Theorem (Jensen): Let \kappa and \mathcal{U} be as above. M is linearly iterable if and only if, for every countable transitive N with a \mathcal{V}\in N such that there is an elementary \pi : N\rightarrow M with \pi(\mathcal{V})=\mathcal U, N is \omega_1-iterable.


The proofs of the above theorems are actually rather nice, and use some fun machinery. It seems worth it to prove those two theorems in a seperate post. Now, we will prove the Gaifman-Rowbottom theorem.


Theorem (Gaifman and Rowbottom): If there exists a measurable cardinal, then \mathcal{P}(\omega)^L is uncountable.



Let \kappa be measurable, and fix a witness \mathcal{U} to the measurability of \kappa. We begin by noting that, by the above results, V is iterably by \mathcal U, and we may reflect down to some H_\lambda such that H_\lambda\models \mathcal{T}_\kappa. Let M be countable, transitive such that there is some elementary embedding \pi: M \rightarrow H_\lambda and some \mathcal V\in M with \pi(\mathcal{V})=\mathcal U. Then, by Jensen’s result above, M is \omega_1-linearly iterable by \mathcal{V}, and it follows that the direct limit M_{\omega_1} is well-founded, and we may identify it with its transitive collapse.

To see this, suppose otherwise, i.e. that there is some sequence \ldots\hat\in[f_1]\hat\in[f_0] of elements in M_{\omega_1}. Fixing representatives of these equivalence classes, there is then some ordinal \alpha<\omega_1 such that \alpha\in\bigcap\mathrm{dom}(f_n). But then we have that \ldots\in f_1(\alpha)\in f_0(\alpha), which is a contradiction. Thus, we have a sequence of iterates of M by \mathcal{V} of length \omega_1+1. Next, note that the sequence \langle \kappa_\alpha=\mathrm{crit}(j_{\alpha,\alpha+1} : \alpha<\omega_1)\rangle is a length \omega_1 increasing sequence of ordinals and therefore that \mathrm{ON}^{M_{\omega_1}}\geq\omega_1.

Next, recall that L^{M_{\omega_1}}=L_{\mathrm{ON}^{M_{\omega_1}}}\supseteq L_{\omega_1}, and therefore we have that \mathcal{P}(\omega)^L\subseteq M_{\omega}. Additionally, note that for any \alpha<\omega_1, and any \gamma<\kappa_0, we have (V_\gamma)^{M_\alpha}=(V_\gamma)^{M_{\alpha+1}}. However, this tells us that \mathcal{P}(\omega)^L\subseteq \mathcal{P}(\omega)^{M_{\omega_1}}=\mathcal{P}(\omega)^M. But since M is countable, we see that \mathcal{P}(\omega)^L is countable as well.


Here, we see a nice application of the machinery of iterated ultrapowers. With that in mind, I want discuss iterations a bit more in the next post by actually proving Gaifman’s and Jensen’s theorems, and showing how we can generalize these tools. Also, my notes on iterated ultrapowers are based on notes by my Masters Thesis advisor, Andrés Caicedo at Boise State University. I’ll see if I can find a public copy of those notes, as they’re much better than my blog post explanations.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s