# 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 .

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\models$$j(\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.

Proof:

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.

Proof:

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.