# Finishing up the Gaifman-Rowbottom theorem

In this post, I will work through the proofs of the following theorems. None of these reuslts are mine, and anything I don’t attribute is probably folklore.

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.

Lemma (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.

This will complete the proof of the Gaifman-Rowbottom theorem that we began in the last post. We will end up proving Gaifman’s theorem in a series of lemmas, of which Jensen’s lemma above is one.  We begin by showing that, if we have a model $M$ that is $\gamma$-linearly iterable by $\mathcal{U}$, and we can elementarily embed $N$ into $M$ with $\mathcal{U}$ being the image of some $\mathcal{V}$ in $N$, then we can also iterate the ultrapower construction over $N$ using $\mathcal{U}$. In order to save some typing, we will say that the pair $(M,\mathcal{U})$ is $\gamma$-linearly iterable if $M$ is $\gamma$-linearly iterable by $\mathcal{U}$ and its images.

Lemma: Assume $(P,\mathcal{U})$ is $\gamma$-linearly. Let $(Q,\mathcal{V})$ be such that $Q$ is transitive, and there exists a $\pi: Q\rightarrow P$ elementary such that that $\pi(\mathcal{V})=\mathcal{U}$. Then, $(Q,\mathcal{V})$ is $\gamma$-linearly iterable.

Proof: The basic idea here is to show that one can iterate $(Q,\mathcal{V})$  by iterating $(P,\mathcal{U})$, and using the embedding $\pi$ at each stage to check that the iterates of $(Q,\mathcal{V})$ are well-founded. In other words, setting $Q_0=Q,P_0=P,\pi_0=\pi$, we want to create the following commutative diagram.

Luckily for us, the natural idea works here. We will let $[f]^S_\mathcal{F}$ denote the typical element of the $\mathrm{Ult}(S,\mathcal{F})$. At stage $0$, we already have the map $\pi_0$. So, we want to see where we need to map $[f]^{Q_1}_{\mathcal{V}_1}$, but the obvious thing works here. That is, we set $\pi_1([f]^{Q_1}_{\mathcal{V}_1})$ $=[\pi_0(f)]^{P_1}_{\mathcal{U}_1}$. So in general, for successors, we set $\pi_{\alpha+1}([f]^{Q_\alpha}_{\mathcal{V}_\alpha})=[\pi_\alpha(f)]^{P_\alpha}_{\mathcal{U}_\alpha}$.

At limit stages $\lambda<\gamma$, we set $\pi_\lambda: Q_\lambda\rightarrow P_\lambda$ equal to the map between direct limits we obtained from the uniqueness lemma in the previous post. More specifically, taking the direct limit of the models $P_\alpha$, we end up with some transitive (after taking the Mostowski collapse) $P_\lambda$. But, because we also have corresponding embeddings $\pi_\alpha: P-\alpha\rightarrow Q_\alpha$, we also see that the models $Q_\alpha$ elementarily embed into $P_\lambda$. Thus, taking the direct limit of the models $Q_\alpha$, we end up with a model $Q_\lambda$ and an elementary embedding $\pi\lambda Q_\lambda\rightarrow P_\lambda$.  This gives us that the diagram above commutes with each of the models $P_\alpha$ transitive, and an elementary embedding $\pi_\alpha: Q_\alpha\rightarrow P_\alpha$. But then, each of the models $Q_\alpha$ are well-founded.

We will now prove Jensen’s lemma above.

Proof: The $(\Rightarrow)$ direction of this lemma follows directly from the special case of the shift lemma above. To prove the other direction, assume that $M$ is not linearly iterable, we will show that there is some $N$ countable transitive as in the statement of the lemma that is not $\omega_1$-iterable.

Let $I=\langle M_\alpha, j_{\alpha,\beta} : \alpha\leq\beta<\gamma\rangle$ witness that $M$ is not iterable, i.e. that the direct limit, $M_\gamma$ is ill-founded. By reflection, we may assume that $M_0$ is a set. Now fix a $\lambda$ large enough such that $I\in H_\lambda$, and $H_\lambda\models M\text{ is not linearly iterable''}$. Let $N$ be countable, transitive such that $\pi:N\rightarrow H_\lambda$ is elementary, and such that $\pi(\langle I',M_0',\mathcal{U}'\rangle)=\langle I, M_0, \mathcal{U}\rangle$. But by elementarity, we see that

$N\models I'\text{ is an iteration of } M_0'\text{ by }\mathcal{U}'\text{ with ill-founded direct limit''}$.

Now, as $N$ is a countable transitive model of (at least) $\mathrm{ZF}^-$, we see that the direct limit of $I'$ is in fact ill-founded by absoluteness, and in fact that it is ill-founded at some countable ordinal $\alpha$. But then, we have $\pi\upharpoonright M_0':M_0'\rightarrow M$ elementary with $\pi(\mathcal{U}')=\mathcal U$, and $(M_0',\mathcal{U}')$ not $\omega_1$-linearly iterable.

The above lemma gives us a rather nice corollary when characterizing linear iterability.

Corollary$(M,\mathcal{U})$ is linearly-iterable if and only if it is $\omega_1$-linearly iterable

Proof:

The $(\Rightarrow)$ direction follows from definition.

To prove the other direction, suppose that $M$ is $\omega_1$-linearly iterable, and further suppose, by way of contradiction, that $M$ is not linearly-iterable. If $M$ is a proper class, pick $\lambda$ large enough so that $H_\lambda$ witnesses $M$ is $\omega_1$-linearly iterable, but not linearly-iterable. That is, $(H_\lambda,\in, \mathcal{U}, \kappa)$ is $\omega_1$-linearly iterable, but not linearly iterable. Let $N$ be the countable, transitive model that witnesses failure of linear-iterability of $H_\lambda$ as in Jensen’s lemma, and fix witnessess $\pi:N\rightarrow H_\lambda$ with $\mathcal{V}\in N$ such that $\pi(\mathcal{V})=\mathcal U$. But then, the shift lemma tells us that $(N,\mathcal{V})$ is at least $\omega_1$-linearly iterable, since we picked $\lambda$ large enough to witness that $H_\lambda$ is $\omega_1$-linearly iterable. Thus, we have have a contradiction, and $\omega_1$-linear iterability implies linear-iterability for such models $M$.

The nice part about the above corollary is that, if we have a failure of linear iterability, we know that it must have failed at some countable limit ordinal $\gamma$. We now move to a proof of Gaifman’s theorem.

Proof of Gaifman’s Theorem: Suppose otherwise, that is, suppose that $M$ has some ill-founded direct limit. Fix some $\lambda$ large enough so that $H_\lambda$ witnesses this, and in particular computes the functions that witness ill-foundedness correctly. Let $N$ be countable, transitive with $\pi:N\rightarrow H_\lambda$ such that there is a $\mathcal{U'}\in N$ with $\pi(\mathcal{U}')=\mathcal{U}$. Let $\langle N_\alpha, j_{\alpha,\beta} : \alpha\leq \beta <\omega_1\rangle$ denote the “iterates” of $N=N_0$, we want to show that each of these iterates is well-founded. We will do this by embedding each of them elementarily into $H_\lambda$, which is transitive.

In order to do this, we will construct maps $\pi_\alpha: N_\alpha\rightarrow H_\lambda$ elementary such that $\pi_\alpha=\pi_{\alpha+1}\circ j_{\alpha,\alpha+1}$. In other words, we want to show that the following diagram commutes with each $\pi_\alpha$ elementary:

That will then give us that each $N_\alpha$ is well-founded, and therefore that $N$ is $\omega_1$ iterable giving us the desired contradiction. We will start with $\pi_0=\pi$, and show how one constructs $\pi_1$ from there. It should be clear from the construction how to continue at successor stages. At limit stages, we just take the map defined in the “uniqueness” of direct limits lemma by expanding the above diagram to the following:

Now, with regards to constructing $\pi_1$, let $\gamma\in\bigcap\{X\in\mathrm{ran}(\pi_0): X\in\pi_0(\mathcal{U}'_0)\}$. Note that this intersection is countable, and therefore non-empty. Now define $\pi_1: N_1\rightarrow H_\lambda$ such that:

$\pi_1([f]^{N_0}_{\mathcal{U}'_0})=\pi_0(f)(\gamma)$

It is fairly routine to check that the above map is well-defined, and the initial segment of the above diagram commutes. That completes the proof.

I was planning on naively discussing mice for $L[x]$ where $x$ is a real, but I feel like that would make this post too long. I don’t think I’ll end up talking about them much for now either, as I really should get started on working through the material in “The Stationary Tower”.