The Undetermined Game

This post is a continuation of the previous one, so make sure to read that one first! The construction here is very set theory heavy, so if you are not familiar with the subject, I would recommend this by Vsauce to help you get started)

Alright, how can we build an undetermined game? As a prior warning (and as you may have guessed), the construction requires the Axiom of Choice

To keep things simple, we will construct a winning set for a game on the infinite binary tree (that is, on each turn, a player plays either 0 or 1).

Now, look at the set $S_1$ of strategies for the first player. What is its cardinality? Well, a strategy (for player 1) is a function from the set of positions where the first player plays to ${0,1}$. Since the number of positions where player 1 plays is countably infinite, the number of strategies is $2^{\aleph_{0}}=\aleph$. Similarly, set $S_2$ of strategies for player 2 is also of cardinality $\aleph$.

Additionally, look at the set $[T]$ of possible games. In other words, the set of infinite strings containing 0 or 1. It too has a cardinality of $\aleph$. We call a string $x\in[T]$ compatible with a strategy $s$ if there is a strategy for the other player $s’$ such that when the players play $s$ and $s’$ respectively, the result is the string $x$. In other words, a string is compatible with a strategy if it is possible to see it as a result when that strategy is played. Notably, for any strategy, there are $\aleph$ games that are compatible with it and $\aleph$ that are not (why? exercise for you!).

The idea of the proof is as follows: we construct a set $W$ by going over every strategy for each player. For every strategy of player 1, we put a game compatible with it outside of $W$. For every strategy of player 2, we put a game compatible with it into $W$. That way, for each strategy for player 1, if player 2 plays the strategy corresponding to the compatible play we added to $W^c$, player 1 loses. Similarly for every strategy of player 2, if player 1 plays the strategy corresponding to the compatible game we added to $W$, player 2 loses.

We cannot, however, do this process naively, since we may end up adding the same game to $W$ and $W^c$. Here’s where we need the Axiom of Choice: look at the sets of strategies for either player $S=S_1\cup S_2$ and define a well-ordering on it, such that for strategy the number of strategies before it is of cardinality less than $\aleph$ (we can get such ordering by taking a bijection to (aleph) as an ordinal).

We inductively define two sets $W$ and $V$, each of them starting as the empty set. Go over the elements of $S$ according to the ordering we defined. For each strategy in $S_1$ (for player 1) we go over, add a game $x$ which is compatible with it to $V$, which was not added to $V$ or $W$ before. Similarly, for each strategy for player 2 we go over we add a game compatible with it to $W$, which was not added to either set before. The result of the process is two disjoint sets $V$ and $W$. In fact, the union of the two is $[T]$ itself; e.g. $V$ is the complement for $W$. However, we will not need this fact for the proof.

It’s important to note that this process is indeed well defined; we may always find a game to add to $V$ or $W$. At each step of the process, because of the way we defined the ordering both $W$ and $V$ have cardinality less than $\aleph$ at each step. Then, because every strategy has $\aleph$ games compatible with it, there will always be a game we haven’t added yet.

Now, we claim the game whose winning set is $W$ is not determined. Why is that? First, suppose player 1 had a winning strategy $s_1$. Then at the step of the process corresponding to $s_1$ we added a game x compatible with $s_1$ to $V$. In other words, there is some strategy $s_2$ for player 2 which results in $x$, which is in $V$. Since $V$ and $W$ are disjoint, if player 2 plays strategy $s_2$ against $s_1$, the result is not in W and so a win for player 2, a contradiction. Therefore, player 2 has no winning strategy.

Similarly, suppose player 2 had a winning strategy $s_2$. Again look at the step of the process corresponding to it. There, we added a game x compatible with $s_2$ to W. In other words, there is a strategy $s_1$ for player 1 which when played against $s_2$ results in x, an element outside of $W$, and hence a win for player 1. This once more is a contradiction to the fact that $s_2$ is winning.

So the winning set $W$ we chose does indeed result in an undetermined game!