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.

  • $\begingroup$ 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? $\endgroup$ – Asaf Karagila Jan 13 '13 at 14:51
  • 1
    $\begingroup$ If $\omega_1$ injects into $\mathbb{R}$, then player 2 plays this copy of $\omega_1$ and then your ZFC proof can take over. $\endgroup$ – Anonymous Jan 13 '13 at 15:35
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jan 13 '13 at 15:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Anonymous Jan 13 '13 at 15:43
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ I'd be delighted to hear any complaints, remarks, or general comments on this proof. $\endgroup$ – Asaf Karagila Jan 13 '13 at 17:23
  • 1
    $\begingroup$ Nice. This answers my question 2. $\endgroup$ – Anonymous Jan 13 '13 at 23:24
  • 1
    $\begingroup$ @Anonymous: Yes, when I couldn't write a reasonable proof for question $1$, I figured I should attack the other question instead. :-) $\endgroup$ – 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.)

  • $\begingroup$ 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? $\endgroup$ – Asaf Karagila Jan 13 '13 at 18:16
  • $\begingroup$ 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]$. $\endgroup$ – Andrés E. Caicedo Jan 13 '13 at 19:44
  • $\begingroup$ I found the mistake, it's mine. $\endgroup$ – Andrés E. Caicedo Jan 13 '13 at 20:12
  • $\begingroup$ Oh what is it? So my argument was correct? $\endgroup$ – Asaf Karagila Jan 13 '13 at 20:13
  • $\begingroup$ 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$.) $\endgroup$ – Andrés E. Caicedo Jan 13 '13 at 20:25

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.