Building Sets/Functions by Playing Games

Question

I have sat in lectures on set theory and I have seen the use of games cropping up in many places. I don't really understand what was going on and how useful games are in set theory, but here I have a question.

Take a typical example in descriptive set theory where we associate initial segments of a branch of a tree to other sets. For instance, let $M$ be a perfect Polish space and we are assigning (a function) each initial segment in the Cantor space a nonempty open neighborhood of $M$ such that

1. if $u < v$, then $N_u\subseteq N_v$,
2. if $u$ and $v$ are incompatible, then $N_u\cap N_v=\emptyset$, and
3. if $lh(u)=n$, then the radius of $N_u$ is no larger than $2^{-n}$.

I find it convenient to picture the construction as two players playing a game: Player I gives a finite binary sequence and Player II collaborate by producing a neighborhood satisfying 1, 2, and 3.

This game doesn't require any player to win, but it seems to give a useful way to describe the process that's taking place.

In set theory, do we ever consider games without having either player to win, perhaps for constructing sets or functions as given above? Or perhaps my description above didn't make much sense, or there are aspects of winning condition in it that was implicit or for which I failed to see?

Answer 1

I will give two explanations for why games crop up so fruitfully, one explanation from mathematics and the other arising from evolutionary biology.

The mathematical explanation for why games crop up in mathematics is that the truth of a complex statement

$$\forall x_0 \exists y_0 \forall x_1 \exists y_1 \cdots \varphi(x_0,y_0,x_1,y_1,\ldots)$$

is easily thought of as a game, where the first player (called Adam for $\forall$) plays $x_0$, challenging Eve (for $\exists$) to respond with a value $y_0$, for which Adam plays $x_1$, to which Eve responds with $y_1$ and so on, with Eve winning when $\varphi(x_0,y_0,x_1,y_1,\ldots)$. The point is that (in the finite case) the statement above is true exactly when Eve has a winning strategy allowing her to defeat all plays of Adam. Thus, the truth of the statement with alternating quantifiers can be thought of in terms of these games and whether they have strategies.

Such a perspective is fruitful even when there are only a few quantifiers, as our calculus students learn when studying continuity or when seeing $\epsilon,\delta$ proofs for the first time ("you pick $\epsilon$, and I can respond with $\delta$").

Thus, the answer to your question about why games are so fruitful is that the existence of strategies for those games is intimately connected with the truth of complex statements. Since it is these statements that we are really interested in, it is fruitful to investigate them particularly with the game perspective.

One can prove using these ideas that all finite length games are determined, in the sense that they have a winning strategy for one of the players. That is, either Eve has a strategy that allows her to defeat all plays by Adam, or else Adam has a winning strategy allowing him to successfully challenge any play of Eve.

The natural generalization of these ideas lead to the Axiom of Determinacy, which asserts even that infinitely long games are determined. In this context, one imagines an infinite game, with Adam playing $x_n$ and Even playing $y_n$ for all natural numbers $n$, and then Eve wins if the play $(x_0,y_0,x_1,y_1,\ldots)$ is in the payoff set $A$, a set of infinite sequences. The Axiom of Determancy asserts that for every set A, either Adam or Eve has a winning strategy, and this axiom can be thought of as an infinitary de Morgan law:

$$\neg[\forall x_0 \exists y_0 \forall x_1 \exists y_1 \cdots A(x_0,y_0,x_1,y_1,\ldots)] \iff\exists x_0 \forall y_0 \exists x_1 \forall y_1 \cdots \neg A(x_0,y_0,x_1,y_1,\ldots)$$

which expresses the idea that if Eve does not have a winning strategy, then Adam does have a winning strategy. Synatically, this equivalence looks quite natural, since we are used to pushing $\neg$ through all the quantifiers and changing them to the dual quantifier. But in the infinitary context, this equivalence is not a matter of logic, and actually contradicts the axiom of choice. But it does suggest AD as a natural axiom. From AD one can prove that every set of reals is Lebesgue measurable and many other natural regularity properties, such as the property of Baire and the perfect set property. The consistency of AD over ZF is equivalent to the consistency of infinitely many Woodin cardinals, a large cardinal property.

