Basics of Determinacy

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 $L(\mathbb{R})$ games are determined. That result uses the following theorem of Martin and Steel.

Theorem (Martin-Steel): If there exists a measurable cardinal with $n$ Woodin cardinals below, then all $\bf{\Pi}^1_{n+1}$ 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 $A$ and $B$, we will let ${}^A B$ to denote the collection of functions from $A$ to $B$. So, the space of functions from naturals to naturals will be denoted by ${}^\omega\omega$. We will often confuse the natural number $n$ with teh set $\{0,1,\ldots, n-1\}$. Given a finite sequence $p=\langle p(0), p(1),\ldots, p(n) \rangle$, we say that $p\frown a=\langle p(0), p(1),\ldots, p(n), a \rangle$ is the result of concatenating $p$ with $a$. Given a sequence $p$ we denote its length by $lh(p)$. Given a sequence $p$ with $lh(p)>n$, we define $p\upharpoonright n=\langle p(0), p(1),\ldots, p(n-1)\rangle$.

Definition: We say that $T$ is a game tree if $T$ is a collection of finite sequences closed under initial segments. That is, if $p\in T$, and $q\subseteq p$ (read “$q$ is an initial segment of $p$“), then $q\in T$. The body of $T$, denoted by $[T]$, is the collection of all infinite branches through $T$. In other words, an $\omega$-sequence $x\in T$ if and only if, for every $n<\omega$, the sequence $x\upharpoonright n\in T$. Given a sequence $p\in T$, we say that $a$ is a legal move at $p$ in $T$ if $p\frown a$ ($p$ concatenated with $a$) is an element of $T$. A sequence $s\in T$ is terminal, if there is no $q\in T$ such that $s\subseteq q$.

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 ${}^{<\omega}\omega$. Here, $[{}^{<\omega}\omega]={}^\omega\omega$, the collection of all infinite sequences of natural numbers. We will follow standard abuse of notation, and refer to the space ${}^\omega \omega$ as the reals. Part of the reason is that, even though “the reals”, as we are referring to them, are not homeomorphic to $\mathbb{R}$, they are Borel isomorphic to $\mathbb{R}$. Here, $X$ is Borel isomorphic to $Y$ simply means that there exists a bijection $f:X\to Y$ that preserves Borel sets in both directions. In fact, every seperable, completely metrizable (Polish) space is Borel isomorphic to ${}^\omega\omega$. For our purposes, we will only need worry that the Borel structure is preserved, and the space ${}^\omega\omega$ is generally easier to work with.

We will define a topology on the space $[T]$ as follows. For a given sequence $s\in T$, we define the basic open set $B_s=\{x\in [T] : s\subseteq x\}$, and define the base for our topology $\tau$ to be $\mathcal{B}=\{B_s : s\in T\}$. So for a set $X$, if we take the discrete topology on $X$, the product topology on ${}^\omega X$ ends up being the same as this tree topology we defined above. In particular, for a set $X$, we can always talk about a tree $T$ over $X$ as a set of finite sequences with elements in $X$ by considering $[T]$ as a subspace of ${}^\omega X$ under the product topology.

Let $T$ be a game tree, and let $A\subseteq[T]$ be a collection of infinite branches through $T$. Define the Gale-Stewart game over  $A$, denoted $G(A;T)$ as follows.

1. We have two players, which we will creatively call $I$ and $II$. 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.
2. There is an inning for each natural number.
3. At Inning $0$, $I$ plays some $a_0$ such that $\langle a_0 \rangle\in T$.
4. At Inning $1$, $II$ plays some $a_1$ such that $\langle a_0,\ a_1\rangle\in T$.
5. From there, $I$ and $II$ take turns playing $a_0, a_1, \ldots, a_k, a_{k+1},\ldots$ such that, at each stage $n$, the sequence $\langle a_0, a_1,\ldots, a_n\rangle\in T$.
6. At the end, $I$ and $II$ have cooperated to create an infinite sequence $x=\langle a_0, a_1,\ldots, a_k, a_{k+1},\ldots \rangle\in [T]$. We call this sequence a play of the game. We will say that $I$ wins this play if $x\in A$, and $II$ wins otherwise.

A strategy $\sigma$ for $I$ is a function from sequences in $T$ of even length to legal moves in $T$ at those sequences, while a strategy $\tau$ for $II$ is a function from sequences in $T$ of odd length to legal moves in $T$ at those sequences. So for example, given a sequence of even length $p$ (this includes the empty sequence), $\sigma(p)=a$ means that the sequence $p\frown a$ is an element of $T$. In other words, a strategy for a player is simply a recipe for how that player should play the game. A branch $x\in [T]$ is said to be consistent with a strategy $\sigma$ for $I$ if for every $n\in \omega$, $\sigma(x\upharpoonright 2n+1)=x(2n+1)$. The notion is defined similarly for $II$. A strategy $\sigma$ for $I$ is a winning strategy for  $I$ in $G(A;T)$ if every play $x$ consistent with $\sigma$ is in $A$. The notion is analogously defined for $II$. A set $A$ is determined if there exists a winning strategy for some player in the game $G(A;T)$

The main question we will be concerned with is the following.

Question: Given a game tree $T$, and a set $A\subseteq [T]$, when is the game $G(A;T)$ determined?

