Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Does Player 2 always have a winning strategy? I think I did recently read something about it in measure and category from John C. Oxtoby. Unfortunately I don't have the book here but I don't know if there is mentioned something about the non AC case. Should I go to library and check it? –  Dominic Michaelis Jul 22 '13 at 5:07
5  
Player 2 can subtract the elements enumerated by 0 or limit ordinals at each step, then re-enumerate in an order preserving way, and repeat. This ensures the ordinals assigned to a given surviving element keeps decreasing. –  Monroe Eskew Jul 22 '13 at 5:58
3  
Related. –  Andres Caicedo Jul 22 '13 at 7:15
    
Andres, thanks for the link! I see there that Asaf Karagila had had essentially the same argument that I have here. –  Joel David Hamkins Jul 22 '13 at 12:51

1 Answer 1

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.

share|improve this answer
    
This answer is incomplete, so I don't think it should be accepted. –  Sam Hopkins Jul 22 '13 at 5:47
1  
good point, but it's a nice start joel –  Monroe Eskew Jul 22 '13 at 6:00
    
I got rid of the use of countable AC. –  Joel David Hamkins Jul 22 '13 at 13:34
4  
I didn't think you used countable choice in the first place. WLOG we are playing in the unit interval, and player 2 can find the least natural $k < n$ such that $E \cap [k/n,(k+1)/n)$ is uncountable. The fact that a finite union of countable sets is countable does not need choice. –  Monroe Eskew Jul 22 '13 at 14:34
    
Aha, that is a better way to do it! –  Joel David Hamkins Jul 22 '13 at 14:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.