Evolutionary biology. But let me come to another more speculative explanation of why games crop up so frequently and fruitfully. This reason has to do with evolutionary biology. The fact is that the truth of a statement involving many alternations of quantifiers is amazingly complex mathematically. Even definitions involving five or six quantifiers are rather complex, and give rise to very subtle distinctions in mathematics, such as the difference between uniform continuity and continuity, or families of continuous functions versus equicontinuous families of functions. Nevertheless, because of the way that we humans evolved, we are used to thinking strategically, in making decisions that are provisional based on the future actions of other individuals. Thus, the strategic way of thinking allows us more easily to understand the meaning of these complex statements. I would say that this facility with strategic thinking means in a sense that we may have a hard-wired kind of inherent ability to reason about extremely complex mathematic statements, since these statements can be equivalently expressed as strategic games.

Answer 2

The use of the "winning" condition is to ensure that the overall construction has the properties we want. For example, in the game in the original question, Player 1 chooses "left" or "right" at each stage. Thus Player I always has a possible move. But Player II is forced to lose if the play arrives at a neighborhood that contains only a single point. So the actual question is whether Player II can play in a way that avoids ever being backed into a corner like that.

A winning strategy for Player II in that game actually encodes a complicated dependent-choice construction in which none of the neighborhoods played ever contains just one point. Such a construction is not possible in every Polish space. But we know that the construction is possible if and only if player II has a winning strategy in that game. So the game-theoretic language gives us a way to characterize topological properties of the space.

Answer 3

The Evolutionary Biology thing is interesting. Has determinacy been helpfun in theoretical computer science (AI) then, especially with regards to the Church-Turing thesis?

In an infinite games, Adam would try to play to come up with a sequence outside A, and Eve would play to hit A. But isn't it true that the sequence s is either in A or in U\A (the complement) and no matter how Adam or Eve plays, with the production of a sequence, we'd know whether $s\in A$ or otherwise, whence the infinitary de Morgan's law? (Hence, the game is determined.)

Answer 4

In the set $A$ produced by assuming the axiom of choice, why is the game not determined when obviously one player has to win eventually because the sequence produced has to be in $A$ or outside $A$? What am I missing in understanding this determinacy thing!

Answer 5

What you describe above is called a Cantor scheme in a polish space X. If one also requires that the closure of $N_v$ is a subset of $N_u$ whenever $u < v$, we get a point in X along each branch of this tree and the resulting map gives an embedding the the Cantor space into $X$. If the polish space is perfect, one may construct a Cantor scheme on it and as a result there is a copy of Cantor set in every such space.

I don't see a useful infinitary game being played in this construction. In any case, a game without a winning criterion doesn't appear very exciting.

One of the early motivations for considering infinitary games in descriptive set theory was the two way interaction between "nice" sets of reals and the determinacy of the games being played on these sets. Suppose $X$ is a set of reals. Define a two player game $G_X$ on $X$ as follows: player 1 and 2 successively choose either $0$ or $1$ to "construct" in $\omega$ steps a real. If this real is in X, player 1 wins otherwise player 2 wins. A winning strategy for a player is a map on finite strings of $0, 1$ that suggests the next digit to be played and when followed results in a win for the corresponding player. A game is determined if there is a winning strategy for one of the players. The following theorems give a sample of such results:

(1) If $X$ is Borel, $G_X$ is determined; analytic games are determined iff sharps exist.

(2) For a pointclass $\Gamma$ determinacy of sets in $\Gamma$ implies that all sets in $\Gamma$ are Lebesgue measurable and have the perfect set property and Baire property.

Determinacy has deep connections with the theory of large cardinals but I am not competent enough to describe it. The following is a landmark result:

(4) "Large" cardinals imply that all projective games are determined and therefore also that every projective set is Lebesgue measurable and has the perfect set property and Baire property.