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.





Commutative Diagram1


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


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:

Commutative Diagram2


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:

Commutative Diagram3


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:


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


Leave a Reply

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

You are commenting using your 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