Set theory seminar -Richard Ketchersid: Quasiiterations I. Iteration trees

In October 24-November 14 of 2008, Richard Ketchersid gave a nice series of talks on quasiiterations at the Set Theory Seminar. The theme is to correctly identify `nice’ branches through iteration trees, and to see how difficult it is for a model to compute these branches. Richard presented a prototypical result in this area (due to Woodin) and a nice application (due to Jackson and Ketchersid). This post will be far from self-contained, and only present some of the definitions.

[Edit Sep. 25, 2010: My original intention was to follow this post with two more notes, on Woodin’s result and on the Jackson-Ketchersid theorem, but I never found the time to polish the presentation to a satisfactory level, so instead I will let the interested reader find my drafts at Lucien’s library.]

I’ll assume known the notions of extender and Woodin cardinal, and associated notions like the length or strength of an extender. A good reference for this post is Donald Martin, John Steel, Iteration trees, Journal of the American Mathematical Society 7 (1) 1994, 1-73. As usual, all inaccuracies below are mine. Some of the notions below are slightly simpler than the official definitions. These notions are all due to Donald Martin, John Steel, and Hugh Woodin.

In this post I present the main notions (iteration trees and iterability) and close with a quick result about the height of tree orders. The order I follow is close to Richard’s but it differs from his presentation at a few places.

I. Definitions.

Definition 1. Say that a transitive structure (M,\in,\delta^M) is a (coarse) premouse iff it satisfies {\sf ZC}+\Sigma_2-replacement, and any M-definable F:M|\delta^M\to{\sf ORD}^M is bounded. Here, M|\kappa=(V_\kappa)^M.

The second condition guarantees that Łos’s theorem holds for ultrapower embeddings by extenders from M. A typical example of a coarse premouse is L(V_\delta) where \delta is Woodin, which is the case we will be most interested in. We recall the notion of Woodinness in Definition 9 below.

Definition 2. Call a premouse M suitable iff it has the form L(M|\delta^M), \delta^M is Woodin in M, and no \alpha<\delta^M is Woodin in L(M|\alpha).

Definition 3. A tree order on \theta is <_{\mathcal T} where

  1. <_{\mathcal T}\subseteq < is transitive,
  2. {\mathcal T}-successors are successors,
  3. \beta limit implies that \{\alpha: \alpha <_{\mathcal T}\beta\} is unbounded in \beta.

Notice that by induction it follows that 3. above holds with unbounded strengthened to club. We also call \theta the length of the tree. Tree orders attempt to isolate the combinatorial content of iteration trees. For such a tree order and \alpha+1<\theta, denote by \alpha_* the <_{\mathcal T}-predecessor of \alpha+1. We will get back to tree orders in abstract at the end of this post.

Definition 4. A (coarse) iteration tree {\mathcal T} on M is

{\mathcal T}=(T,\langle E_\alpha:\alpha+1<{\rm lh}(T)\rangle,\langle M_\alpha:\alpha<{\rm lh}(T)\rangle)


  1. T is a tree order on \theta={\rm lh}(T).
  2. E_\alpha\in M_\alpha|\delta^{M_\alpha} is a (\kappa_\alpha,\lambda_\alpha)M_\alpha-extender.
  3. M_{\alpha+1}={\rm ult}(M_{\alpha_*},E_\alpha).
  4. For \beta<\theta limit, M_\beta is the direct limit of (M_\alpha:\alpha<_{\mathcal T}\beta).
  5. All the M_\alpha are well-founded.
  6. The strength \rho_\alpha in M_\alpha of E_\alpha is at most \lambda_\alpha.

One proves inductively that along an iteration tree different agreements hold that allow for its clauses to make sense; for example, M_\alpha|\kappa_\alpha+1=M_{\alpha_*}|\kappa_\alpha+1, which implies that clause 3. makes sense. One also has the following inequality:

\sup\{\kappa_\alpha:\alpha_*\le\gamma<\alpha\}\le\rho_\gamma. (1)

Definition 5. If {\mathcal T} is as above and the left hand side of (1) +2 is still below \rho_\gamma, we say that {\mathcal T} is a +2-tree.

The trees one is interested in practice are all +2-trees.

Definition 6. An iteration tree {\mathcal T} is normal iff there are \nu_\alpha, \alpha<\theta, such that

  1. \nu_\alpha+2\le\rho_\alpha and \alpha<\beta implies \nu_\alpha<\nu_\beta,
  2. \kappa_\alpha<\nu_{\alpha_*},
  3. \alpha_* is the least \gamma such that \kappa_\alpha<\nu_\gamma.

Usually a tree satisfying items 1 and 2 is called normal, and trees that moreover satisfy 3 are called maximal. We will use maximal for a different notion (see Definition 12). Item 3 is somewhat stronger than requiring that \alpha_* is the least \gamma such that {\rm ult}(M_\gamma,E_\alpha) is defined. Normal trees and transfinite stacks of +2-trees are +2-trees. A stack is a \mu-sequence of iteration trees ({\mathcal T}_\alpha:\alpha<\mu) for some \mu, with {\mathcal T}_\alpha a tree on some premouse N_\alpha, each tree {\mathcal T}_\alpha (other than the last one, if \mu is a successor) having a last model P_\alpha, with N_{\alpha+1}=P_\alpha for all \alpha+1<\mu. Note that a stack can be naturally seen as a tree.

One of the main notions one is interested in when considering premice is iterability. It is now customary to describe iterability in terms of a game.

Definition 7. M is normally \xi-iterable iff player II has a winning strategy in the game G(M,\xi). In this game, players I and II collaborate to produce an iteration tree on M by playing as follows:

  1. The game starts at stage 1. At successor stages \alpha+1<\xi, player I plays either \nu_\alpha,E_\alpha\in M_\alpha, or {\tt end}.
  2. If player I ever plays {\tt end}, player I loses and the game concludes.
  3. \nu_\beta<\nu_\alpha for all \beta<\alpha, or else player I loses and the game concludes.
  4. Letting \alpha_* be the least \gamma such that \kappa_\alpha<\nu_\gamma, player II loses and the game concludes if {\rm ult}(M_{\alpha_*},E_\alpha) is illfounded.
  5. At limit stages \lambda<\xi, player II plays a cofinal well-founded branch of the tree produced so far. If this is not possible, player II loses and the game concludes.
  6. If the game lasts \xi stages, player II wins.

Definition 8. For \zeta a limit ordinal, the game G(M,\xi,\zeta) consists of \zeta rounds of the games G(\cdot,\xi), where

  1. At round 0, M_0=M and players I and II play G(M_0,\xi).
  2. For all \alpha+1<\zeta, the game G(M_\alpha,\xi) ends because player I plays {\tt end} (else, player I loses and the game ends). Hence, the tree built at this round has a top model that we set as M_{\alpha+1}.
  3. At limit stages \gamma\le\zeta, the sequence (M_\alpha:\alpha<\gamma) has a natural direct limit M_\gamma. If M_\gamma is not well-founded, player II loses and the game ends.

The game that we are most interested in is G(M,\omega_1+1,\omega_1). As with the game G(M,\xi), there is a natural notion of iterability associated to a model M iff player II has a winning strategy in G(M,\xi,\theta).

The following is the main theorem from which iterability can be deduced.

Theorem. (Martin, Steel, 85). Suppose (V_\alpha,\delta) is a premouse, \pi:M\to V_\alpha is elementary, and \delta\in{\rm ran}(\pi), so (M,\pi^{-1}(\delta)) is a premouse. (For example, M could be the transitive collapse of an elementary substructure of V_\alpha, with \pi being the inverse of the collapse.)

Suppose that {\mathcal T} is a countable +2-tree on M. Then either

  1. {\mathcal T} has a maximal branch b such that if M_b is the corresponding direct limit model and j:M\to M_b is the corresponding embedding, then there is an elementary map k:M_\beta\to V_\alpha such that the natural diagram commutes, i.e., k\circ j=\pi. In particular, M_b is well-founded. We say that b is a \pi-realizable maximal branch.
  2. Or else there is no such b and {\rm lh}({\mathcal T})=\alpha+1, so there is a last model M_\alpha, and for any “appropriate move (E_\alpha,\nu_\alpha,\alpha_*) for player I,” if j:M\to M_{\alpha_*} is the natural embedding along {\mathcal T}, and i_\alpha:M_{\alpha_*}\to{\rm ult}(M_{\alpha_*},E_\alpha) is the corresponding ultrapower embedding, then there is an elementary map k:{\rm ult}(M_{\alpha_*}, E_\alpha) \to V_\alpha such that the natural diagram commutes, i.e., k\circ i_\alpha\circ j=\pi. In particular, M_\alpha is well-founded.

Notice that in 1., b could fail to be cofinal, or there could be more than one possible b. The result gives appropriate iterability of models that embed into V. This iterability guarantees uniqueness and cofinality.

Definition 9. A cardinal \delta is Woodin with respect to {\mathfrak A}\subseteq{\mathcal P}(\delta) iff \delta is inaccessible and for all A\in{\mathfrak A} there is a \kappa<\delta such that \kappa is <\delta\mbox{-}Astrong, i.e., for all \lambda<\delta there is an embedding j:V\to M with critical point \kappa  such that V_\lambda\in M and j(A)\cap\lambda=A\cap\lambda.

If {\mathfrak A}={\mathcal P}(\delta), we simply say that \delta is Woodin. We say that \delta is \Sigma^1_2-Woodin iff L(V_\delta)\models\delta is Woodin. The name comes from descriptive set theory, recalling the fact that for reals x,y,

x\in L[y] iff x\in C_{\Sigma^1_2}(y).

One can show that if {\mathfrak A}={\mathcal P}(\delta) (i.e., if \delta is Woodin), then the clause stating that \delta is inaccessible is redundant.

Given \delta Woodin and A\subseteq\delta, let

S_A=\{\kappa<\delta:\kappa is <\deltaA-strong\}.

Then \{S_A:A\subseteq\delta\} generates a normal filter on \delta.

Definition 10. Given {\mathcal T} an iteration tree of limit length \theta, let \rho[\alpha,\theta)=\inf\{\rho_\gamma:\alpha\le\gamma<\theta\}, and set \delta({\mathcal T})=\sup\{\rho[\alpha,\theta):\alpha<\theta\}.

One can show that if \delta({\mathcal T})\subseteq{\rm wfp}(M^{\mathcal T}_b) for some cofinal branch b, then for any \gamma<\delta({\mathcal T}) and cofinally many \alpha<\theta, we have M_\alpha|\gamma=M_b|\gamma. Here, {\rm wfp}(M) denotes the well-founded part of the model M, which we always identify with its transitive collapse.

Definition 11. For {\mathcal T} and b as above, the common part model M({\mathcal T}) is \bigcup_{\gamma<\delta({\mathcal T})}M_b|\gamma.

One can show that, as long as {\mathcal T} is normal, there is always one such branch b and M({\mathcal T}) is independent of the choice of such a branch. Moreover, for all \gamma<\delta({\mathcal T}) there is \alpha_0<\theta such that whenever \alpha,\beta>\alpha_0, then in fact M_\alpha|\gamma=M_\beta|\gamma, and this common value coincides with M({\mathcal T})|\gamma.

The key relation between iteration trees and Woodin cardinals is the following result:

Theorem. (Martin, Steel). Suppose that b,c are cofinal branches of a limit length iteration tree {\mathcal T}. Suppose that \delta({\mathcal T})\in{\rm wfp}(M_b)\cap{\rm wfp}(M_c). Then \delta({\mathcal T}) is Woodin with respect to M_b\cap M_c\cap {\mathcal P}(\delta({\mathcal T})), so (M({\mathcal T}),A)\models S_A\ne\emptyset for all A\in M_b \cap M_c \cap {\mathcal P}(\delta({\mathcal T})).

Definition 12. A normal iteration tree {\mathcal T} on a suitable premouse M is called maximal iff L(M({\mathcal T}))\models\delta({\mathcal T}) is Woodin. We say that it is short iff no initial segment of {\mathcal T} is maximal.

Woodin showed that, in a precise sense, there is not much leeway in the computation of cofinal wellfounded branches (through short trees on suitable models), and it is here that quasiiterations (an early version of generic iterations) first appeared.

Theorem (Woodin). Let (M,\vartriangleleft_M) be suitable and assume that \delta^M is inaccessible in M and \vartriangleleft_M is a well-ordering of M. Let {\mathcal T} be a normal short tree on M. Then there is at most one cofinal wellfounded branch b_{\mathcal T}. Moreover, either

  1. b_{\mathcal T} exists and belongs to L(M,{\mathcal T}),  or else
  2. {\mathcal T} is maximal. If this is the case, and b_{\mathcal T} and (M,{\mathcal T})^\sharp exist, then b_{\mathcal T} in L((M,{\mathcal T})^\sharp).

I want to close this post with a couple of observations about tree orders.

II. The height of tree orders.

Recall the notion of tree order, from Definition 3. It intends  to capture the combinatorial structure of iteration trees, introduced in Definition 4. Two natural questions come to mind:

Question 1. Assume that <_{\mathcal T} is a tree order on the regular cardinal \theta. Is it necessarily the case that <_{\mathcal T} has height \theta?

This would certainly be the case if the tree order comes from an iteration tree on an iterable model, so one could also ask:

Question 2. Does every tree order come from an iteration tree?

Alessandro Andretta, Building Iteration Trees, The Journal of Symbolic Logic, 56 (4), (Dec., 1991), 1369-1384, settles question 2:

Theorem. (Andretta). Assume that \delta is Woodin. Then for every limit \lambda<\delta, every tree order on \lambda with a cofinal branch is the tree order of an iteration tree on V.

Andretta’s result has the extra hypothesis of the existence of a cofinal branch, but this is to be expected if the underlying model is iterable. Allowing the use of long extenders, Neeman and others have shown that there are trees (of length \omega) on V without cofinal branches. Question 2 is still open in this generality.

In general, the answer to Question 1 is no. For \omega_1, the following is an example of a tree order on \omega_1 of height \omega+1. This is the shortest possible height, since limit ordinals need to appear at limit levels. This construction is a slight variation due to Ketchersid of an example suggested by Paul Larson:

Let c=(c_\alpha : \alpha\in\omega_1\cap{\rm Lim}) be a ladder system, i.e., c_\alpha is a cofinal subset of \alpha of order type \omega. Let \{c_\alpha(n) :n\in\omega\} be the increasing enumeration of c_\alpha. Then, definably from c, we can construct a tree order on \omega_1 of height \omega+1.

The key observation is Cantor’s result that every ordinal \alpha has a unique representation in the form


where \alpha\ge\beta_0>\dots>\beta_i and 0<n_j for all j\le i. We define a tree based on this representation.

For \alpha a limit ordinal as above, set \beta=\beta_i, n=n_i, and let \gamma<\alpha be the unique ordinal such that \alpha=\gamma+\omega^\beta. We associate to \alpha a branch b_\alpha.

Case 1. \beta>0 is limit. Then set

b_\alpha (i)=\gamma+\omega^{c_\beta(i)} +\omega^{c_\beta(i-1)} + \dots +\omega^{c_\beta(0)} +1.

Case 2. \beta is a successor, say, \beta=\xi+1. Then set

b_\alpha(i)=\left\{\begin{array}{cl}\gamma+\omega^\xi i +2& \quad\mbox{ if }\xi>0,\\ \gamma+i+3 & \quad \mbox { if }\xi=0.\end{array}\right.

Finally, given a successor ordinal \alpha that does not appear in any of the representations above, we simply set \alpha as an immediate {\mathcal T}-successor of 0, with no {\mathcal T}-successors of its own.

From the uniqueness of Cantor representations, it is straightforward to check that we have defined a tree order on \omega_1 of height \omega+1.


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 )

Facebook photo

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

Connecting to %s

%d bloggers like this: