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.
Definition 1. Say that a transitive structure is a (coarse) premouse iff it satisfies -replacement, and any -definable is bounded. Here, .
The second condition guarantees that Łos’s theorem holds for ultrapower embeddings by extenders from . A typical example of a coarse premouse is where 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 suitable iff it has the form , is Woodin in , and no is Woodin in .
Definition 3. A tree order on is where
- is transitive,
- -successors are successors,
- limit implies that is unbounded in .
Notice that by induction it follows that 3. above holds with unbounded strengthened to club. We also call the length of the tree. Tree orders attempt to isolate the combinatorial content of iteration trees. For such a tree order and , denote by the -predecessor of . We will get back to tree orders in abstract at the end of this post.
Definition 4. A (coarse) iteration tree on is
- is a tree order on .
- is a –-extender.
- For limit, is the direct limit of .
- All the are well-founded.
- The strength in of is at most .
One proves inductively that along an iteration tree different agreements hold that allow for its clauses to make sense; for example, , which implies that clause 3. makes sense. One also has the following inequality:
Definition 5. If is as above and the left hand side of (1) is still below , we say that is a -tree.
The trees one is interested in practice are all -trees.
Definition 6. An iteration tree is normal iff there are , , such that
- and implies ,
- is the least such that .
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 is the least such that is defined. Normal trees and transfinite stacks of -trees are -trees. A stack is a -sequence of iteration trees for some , with a tree on some premouse , each tree (other than the last one, if is a successor) having a last model , with for all . 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. is normally -iterable iff player II has a winning strategy in the game . In this game, players I and II collaborate to produce an iteration tree on by playing as follows:
- The game starts at stage 1. At successor stages , player I plays either , or .
- If player I ever plays , player I loses and the game concludes.
- for all , or else player I loses and the game concludes.
- Letting be the least such that , player II loses and the game concludes if is illfounded.
- At limit stages , 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 stages, player II wins.
Definition 8. For a limit ordinal, the game consists of rounds of the games , where
- At round 0, and players I and II play .
- For all , the game ends because player I plays (else, player I loses and the game ends). Hence, the tree built at this round has a top model that we set as .
- At limit stages , the sequence has a natural direct limit . If is not well-founded, player II loses and the game ends.
The game that we are most interested in is . As with the game , there is a natural notion of iterability associated to a model iff player II has a winning strategy in .
The following is the main theorem from which iterability can be deduced.
Theorem. (Martin, Steel, 85). Suppose is a premouse, is elementary, and , so is a premouse. (For example, could be the transitive collapse of an elementary substructure of , with being the inverse of the collapse.)
Suppose that is a countable -tree on . Then either
- has a maximal branch such that if is the corresponding direct limit model and is the corresponding embedding, then there is an elementary map such that the natural diagram commutes, i.e., . In particular, is well-founded. We say that is a -realizable maximal branch.
- Or else there is no such and , so there is a last model , and for any “appropriate move for player I,” if is the natural embedding along , and is the corresponding ultrapower embedding, then there is an elementary map such that the natural diagram commutes, i.e., . In particular, is well-founded.
Notice that in 1., could fail to be cofinal, or there could be more than one possible . The result gives appropriate iterability of models that embed into . This iterability guarantees uniqueness and cofinality.
Definition 9. A cardinal is Woodin with respect to iff is inaccessible and for all there is a such that is –strong, i.e., for all there is an embedding with critical point such that and .
If , we simply say that is Woodin. We say that is -Woodin iff is Woodin. The name comes from descriptive set theory, recalling the fact that for reals ,
One can show that if (i.e., if is Woodin), then the clause stating that is inaccessible is redundant.
Given Woodin and , let
Then generates a normal filter on .
Definition 10. Given an iteration tree of limit length , let , and set .
One can show that if for some cofinal branch , then for any and cofinally many , we have . Here, denotes the well-founded part of the model , which we always identify with its transitive collapse.
Definition 11. For and as above, the common part model is .
One can show that, as long as is normal, there is always one such branch and is independent of the choice of such a branch. Moreover, for all there is such that whenever , then in fact , and this common value coincides with .
The key relation between iteration trees and Woodin cardinals is the following result:
Theorem. (Martin, Steel). Suppose that are cofinal branches of a limit length iteration tree . Suppose that . Then is Woodin with respect to , so for all .
Definition 12. A normal iteration tree on a suitable premouse is called maximal iff is Woodin. We say that it is short iff no initial segment of 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 be suitable and assume that is inaccessible in and is a well-ordering of . Let be a normal short tree on . Then there is at most one cofinal wellfounded branch . Moreover, either
- exists and belongs to , or else
- is maximal. If this is the case, and and exist, then
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 is a tree order on the regular cardinal . Is it necessarily the case that has height ?
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 is Woodin. Then for every limit , every tree order on with a cofinal branch is the tree order of an iteration tree on .
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 ) on without cofinal branches. Question 2 is still open in this generality.
In general, the answer to Question 1 is no. For , the following is an example of a tree order on of height . 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 be a ladder system, i.e., is a coﬁnal subset of of order type . Let be the increasing enumeration of . Then, definably from , we can construct a tree order on of height .
The key observation is Cantor’s result that every ordinal has a unique representation in the form
where and for all . We deﬁne a tree based on this representation.
For a limit ordinal as above, set , , and let be the unique ordinal such that . We associate to a branch .
Case 1. is limit. Then set
Case 2. is a successor, say, . Then set
Finally, given a successor ordinal that does not appear in any of the representations above, we simply set as an immediate -successor of 0, with no -successors of its own.
From the uniqueness of Cantor representations, it is straightforward to check that we have defined a tree order on of height .