# A question about a two player game and axiom of choice

Suppose two players 1 and 2 play the following game:

Player 1 starts by playing the set of reals $\mathbb{R}$. Player 2 plays an uncountable subset $Y_1$ of $\mathbb{R}$. Then player 1 plays an uncountable subset $X_1$ of $Y_1$. Then player 2 plays an uncountable subset $Y_2$ of $X_1$ and so on. Player 1 wins if the intersection of all the sets played is non empty otherwise player 2 wins.

Then one can show that if $\omega_1$ injects into $\mathbb{R}$ then player 2 has a winning strategy.

Question 1: Can the existence of a winning strategy for player 2 be shown in $ZF + DC$?

Question 2: If not, then is the following consistent: $ZF + DC +$ "Player 1 has a winning strategy"? A possible model for this could be a model of "Every uncountable set of reals has a perfect subset" but I don't know anymore.

-
I can see how in ZFC Player 2 has a winning strategy, but in $\mathsf{ZF+DC}+\omega_1\leq\mathbb R$ I just don't see it. In what context did you come up with these questions? –  Asaf Karagila Jan 13 '13 at 14:51
If $\omega_1$ injects into $\mathbb{R}$, then player 2 plays this copy of $\omega_1$ and then your ZFC proof can take over. –  Anonymous Jan 13 '13 at 15:35
No, because the proof requires a choice function for subsets all across the board; not just a countable collection of subsets. I am certain that I'm missing something, I'm just too deep into this problem to see what it is. –  Asaf Karagila Jan 13 '13 at 15:38
I had this strategy in mind: If $\omega_1$ injects into $\mathbb{R}$, player 2 can play a copy of $\omega_1$ in his first move. At any later stage, he enumerates the subset of $\omega_1$ just played by player 1 in order type $\omega_1$ and removes all ordinals that occur at limit positions and also zeroth ordinal. –  Anonymous Jan 13 '13 at 15:43
Okay. That was what I had in mind as well, although in a far more complicated and convoluted way (using stationary co-stationary subsets and so on). Your method is much simpler and now I could finally finish this proof in a single line. Thanks! It frees me up to think about the choiceless case. –  Asaf Karagila Jan 13 '13 at 15:48

I think that the following is a correct proof of the following claim:

Proposition ($\mathsf{ZF+DC}$). If Player I has a winning strategy then $\omega_1\leq\mathbb R$.

Proof. Let $F\colon\mathbb R\to\omega_1$ be a surjection such that each fiber is uncountable (which is definable in $\mathsf{ZF}$), and let $q_n$ be an enumeration of the rationals.

Let $\alpha<\omega_1$, we consider the following game: $Y_1=F^{-1}(\alpha)$. This is an uncountable set, so it is a legal move. Player I plays by its strategy, and Player II plays by the following strategy:

Suppose $X_n$ was chosen, let $q$ be the least rational number such that $(q-\frac1n,q+\frac1n)\cap X_n$ is a legal move. Such rational exists otherwise $X_n$ is the countable union of countable sets, which under $\mathsf{DC}$ is countable. Then $Y_n$ is that intersection.

As the first player has a winning strategy it assures us that $\bigcap Y_n\neq\varnothing$, but in this case the intersection can only contain one point, because $a,b\in Y_n$ for all $n$ it means that $|a-b|<\frac1n$ for all $n$. We denote $r_\alpha$ this unique point.

It is left to show that $f(\alpha)=r_\alpha$ is injective, but this is trivial because $F(r_\alpha)=\alpha$ by the fact that $r_\alpha\in F^{-1}(\alpha)$. $\square$

From this follows that it is impossible in $\mathsf{ZF+DC}$ to have a winning strategy for Player I. But it is not enough to prove the existence of a strategy for Player II.

I think that the only use of the axiom of choice is in showing that countable unions of countable sets of real numbers are countable. If this is false, Andres gave a strategy for Player I, and if this is true the arguments above along with the arguments in the comments to the question show that Player I cannot have a winning strategy. Indeed we are left to show whether or not $\mathsf{ZF+DC}$ prove that Player II can win, or maybe there is some model in which the game is indeterminate.

-
I'd be delighted to hear any complaints, remarks, or general comments on this proof. –  Asaf Karagila Jan 13 '13 at 17:23
Nice. This answers my question 2. –  Anonymous Jan 13 '13 at 23:24
@Anonymous: Yes, when I couldn't write a reasonable proof for question $1$, I figured I should attack the other question instead. :-) –  Asaf Karagila Jan 13 '13 at 23:34
Let me first point out that (in $\mathsf{ZF}$) if there is a countable collection of countable sets of reals whose union is uncountable, say $Y=\bigcup_n A_n$, where we may as well assume the $A_n$ are disjoint, then II has a winning strategy: For each $n$, II wins by playing $Y_{n+1}=X_n\cap\bigcup_{m>n}A_m$, where $X_0=\mathbb R$. Note each $Y_{n+1}$ has countable complement in $X_n$, and their intersection is contained in $\bigcap_n\bigcup_{m>n}A_m=\emptyset$, so this is winning for II.
An earlier version of this answer had a mistake. Asaf has given the right answer, let me add some remarks: Asaf proof actually shows that, if every countable union of countable sets of reals is countable, and I has a winning strategy, then $\omega_1\le \mathbb R$. As described in the comments, if $\omega_1\le\mathbb R$, then I was a winning strategy. It remains to address what happens when $\omega_1\not\le\mathbb R$ but countable unions of countable sets of reals are countable. (The two possibilities are that the game is undetermined, or that II has a winning strategy.)
Nice, Andres. Can you help me find the mistake in my answer? Also why does the bijection between $\mathbb R$ and $2^\omega$ preserves perfectness? –  Asaf Karagila Jan 13 '13 at 18:16
It doesn't have to, but every uncountable subset of the Cantor ternary set, being an uncountable subset of $\mathbb R$, contains a perfect set, which is all I need. I am only using the Cantor set so I can easily describe closed sets via their trees, but we can as well work with $[0,1]$. –  Andres Caicedo Jan 13 '13 at 19:44
Yes, of course. The set $Y_n$ I had was not necessarily closed, so the tree associated with $Y_n$ will most likely have branches that lie outside of $Y_n$, so the perfect set $X_n$ is not a subset of $Y_n$ in general. (It was a silly thing: We can define an element of each closed set, so if we could do as I suggested, we would have a choice function on uncountable sets. But then $\omega_1\le\mathbb R$.) –  Andres Caicedo Jan 13 '13 at 20:25