Our primary concern will be with the space ${}^\omega\omega$, 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 $A$ is a collection of $\omega$-sequences of natural numbers. Of course, we can ask whether or not it’s possible for all sets $A\subseteq {}^\omega \omega$ to be determined. In the presence of AC, the answer is no.

We will work simply in ${}^\omega \omega$. 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 $\{\sigma_\alpha :\alpha<\mathfrak{c}\}$. Pick distinct plays $x_0, y_0$ consistent with $\sigma_0$. Then, at each ordinal $\alpha$, pick distinct plays $x_\alpha, y_\alpha$ consistent $\sigma_\alpha$ that are distinct from all previous $x_\beta, y_\beta$. Let $A=\{x_\alpha : \alpha<\mathfrak{c}\}$, and note that ${}^\omega\omega\setminus A$ contains $\{y_\alpha :\alpha<\mathfrak{c}\}$. But then, given a strategy $\sigma$ both $A$ and its complement contain a play consistent with $\sigma$, 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 $\Gamma$ (like closed sets, Borel sets, Analytic sets, etc.) such that all elements of $\Gamma$ 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 ${}^\omega\omega$ 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 $A\subseteq {}^\omega\omega$, we will often define an auxiliary game tree $T^*$ and a set $A^*\subseteq [T^*]$ such that $A^*$ is closed in $T^*$, and such that $A^*$ is somehow related to $A$. Then, we will use determinacy of closed games to extract a winning strategy for $A^*$, and translate that to a winning strategy for the same player in $A$.

Theorem (Gale-Stewart): Let $T$ be a game tree, and let $A\subseteq [T]$ be closed. Then the game $G(A;T)$ is determined.

Proof: We simply need that there is a winning strategy for some player. So, assume that player $II$ does not have a winning strategy for $G(A;T)$. We want to use this to construct a winning strategy for $I$ in $G(A;T)$. 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 $II$ has no winning strategy, there must be some play $a_0$ such that $A$ contains a sequence of the form $\langle a_0,\ldots\rangle$. Otherwise, $I$ could not possibly win, and a the winning strategy for $II$ would be to do whatever she wants. So, fix such an $a_0$. Say $II$ plays $a_1$. Again, there should be some $a_2$ such that $A$ contains a sequence of the for $\langle a_0,a_1,a_2,\ldots \rangle$ otherwise $II$ would have a winning strategy.

Continuing inductively in this manner, say we end up with a sequence $\langle a_0, a_1,\ldots, a_{2n-1} \rangle$ such that there is a sequence of the form $\langle a_0, a_1,\ldots, a_{2n-2},\ldots \rangle$ in $A$. Then there should be some $a_{2n}$ such that $A$ contains a sequence of the form $\langle a_0, a_1,\ldots, a_{2n-2}, a_{2n-1}, a_{2n}\ldots \rangle$. Otherwise, $II$ would have a winning strategy. At the end, we end up with a play $x=\langle a_0, a_1,\ldots\rangle\in [T]$ such that for each $n$, there is a sequence $f_n\in A$ containing $x\upharpoonright n$ as a subsequence. But then, since $A$ is closed, the limit of this sequence, which is $x$ by construction, is also in $A$. Thus, this strategy of that we have described is a winning strategy for $II$.

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 $I$ in the game $G(A;T)$ to a winning strategy for $II$ in the game $G([T]\setminus A; T)$. 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 $T$, and products of game trees (which we can also consider as game trees of $n$-tuples).

Let ${\bf\Sigma}^1_0\upharpoonright [T]$ denote the collection of open subsets of a game tree $[T]$. In general, when we talk about the ${\bf \Sigma}^1_0$ sets, we will leave the game tree intentionally ambiguous. We now inductively define the projective hierarchy as follows.

1. A set is $A\subseteq [T]$ is ${\bf \Pi}^1_n$ if the set $[T]\setminus A$ is ${\bf \Sigma}^1_n$.
2. A set $A \subseteq [T]$ is ${\bf \Sigma}^1_{n+1}$ if there is some $C\subseteq [T]\times{}^\omega\omega$ such that $A=\{x\in [T] : (\exists y\in {}^\omega\omega)(\langle x,y\rangle\in C)\}$. That is, $A=pC$ is the projection of $C$
3. We denote the class ${\bf\Delta}^1_n={\bf \Sigma}^1_n\cap{\bf\Pi}^1_n$.

A set $A\subseteq [T]$ is projective if there is some $n$ such that $A\in {\bf \Sigma^1_n}$. 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, ${\bf\Pi}^1_n$ determinacy is equivalent to ${\bf\Sigma}^1_n$ determinacy. Now, the question of whether or not all ${\bf \Pi^1_1}$ games are determined is a very delicate question. For example, if all such games are determined, then we can show that all ${\bf\Sigma}^1_2$ sets are Lebesgue measurable. But, if $V=L$, then there exists a non-measurable ${\bf\Sigma}^1_2$ set of reals. In fact, we have the following.

Theorem (Martin-Harrington): The hypothesis that all ${\bf \Pi}^1_1$ games are determined is equivalent to the existence of $x^\sharp$ for every real $x$.

The object $x^\sharp$ is a bit technical, but we may think of $0^\sharp$ as a collection of natural numbers that codes the construction of $L$. It turns out that one consequence of the existence of $0^\sharp$ is that $L$ 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 $\kappa$. If $T$ is a game tree with $|T|<\kappa$, and $A\subseteq [T]$ is ${\bf\Pi}^1_1$, then the game $G(A;T)$ 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.