The goal of this post is to prove analytic determinacy form the hypothesis that a measurable cardinal exists. This hypothesis is not optimal, but it is much less technical than the optimal hypothesis. Furthermore, the proof we will give is the “base case” for the inductive proof of projective determinacy from Woodin cardinals.
Definition: For a set , an ultrafilter over is a collection of subsets of with the following properties:
- If , then ;
- If , and , then ;
- For every , either , or .
The first three conditions define a filter, whereas the fourth condition is what makes a filter into an ultrafilter. Given a cardinal , we say that an ultrafilter is -complete if for every , is closed under intersections of length . An ultrafilter is non-principal if it contains no singletons.
Definition: An uncountable cardinal is measurable if there exists a -complete, non-principal ultrafilter over .
The name measurable comes from the fact that such an ultrafilter determines a nontrivial, -additive, binary measure over all of . For more on the measure problem, and the history thereof, the reader may consult Kanamori’s “The Higher Infinite”. It is relatively easy to check that a measurable cardinal is strongly inaccessible, directly from the definition. What is less apparent is that there are many inaccessible cardinals below , and in fact there are stationary many measurable cardinals below . The argument for this uses the fact that taking the ultrapower by V with respect to gives us an elementary embedding with critical point of being . For now, I will push this material to the side, and focus on the combinatorial properties of measurable cardinals.
Definition: Let be an ultrafilter over a cardinal . Such an ultrafilter is uniform if every element of has cardinality . We say that an ultrafilter over a cardinal is normal if for every function such that , there is an ordinal such that .
Lemma: If is a measurable, then there exists a uniform, normal ultrafilter over .
Definition: Let be a set, and let be a cardinal. We define the set .
Theorem (Ramsey): Let be a uniform, normal ultrafilter over a cardinal , then for every , and every , there is some such that either , or .
Using the above theorem of Ramsey, we may define, for any , an ultrafilter over by
Note that if , then each is -complete and non-principal.
We will be black-boxing the above results, but the proofs are fairly standard affair, and can be found in Jech or Kanamori. The main idea here is that we will use these Ramsey ultrafilters to define a tree of ultrafilters that correspond to some analytic subset . Using this tree of measures, we can then show that the game is determined. We will now attempt to make this notion of correspondence more precise by introducing the notion of homogeneously Suslin sets, and homogeneous trees. We will be following the presentation in Martin’s unpublished monograph on determinacy. We begin by fixing some notation.
If are finite sequences of the same length, then we define the sequence
If is a game tree, and is a finite sequence, define
If is a game tree, and if is an infinite sequence, define
Let be a game tree, be a set, and be a tree on . We say that the -projection of is the set . Given an infinite cardinal , and a game tree , we say that a set is -Suslin if it is the -projection of a tree on . That is, for , we have that if and only if . I want to point out that the version of -Suslin is slightly different, but equivalent, to the one that is normally found in texts on descriptive set theory. The reason I’m using this definition is that it’s a bit easier to work with for what I want to do, and it makes the connection to -homogenously Suslin sets more apparent.
We claim that every coanalytic set is -homogeneously Suslin for every uncountable cardinal . In order to see this, we need a more useful, but slightly more complicated representation of coanalytic sets.
Theorem (Representations of sets): Let be a game tree, then is if and only if there is a function with domain such that the following hold.
- For each , is a linear order with greatest element ;
- If are such that , then ;
- For each , if and only if is a well-ordering of .
The above theorem is a less techincal version of a result attributed to Lusin, Sierpinski, and Kleene, a corollary of which is that the pointclass is normed. The existence of a norm on a pointclass gives us some fairly nice closure properties (among other things), and the question of which pointclasses are normed turns out to be closely related to determinacy. Maybe I’ll take the time to discuss normed pointclasses and the First Periodicity Theorem once I’ve finished this project of working through the proof of projective determinacy from Woodins.
The above representation theorem is basically the reason we are working with sets, as it allows us to show that they have quite a few nice properties.
Lemma (Shoenfield): Let be a game tree. If is , then is -Suslin for every uncountable cardinal .
Proof: Fix an uncountable cardinal . Since is coanalytic, we may fix functions and as given by the above representation theorem. Using this, we can define the desired tree by setting
and embeds into .
Here, denotes the usual well order on . So, the idea is that, given some , we know that is a linear order of with greatest element . So, we can thank of an embedding of into as finite sequence consisting of elements from of length such that if and only if .
Now let . If , then embeds into , which witnesses that is a well order of . Thus, . If we now fix some , we have that is a well-order, and so there must be some embedding into . Such a must be in be construction. Therefore, for , if and only if , and so is the -projection of a tree on .
In the presence of a measurable cardinal, we can strengthen the above lemma. In particular, we can show that the coanalytic sets are -Suslin as witnessed by a tree over that is homogeneous in the sense that it corresponds to a system of ultrafilters that “fit” well together. This homogeneity allows us to show that, in the presence of a measurable, coanalytic games are determined. The precise nature of this homogeneity will come from the Ramsey ultrafilters we defined earlier.
Definition: Let be a tree, and be a tree over for some set . Given two sequences , define the projection of to , by . Given two countably complete ultrafilters and over and respectively, we can use the defined projection to define a notion of compatibility between and . We say that projects to if, for every , the set . Given a system of ultrafilters , we say that the ultrafilters are compatible if, whenever , projects to .
Definition: Let be a game tree, a set, and a game tree over . We say that is homogeneous for if there exists a system of ultrafilters such that the following hold.
- Each is a countably complete ultrafilter over ;
- The ultrafilters are compatible;
- Given , and a sequence with for each , then if and only if there is some function such that, for each , .
Additionally, we say that such a tree is -homogeneous for an infinite cardinal if each is -complete.
The idea here is that, in order for this system to satisfy the third condition, it must be homogeneous in some sense. In particular, it tells us that each sequence corresponds to a direct system of elementary embeddings, the direct limit of which is well-founded if and only if . For now, discussing elementary embeddings would take us too far afield, but this does tell us that the system of ultrafilters associated to the -projection of fit well together.
Definition: Let be a game tree, and . We say that is homogeneously Suslin if there exists a tree over for some set such that is homogeneous for and is the projection of . For an infinite cardinal , we say that is -homogeneously Suslin if it is the projection of a -homogeneous tree.
We note that, our definition of -homogeneously Suslin says nothing about how large the set is. So, it may be the case that a set is -homogeneously Suslin without being -Suslin. The reason here is that we want a -homogeneously Suslin set to be -homogeneously Suslin for each cardinal .
Theorem (Martin-Steel): For any game tree , all -homogeneously Suslin games in are determined. That is, if is -homogeneously Suslin, then the game is determined.
Proof: Let be a game tree, and let be -homogeneously Suslin. Let be a set and a game tree on that is -homogeneously Suslin for , and such that . Fix a system that witnesses the -homogeneity of . We will now define an auxiliary game tree by describing the plays in , and a set that is closed in , such that the determinacy of gives us the determinacy of . With that said, let be the game tree in which plays are as follows:
where for each , , and . Let be the collection of all plays such that for each . By definition, is closed in , and thus the game is determined. At this point, we want to translate winning strategies for certain players in this auxiliary game to winning strategies for those same players in the original game.
We begin by defining the projection map by . Note that this induces a continuous surjection, which we will also call . Now, suppose that is determined in favor of , and let be a winning strategy witnessing this. Define a strategy for in by simply removing the second coordinates from ‘s plays in the auxiliary game. That is, we define . Let be a play consistent with the strategy , then by definition, for each , there is some sequence such that . Thus, , and therefore , which means that is winning for in .
Next, assume that the game is determined in favor of . Let be a winning strategy for witnessing this. As before, we want to use this to define a winning strategy for in , but this is a bit more delicate than in the previous case. Whenever makes a play in the original game, has to somehow pick a canonical play for in the game and use that to inform her play in . It is here that we use the fact that is -homogeneously Suslin. For each , and each , let
Each is a position in , and is such that . We now define a strategy for in by setting
Where is of length . The map is well-defined since each is -complete since, at worst, latex $\tau$ could attempt to map to -many different things. But, take the intersection of the witnesses, and it turns out that they agree on a set in the associated ultrafilter, so was in fact not trying to take to -many different things. We claim that is a winning strategy for in . To see this, suppose otherwise. That is, suppose by way of contradiction that there is some that is consistent with . For each , set
and . In other words, each witnesses that and is therefore in , while by definition. Therefore, since is homogeneous, there is some such that for each . This means that the play
is a play in consistent with . But by definition, that means that , which contradicts the fact that is winning for in .
Theorem (Martin-Steel): Let be a game tree. If there exists a measurable cardinal , then every subset is -homogeneously Suslin as witnessed by a tree on .
Proof: Let be a game tree, be a measurable cardinal, be a uniform normal ultrafilter on , and coanalytic. Using the representation theorem for sets, fix maps and as given by that theorem. We will define our tree as we did when proving that sets are -Suslin for every uncountable cardinal . That is, we define
and embeds into .
Let . For each , there is a unique embeds into by way of , and thus such that . We will use these embeddings and the Ramsey ultrafilters above to define the desired system of ultrafilters . Recall that we defined, for each , a -complete ultrafilter over by
Given , we define the ultrafilter on by
That is, a set is in the ultrafilter if and only if the ranges of the elements of are in the corresponding Ramsey ultrafilter. We already have shown that is the -projection of . Furthermore, the system is a system of -complete ultrafilters as we discussed earlier. To see that the ultrafilters are compatible, let , let , and let witness that . Then, there is some such that . Now consider , and let . We then see that , which means that , thus verifying compatibility.
We only need to check the third condition in the definition of homogeneous trees. With that in mind, fix , and let be such that for each . For each , fix the witness that . For each we may, by definition of , fix such that . By -completeness of , let . Of course, we also have that for each , . Suppose that . Then, , and so is a well-order. Let embed into . To see that is the desired witness to homogeneity, let . By definition of and , we have that , and that the range of is in for each . But then we immediately have that for every .
As an immediate corollary to the above two theorems, we have the famous result of Martin’s from 1975.
Theorem (Martin): Let be a game tree. If there exists a measurable cardinal , then for every set , the game is determined.
Okay, so I’m giving a seminar talk about topological games over the real line in a couple of weeks. Because of that, I think the next entry I’m going to do would be about showing how one propagates regularity properties through the projective hierarchy.
Definition: Let be a Polish space, and let . We say that has the perfect set property if either is countable, or there exists a homeomorphic copy of the Cantor space in . We say that has the property of Baire if there exists some open such that is meagre.
In particular, I’d like to start working towards proving the following theorem.
Theorem: Suppose that all games over countable branching trees of countable height are determined, then every set has the perfect set property, has the property of Baire, and is Lebesgue measurable.
In particular, a corollary is the classical result that in ZFC, the sets have the previously mentioned regularity properties.
It can be shown that the above hypothesis is actually optimal, but that requires a bit of inner model theory. Though, I may sketch the result that, if , then there exists a subset of the real line that is uncountable, but contains no homeomorphic copy of the cantor space.