infinite-gamespuzzlerecreational-mathematicsset-theory
A 2 player game on $\mathcal{P}(\mathbb{R})$: Players take turns playing uncountable sets of reals. Each play must be a subset of the previously played set. Player 1 wins if the intersection of all the sets is nonempty. Otherwise player 2 wins.
Assuming AC, player 2 has a winning strategy. On can prove in ZF that 2 wins the analogous game on any well-ordered set.
What might happen without AC? I heard a false argument that 1 wins assuming the perfect set property, so be careful.
Neither player has a winning strategy, see below.
However, when the game is restricted so that Q can only play sets with the Baire property, then A has a winning strategy. Note that sets with the Baire property form a $\sigma$-algebra which includes all analytic sets, and assuming the axiom of projective determinacy, all projective sets.
In the restricted game, we can write $A_i=U_i\vartriangle\bigcup_jM_{p(i,j)}$, where $U_i$ is open, $M_k$ are nowhere dense, and $p\colon\omega\times\omega\to\omega$ is a bijective pairing function such that $p(i,j)\ge i,j$. The winning strategy for A is then to maintain a chain of nonempty bounded open intervals $I_n$ so that
$I_0\supseteq\overline{I_1}\supseteq I_1\supseteq\overline{I_2}\supseteq I_2\supseteq\cdots$,
$I_i\subseteq U_i$,
$I_i\cap M_i=\varnothing$.
This can be arranged as follows. Let $Q_i=V\vartriangle M$ be given, where $V$ is open and $M$ is meager. If $I_{i-1}\cap V\ne\varnothing$, A chooses $A_i=Q_i$, otherwise $A_i=Q_i^c$ (note that in the latter case, we will have $I_{i-1}\subseteq U_i$). This determines $U_i$ and $M_{p(i,j)}$, and it remains to find $I_i$. Now, $I_{i-1}\cap U_i$ is a nonempty open set. Moreover, $M_i$ is nowhere dense, hence the open set $I_{i-1}\cap U_i\smallsetminus\overline{M_i}$ is still nonempty, and therefore it contains an interval $I_i$. By shortening it if necessary, we can make sure that $\overline{I_i}\subseteq I_{i-1}$.
When the game finishes using this strategy, then $\bigcap_iI_i=\bigcap_i\overline{I_i}$ is nonempty by compactness. Any its element is included in every $U_i$, and avoids all $M_{p(i,j)}$, hence it lies in every $A_i$. On the other hand, each $A_i$ contains an interval minus a meager set, hence it cannot itself be meager, and in particular, it has more than one element.
EDIT: The argument above does not require full axiom of choice, it goes through in ZF + DC. Shelah has shown the relative consistency of ZF + DC + “every set of reals has the Baire property”, hence it is consistent with ZF + DC that A has a nondeterministic winning strategy in the unrestricted game.
A also has a winning strategy if Q is restricted to Lebesgue measurable sets. The strategy is to maintain a chain $P_0\supseteq P_1\supseteq P_2\supseteq\cdots$ of perfect sets with positive measure such that $P_i\subseteq A_i$. Given $Q_i$, we choose $A_i$ so that $P_{i-1}\cap A_i$ has positive measure. Using inner regularity, there exists a perfect set $P_i$ of positive measure included in $P_{i-1}\cap A_i$. This strategy guarantees that each $\bigcap_{i<n}A_i$ is uncountable, and $\bigcap_{i\in\omega}A_i\supseteq\bigcap_{i\in\omega}P_i$ is nonempty by compactness.
In ZFC, neither player has a winning strategy in the unrestricted game. For Q, this is shown in Joel David Hamkins' answer.
Theorem. A does not have a winning strategy.
For simplicity, I will consider the game played with the product space $2^\omega$ instead of $\mathbb R$. For $t\in2^{<\omega}$, let $B_t=\{f\in2^\omega\mid f\supseteq t\}$ be a basic clopen set, let $D_n=\{f\in2^\omega\mid f(n)=1\}$, and let $C$ be the Boolean algebra consisting of sets of the form $X\vartriangle Y$, where $X$ is clopen and $Y$ is finite. Given a sequence of sets $Q=\langle Q_0,\dots,Q_n\rangle$ as moves of the first player and a strategy $\sigma$ of A, I will write $\sigma(Q)=A_n\in\{Q_n,Q_n^c\}$ for A's move provided by the strategy, and $Q^\sigma=\bigcap_{i\le n}A_n$. The latter notation can also be used for infinite sequences $Q$. If $Q,R$ are sequences, then $Q\smallfrown R$ is their concatenation, $|Q|$ is the length of $Q$, and $Q\subseteq R$ means that $Q$ is an initial segment of $R$.
Lemma. If A has a winning strategy in the game played on a subset $G\subseteq2^\omega$, then $G$ contains a perfect subset.
Proof: let's consider finite sequences $Q$ consisting of elements of $C$. First, assume that there exists such $Q$ so that for every finite $R,S\supseteq Q$, $R^\sigma\cap S^\sigma\ne\varnothing$. Then it is easy to see that there exists an ultrafilter $F\subseteq C$ such that $\sigma(R)\in F$ for every $R\supseteq Q$. Let $R$ be the infinite sequence $\langle D_n\mid n\in\omega\rangle$. Then $|(Q\smallfrown R)^\sigma|\le1$. On the other hand, since $\sigma$ is a winning strategy, $(Q\smallfrown R)^\sigma$ is nonempty (and intersects $G$), hence it equals $\{\alpha\}$ for some $\alpha\in2^\omega$. Then either $(Q\smallfrown\{\alpha\})^\sigma=\{\alpha\}$ or $(Q\smallfrown\{\alpha\}\smallfrown R)^\sigma=\varnothing$, contradicting $\sigma$'s being a winning strategy.
Thus, for each $Q$ there exist $R,S\supseteq Q$ such that $R^\sigma\cap S^\sigma=\varnothing$. By induction, we can construct $\{Q_t\mid t\in2^{<\omega}\}$ such that
$t\subseteq s\Rightarrow Q_t\subseteq Q_s$,
$Q_{t\smallfrown0}^\sigma\cap Q_{t\smallfrown1}^\sigma=\varnothing$.
Moreover, $Q_t^\sigma\in C$, hence we can write it as $X_t\vartriangle Y_t$ with $X_t$ clopen and $Y_t$ finite. By extending $Q_t$ (at the point where it is being constructed) with $D_i$, $i\le|t|$, we can make sure that
By extending $Q_t$ with $Y_t$, we can make sure that $Q_t^\sigma$ actually equals $X_t\smallsetminus Y_t$. Then $X_{t\smallfrown0}\cap X_{t\smallfrown1}$ is a finite clopen set, hence it is empty, thus:
For every $f\in2^\omega$, let $Q$ be the infinite sequence $\bigcup_{t\subseteq f}Q_t$. Since $\sigma$ is a winning strategy, $Q^\sigma\cap G$ is nonempty, hence it contains an element $\phi(f)$. The properties of $Q_t$ ensure that $\phi\colon2^\omega\to2^\omega$ is injective and continuous, hence its range is a perfect subset of $G$, finishing the proof of the Lemma.
In order to prove the theorem, observe that there are $\mathfrak c=2^\omega$ perfect subsets of $2^\omega$, so we can enumerate them as $\{P_\alpha\mid\alpha<\mathfrak c\}$. (This is the place which breaks in ZF + DC, we need $2^\omega$ to be well ordered.) We construct disjoint sequences $\{a_\alpha\mid\alpha<\mathfrak c\},\{b_\alpha\mid\alpha<\mathfrak c\}\subseteq2^\omega$ by induction as follows: each $P_\alpha$ has cardinality $\mathfrak c$, whereas $S=\{a_\beta,b_\beta\mid\beta<\alpha\}$ has smaller cardinality, hence we can choose disctinct $a_\alpha,b_\alpha\in P_\alpha\smallsetminus S$. Let $X=\{a_\alpha\mid\alpha<\mathfrak c\}$. By the construction, neither $X$ nor $X^c$ contains a perfect subset.
Assume that $\sigma$ is a winning strategy for A in the game played on $2^\omega$. Take $Q_0=X$, and let $A_0=\sigma(Q_0)$. Then $\tau(R):=\sigma(Q_0\smallfrown R)$ defines a winning strategy for A in the game played on $A_0$, hence by the Lemma, $A_0$ has a perfect subset, a contradiction.
Here is an amusing concrete non-determined game, under the assumption that the dependent choice principle fails.
Assume DC fails. This means that there is a set $X$ and a binary relation $R$ on $X$, such for every $x\in X$ there is $y$ with $x\mathrel{R} y$, but there is no sequence $\langle x_n\mid n\in\omega\rangle$ with $x_n\mathrel{R} x_{n+1}$ for all $n$. In other words, the tree of finite sequences that accord with $R$ has no leaves — every node can be extended one more step — but there is no way to iterate these steps and the tree has no infinite branch.
Consider the game on $X$ where player I plays a point $a$ from $X$ and player II responds with $b$, and player II wins just in case $a\mathrel{R} b$; otherwise player I wins. So the game is over very quickly, after just one move for each player. (If you insist that games should have infinitely many plays, then you can continue with infinitely many irrelevant moves.)
Player I obviously cannot have a winning strategy, since whatever point $a$ is played, there is a way for II to defeat it by playing some $b$ with $a\mathrel{R} b$.
But player II also cannot have a winning strategy, since any such strategy would provide a choice function on the $R$-successors of the points in $X$, and any such function could be iterated to thread $R$, whereas there is no such infinite thread.
Since the game is an open game (in fact clopen), this argument shows that one cannot prove open determinacy without DC. The usual proof of open determinacy uses DC, when showing that if a position does not have an ordinal rank, then the closed player can avoid losing by maintaining rank. But in order to do so, that player needs DC to find the infinite thread of rank-maintaining moves.
Update. As noted in wojowu's comment below, this example can be adapted to prove the following theorem.
Theorem. ZF proves that there is a non-determined set. Specifically, in ZF we can prove that $\text{AD}_{P(\mathbb{R})}$ fails.
Proof. First, let $F$ be any family of non-empty sets, and consider the game where player I selects some $A\in F$ and player II selects some $a\in A$, and the first player to violate either requirement loses. Clearly, there can be no winning strategy for player I, since if such a strategy directed player I to play a particular $A$ in $F$, then it would be defeated by the strategy for player II to always play some particular element $a\in A$. Conversely, observe that if player II has a winning strategy for the game, then we would have a choice function for $F$. So any violation of AC leads immediately to a non-determined game. In particular, if choice fails for families of nonempty sets of reals, then we get a violation of $\text{AD}_{P(\mathbb{R})}$. On the other hand, if choice holds for such families, then the reals are well-orderable, and we may construct a non-determined set for binary play. So in either case, $\text{AD}_{P(\mathbb{R})}$ fails. QED
Regarding the remarks below about constructing an "explicit" game, one can easily do this as follows.
Corollary. In ZF we can write down an explicit definition of a non-determined set.
Proof. Consider the game where player I chooses either (1) a well-ordering of the reals, and then the rest of the payoff set is as would be constructed for a non-determined set by the usual argument given such a well-ordering; or (2) a family $F$ of nonempty sets of reals having no choice function, with player II then picking an element of the family and player I playing an element of that set, as in the theorem (but with the players reversed). This gives altogether one big payoff set, explicitly defined.
Note that player I cannot have a winning strategy, since he cannot have a strategy for the resulting play in case (1), as the game is undetermined, and he cannot have a strategy that wins by placing him in case (2), since any such strategy would have to provide a choice function for $F$.
Conversely, player II cannot have a winning strategy, since player I can play either a family with no choice function, in which case it is hopeless for II to play with particular element of the family, or else AC holds for all such families in which case player I can play a well-ordering and a non-determined game, for which player II can have no responding strategy. QED
Best Answer
This is a great question! I've now managed to eliminate the use of countable choice.
Theorem. Without using any choice principle, it follows that player I can have no winning strategy in the game.
Proof: Working in ZF only, suppose toward contradiction that player I has a winning strategy $\tau$. Look at the set $A$ played by player I on the first move, using strategy $\tau$. Note that $A$ is uncountable, but it can have no uncountable well-orderable subset, since in this case player II could play that subset and move to the well-orderable case, which according to what you have said would put player II in a winning position and therefore contradict that $\tau$ is winning for player I.
Let us now argue that there is a choice function on the uncountable subsets of $A$. To see this, fix any uncountable $B\subset A$ and let us have player II respond with $B$ on player II's first move, with player I continuing subsequently to play according to $\tau$. At each subsequent stage $n$, let us have player II follow the (losing) strategy, where when confronted with a set $E\subset A$, he will find the first rational interval $I$ (in some canonical enumeration) of width $\frac 1n$ such that $E\cap I$ is uncountable, and then play $E\cap I$.
We could deduce that such an interval $I$ exists if we had countable choice, since otherwise $E$ would be a countable union of countable sets. But I claim that we do not need to assume any choice principle in order to make this conclusion. If the set $E$, which was played by player I according to the strategy $\tau$, is the countable union of countable sets $\bigcup_n E_n$, then this is now a winning position for player II, since every uncountable subset of $E$ must contain points from infinitely many $E_n$, and so player II can always subsequently play on his $k^{th}$ step so as to remove the sets $E_i$ for $i\leq k$ from play (a countable removal). Since $\tau$ is winning for player I, however, it must be that the set $E$ is not a countable union of countable sets and so such a rational interval $I$ exists.
Continuing with the main line of argument, what we have is that player II is playing in a prescribed manner (without using any AC), but ensuring that the diameters of the sets in the play of the game go to $0$. Since $\tau$ is winning, the final intersection set will therefore be a singleton subset of $B$, and thus we have provided a means to choose an element from any such $B$.
Using this choice function, we can now choose elements from uncountable subsets of $A$. It follows that we can define an injection of $\omega_1$ into $A$: we first choose a point $a_0\in A$, and then choose a point from $A-\{a_0\}$ and so on. At each stage $\beta$, we choose a point in $A-\{a_\alpha\mid\alpha\lt\beta\}$, which is an uncountable subset of $A$. The set of $a_\alpha$ is an uncountable well-orderable subset of $A$, which contradicts our assumption that there was no such subset. So player I cannot have such a winning strategy after all. QED
This theorem does not seem to imply that player II must have a winning strategy, however, since perhaps the game is undetermined.
Following the link in Andres's comment, we see that Asaf Karagila had had essentially the same argument over at math.SE. And the trick to eliminate the use of countable AC uses the same idea as in Andres's answer over at math.SE.