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

$<_{\mathcal T}\subseteq <$ is transitive,
${\mathcal T}$ -successors are successors,
$\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)$

where

$T$ is a tree order on $\theta={\rm lh}(T)$ .
$E_\alpha\in M_\alpha|\delta^{M_\alpha}$ is a $(\kappa_\alpha,\lambda_\alpha)$ – $M_\alpha$ -extender.
$M_{\alpha+1}={\rm ult}(M_{\alpha_*},E_\alpha)$ .
For $\beta<\theta$ limit, $M_\beta$ is the direct limit of $(M_\alpha:\alpha<_{\mathcal T}\beta)$ .
All the $M_\alpha$ are well-founded.
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

$\nu_\alpha+2\le\rho_\alpha$ and $\alpha<\beta$ implies $\nu_\alpha<\nu_\beta$ ,
$\kappa_\alpha<\nu_{\alpha_*}$ ,
$\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:

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}$ .
If player I ever plays ${\tt end}$ , player I loses and the game concludes.
$\nu_\beta<\nu_\alpha$ for all $\beta<\alpha$ , or else player I loses and the game concludes.
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.
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.
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

At round 0, $M_0=M$ and players I and II play $G(M_0,\xi)$ .
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}$ .
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

${\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.

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{-}A$ –strong, 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 $<\delta$ – $A$ -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

$b_{\mathcal T}$ exists and belongs to $L(M,{\mathcal T})$ , or else

${\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 coﬁnal 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

$\alpha=\omega^{\beta_0}n_0+\dots+\omega^{\beta_i}n_i$

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

This entry was posted on Monday, January 19th, 2009 at 11:55 am and is filed under math.LO, Set theory seminar. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

A kind of library