I have just learned that Gale-Stewart game is determined for open and closed sets, so naturally I'm interested to understand Borel determinacy which seems to be on a totally different level. What's the minimal set of knowledge to understand Borel determinacy without diving into a standard descriptive set theory textbook?

I know, or have some exposure, to some basics of game theory, set theory, and mathematical logic at an introductory level.


Borel determinacy was proved by Tony Martin. You don't need much if you read the inductive proof, as presented in Kechris's book on Descriptive set theory. Just about the only "technical" notion you need is the concept of tree, which is a collection of finite sequences closed under initial segments, that is, if $\sigma$ is an element of a tree $T$, then $\sigma$ is a finite sequence, and any proper initial segment of $\sigma$ is also an element of $T$.

This proof uses the key idea of "unraveling" of games. It proceeds by transfinite induction. The point is that the Borel sets are naturally stratified in a hierarchy of length $\omega_1$. One can form the stratification in several ways. For example: At the first level you have open sets. At level $\alpha$ you have sets that are countable unions of sets at level before $\alpha$, or their complements (one can refine this a little). What the unraveling does is associate to a Borel set an open set, with an equivalent game, meaning that player I wins the game on the Borel set iff player I wins the game on the open set, and same for player II. This proves determinacy, by the Gale-Stewart result. The technical issue is that the open set is not a subset of the reals, but rather of a much larger space -- something like $\mathcal P^\alpha(\mathbb N)$ if the original Borel set was at level $\alpha$. The superscript $\alpha$ indicates we iterate the power set operation $\alpha$ times. I say "something like" since the precise computation requires a bit more care with the stratification.

(One talks of "unraveling" because the associated open game is built up from the original Borel set $X$, its "history" (that is, what sets are used when taking countable unions and complements leading up from open sets to $X$), and the possible (not necessarily winning) strategies of the game on $X$.)

This need to look at huge spaces is an essential technicality, which explains the difficulty of the result (it uses replacement in an unavoidable manner). The precise count of how many power sets any proof requires (level by level through the stratification) is a refinement of Martin of the original argument, due to Harvey Friedman.

So: If you understand the Gale-Stewart result, and are comfortable with the basic theory of ordinals or transfinite induction, the result should be fairly accessible. Typically, the presentations of the argument use $\omega^\omega$ rather than $\mathbb R$. A bit more descriptive set theory shows that this is not an issue: There is a Borel bijection between $\mathbb R$ and $\omega^\omega$ that sends Borel sets to Borel sets (this is also explained in Kechris's book), and one can check that determinacy is preserved through this transformation.

The idea of unravelings can be extended beyond Borel sets. Itay Neeman, for example, showed how to unravel $\Pi^1_1$ sets. That said, the proofs of projective determinacy and beyond proceed differently from the proof of Borel determinacy, and use large cardinals in an essential fashion.

Edit, Sep. 24, 2013: Timothy Gowers has written a beautiful five-part series of posts discussing the proof, and motivating how one may go about discovering it: 1, 2, 3, 4, 5.

  • $\begingroup$ Thank you very much. I should admit that I'm very lucky to have an answer from an expert like you. $\endgroup$ Jun 14 '13 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.