While working through “The Stationary Tower”, I realized that many of the ingredients needed to prove analytic determinacy form a measurable using homogeneous trees cropped up in the text. Furthermore, one of the main results discussed in “The Stationary Tower” is the theorem of Woodin’s that says, if there exists infinitely many Woodin cardinals with a measurable above, then all games are determined. That result uses the following theorem of Martin and Steel.
Theorem (Martin-Steel): If there exists a measurable cardinal with Woodin cardinals below, then all games are determined.
So, I would like to use this blog to go through the proof of the above theorem. We will begin by (roughly speaking) starting from scratch, and in this post I would like to introduce some of the basic notions and problems when it comes to determinacy of games. We begin by fixing notation, defining the types of games we will be considering.
Given sets and , we will let to denote the collection of functions from to . So, the space of functions from naturals to naturals will be denoted by . We will often confuse the natural number with teh set . Given a finite sequence , we say that is the result of concatenating with . Given a sequence we denote its length by . Given a sequence with , we define .
Definition: We say that is a game tree if is a collection of finite sequences closed under initial segments. That is, if , and (read “ is an initial segment of “), then . The body of , denoted by , is the collection of all infinite branches through . In other words, an -sequence if and only if, for every , the sequence . Given a sequence , we say that is a legal move at in if ( concatenated with ) is an element of . A sequence is terminal, if there is no such that .
We will assume that all of our trees have no terminal points. It turns out that all of the theorems we want to prove go through even without this assumption, but the exposition is a bit messier.
Perhaps the most frequently encountered game tree is the tree of finite sequences of natural numbers, which we will denote by . Here, , the collection of all infinite sequences of natural numbers. We will follow standard abuse of notation, and refer to the space as the reals. Part of the reason is that, even though “the reals”, as we are referring to them, are not homeomorphic to , they are Borel isomorphic to . Here, is Borel isomorphic to simply means that there exists a bijection that preserves Borel sets in both directions. In fact, every seperable, completely metrizable (Polish) space is Borel isomorphic to . For our purposes, we will only need worry that the Borel structure is preserved, and the space is generally easier to work with.
We will define a topology on the space as follows. For a given sequence , we define the basic open set , and define the base for our topology to be . So for a set , if we take the discrete topology on , the product topology on ends up being the same as this tree topology we defined above. In particular, for a set , we can always talk about a tree over as a set of finite sequences with elements in by considering as a subspace of under the product topology.
Let be a game tree, and let be a collection of infinite branches through . Define the Gale-Stewart game over , denoted as follows.
- We have two players, which we will creatively call and . Each player has perfect information in the sense that they can see all plays made prior, and have access to all possible plays that can be made.
- There is an inning for each natural number.
- At Inning , plays some such that .
- At Inning , plays some such that .
- From there, and take turns playing such that, at each stage , the sequence .
- At the end, and have cooperated to create an infinite sequence . We call this sequence a play of the game. We will say that wins this play if , and wins otherwise.
A strategy for is a function from sequences in of even length to legal moves in at those sequences, while a strategy for is a function from sequences in of odd length to legal moves in at those sequences. So for example, given a sequence of even length (this includes the empty sequence), means that the sequence is an element of . In other words, a strategy for a player is simply a recipe for how that player should play the game. A branch is said to be consistent with a strategy for if for every , . The notion is defined similarly for . A strategy for is a winning strategy for in if every play consistent with is in . The notion is analogously defined for . A set is determined if there exists a winning strategy for some player in the game
The main question we will be concerned with is the following.
Question: Given a game tree , and a set , when is the game determined?
Our primary concern will be with the space , but we need this slightly more general setting of game trees in order to simplify the exposition. That is, we will be concerned with games where legal moves are natural numbers, and the payoff set is a collection of -sequences of natural numbers. Of course, we can ask whether or not it’s possible for all sets to be determined. In the presence of AC, the answer is no.
We will work simply in . We begin by noting that, a strategy for any player in this space will be a function from finite length sequences to natural numbers. Thus, there are at most continuum-many strategies. To each strategy, we can associate the set of plays consistent with that strategy, of which there are continuum-many. From there, we diagonalize. Bijectively enumerate the strategies . Pick distinct plays consistent with . Then, at each ordinal , pick distinct plays consistent that are distinct from all previous . Let , and note that contains . But then, given a strategy both and its complement contain a play consistent with , and thus neither player can have a winning strategy.
We may ask ourselves why we care about determinacy here. Looking at the notion of determinacy of a game, if we have a well-defined (in some sense) collection of sets (like closed sets, Borel sets, Analytic sets, etc.) such that all elements of are determined, then we can reasonably conclude that those sets are well-behaved. That is, the existence of winning strategies allows us to say nice things about that set. For example, we will can that fact that all closed subsets of are determined to show that all analytic subsets of the real line have the perfect set property, have the property of Baire, and have the perfect set property. I will talk more about using games to show that sets have nice properties later. For now, I mentioned that closed games are determined. This result turns out to be the crux of most of our determinacy arguments, and the reason we need to go to a more general setting. The idea here is that, when dealing with more complex sets , we will often define an auxiliary game tree and a set such that is closed in , and such that is somehow related to . Then, we will use determinacy of closed games to extract a winning strategy for , and translate that to a winning strategy for the same player in .
Theorem (Gale-Stewart): Let be a game tree, and let be closed. Then the game is determined.
Proof: We simply need that there is a winning strategy for some player. So, assume that player does not have a winning strategy for . We want to use this to construct a winning strategy for in . We will describe such a strategy informally, and it will show that this description actually produces a winning strategy. We begin by noting that, since has no winning strategy, there must be some play such that contains a sequence of the form . Otherwise, could not possibly win, and a the winning strategy for would be to do whatever she wants. So, fix such an . Say plays . Again, there should be some such that contains a sequence of the for otherwise would have a winning strategy.
Continuing inductively in this manner, say we end up with a sequence such that there is a sequence of the form in . Then there should be some such that contains a sequence of the form . Otherwise, would have a winning strategy. At the end, we end up with a play such that for each , there is a sequence containing as a subsequence. But then, since is closed, the limit of this sequence, which is by construction, is also in . Thus, this strategy of that we have described is a winning strategy for .
This shows us that all closed games are determined. In fact, this also tells us that all open games are determined since we can translate a winning strategy for in the game to a winning strategy for in the game . In their original paper, where the above result first appeared, Gale and Stewart concluded by asking whether or not all Borel games are determined. The paper first appeared in 1953, and it took until 1975 to prove that indeed all Borel games are determined, the proof of which is due to D.A Martin. Of course, we can now ask ourselves whether or not we can go further. It turns out that the answer here is a much more delicate maybe. We begin by defining the projective sets. We will work over game trees , and products of game trees (which we can also consider as game trees of -tuples).
Let denote the collection of open subsets of a game tree . In general, when we talk about the sets, we will leave the game tree intentionally ambiguous. We now inductively define the projective hierarchy as follows.
- A set is is if the set is .
- A set is if there is some such that . That is, is the projection of
- We denote the class .
A set is projective if there is some such that . As we already noted, if we have the determinacy of one class of sets, we have the determinacy of the class of its complements. In particular, determinacy is equivalent to determinacy. Now, the question of whether or not all games are determined is a very delicate question. For example, if all such games are determined, then we can show that all sets are Lebesgue measurable. But, if , then there exists a non-measurable set of reals. In fact, we have the following.
Theorem (Martin-Harrington): The hypothesis that all games are determined is equivalent to the existence of for every real .
The object is a bit technical, but we may think of as a collection of natural numbers that codes the construction of . It turns out that one consequence of the existence of is that is very thin with respect to the universe of sets. We will not dig much further into this relationship here, as the point was to demonstrate that going beyond Borel Determinacy is somewhat difficult. One less technical object that gives us the existence of a sharp for every real is a measurable cardinal, which we will be defining later. Our next goal is to define the notion of homogeneously Suslin trees, and use them to prove the analytic determinacy directly from the existence of a measurable cardinal. That is, we will prove the following.
Theorem (Martin): Suppose there exists a measurable cardinal . If is a game tree with , and is , then the game is determined.
At some point, I would also like to show how one gets regularity properties from games. I will probably do that after exhibiting Martin’s proof of analytic determinacy.