9
$\begingroup$

Consider the following infinite game: two players, I and II, are alternating and choosing a descending sequence of subsets of $\mathbb R$ of cardinality $\frak c$, so I chooses a set $A_1\subseteq\mathbb R$, II chooses a set $A_2\subseteq A_1$, I chooses $A_3\subseteq A_2$ etc., all having the size continuum. Let $A=\cap_{i=1}^\infty A_i$. I wins if $A$ is nonempty, otherwise II wins.

Who has a winning strategy in this game?

This game was posed to me as a puzzle from a person I don't have any means of contact with anymore (so I can't ask them about this). However, I don't know whether he himself knew the answer or not (as far as I know it might be independent of ZFC or unknown) which is why I'm posting this on MO and not Math.SE (the same person has posed as a puzzle a combinatorial problem which I happened to know is open).

All I know is that it's consistent with ZF that II has the winning strategy: if $\mathbb R$ had countable cofinality, i.e. was a countable union of sets $S_i,i\in\mathbb N$ of cardinality $<\frak c$, then II could play on his turns $A_{2k}=A_{2k-1}\setminus(S_1\cup\dots\cup S_n)$, which would have size $\frak c$. This doesn't go through in ZFC, since there $\frak c$ has uncountable cofinality.

One can also consider the problem with $\mathbb R$ replaced by some other set, for example an ordinal. For some sufficiently well-behaved sets (not Dedekind-finite, for example) the above reasoning shows that if a cardinal has countable cofinality, I has a winning strategy. I am especially interested in the case of $\omega_1$, which is equivalent to the problem at hand if we assume CH.

I am interested in this problem both in context of ZF and ZFC, and I am willing to assume CH to resolve the original problem if it is of help there.

$\endgroup$
  • $\begingroup$ See related question: mathoverflow.net/questions/137362/a-game-on-sets-of-reals $\endgroup$ – Joel David Hamkins Jan 2 '17 at 19:16
  • $\begingroup$ @JoelDavidHamkins Ah, haven't found that question before. This does answer a big part of my question, since it gives that I (the player who aims for the empty set) wins if the set is well-orderable. $\endgroup$ – Wojowu Jan 2 '17 at 19:24
  • $\begingroup$ And related to that related question, math.stackexchange.com/q/276796/622 $\endgroup$ – Asaf Karagila Jan 2 '17 at 19:31
  • $\begingroup$ @AsafKaragila Well damn, it seems like I did an awful job at searching for related questions. $\endgroup$ – Wojowu Jan 2 '17 at 19:32
  • $\begingroup$ Ain't no thing but a hyperchicken wing. $\endgroup$ – Asaf Karagila Jan 2 '17 at 19:34
13
$\begingroup$

In ZFC, the player aiming for the empty set has a winning strategy in the game played on any infinite set, including the reals. Using the axiom of choice, we can well-order the set and thereby pretend that we are playing sets of ordinals. Now, whenever it is the empty-set player's turn, she should look at the order type of the ordinals remaining, and play so as to omit the first element of every successive block of $\omega$ many elements in the enumeration of the set. In this way, no element can survive into the final intersection. If an element is the $(k+1)^{th}$ in it's $\omega$-block, then it is the $(\omega\cdot\gamma+k+1)^{th}$ element of $A_n$ for some ordinal $\gamma$, and after the empty-set player plays, it will become the $(\omega\cdot\gamma+k)^{th}$ element of the new set, strictly smaller. When the other player plays, if it was the $\alpha^{th}$ element, it becomes the $\beta^{th}$ element for some $\beta\leq\alpha$. So as play progresses, the index of the element in the enumeration will steadily descend. Since it cannot descend forever, the element must eventually fall out of the set and so the final intersection is empty, as desired.

In ZF, the argument I gave at the other question shows that the non-empty player cannot have a winning strategy in the game on the reals.

$\endgroup$
  • $\begingroup$ Thank you for summing up the ideas from the other question into an answer. So to the best of our knowledge the game is fully resolved in the case of well-orderable sets and in other cases it is the empty player who wins, if either does. I am still going to wait with accepting this, since this puzzle was posed to the audience with very little set theory background, so in the case of $\mathbb R$ an answer might exist. $\endgroup$ – Wojowu Jan 2 '17 at 19:32
  • $\begingroup$ Sure, that's fine! I like this game a lot, and I really do wonder what happens with it. $\endgroup$ – Joel David Hamkins Jan 2 '17 at 19:36
  • $\begingroup$ @Wojowu: You might want to take a look at this question where it is asked what happens if we are not allowed to use AC. This question is also related. $\endgroup$ – Burak Jan 2 '17 at 19:42
  • $\begingroup$ @Burak Thanks, this link was already posted in a comment under the question. Also, this is a slightly different question - in mine, we require all sets to not only be uncountable, but have the same size as the original. $\endgroup$ – Wojowu Jan 2 '17 at 19:44
  • 3
    $\begingroup$ Once again, I casually mention that this problem (with AC) is in my problem book with Totik. $\endgroup$ – Péter Komjáth Jan 3 '17 at 10:04
7
$\begingroup$

This problem (with inconsequential differences in the rules of play) was posed by S. Banach as Problem 67 in The Scottish Book, which is available here. The following text is copied from R. Daniel Mauldin's edition:

(A MODIFICATION OF MAZUR'S game, [see Problem 43]).

We call a half of the set $E$ [in symbols, $(1/2)E$] an arbitrary subset $H\subset E$ such that the sets $E,H,E-H$ are of equal power.

(1) Two players $A$ and $B$ give in turn sets $E_i, i=1,2,\dots$ ad inf. so that $E_i=(1/2)E_{i-1}\ i=1,2,\dots$ where $E_0$ is a given abstract set. Player $A$ wins if the product $E_1E_2\dots E_iE_{i+1}\dots$ is vacuous.

(2) The game, similar to the one above, with the assumption that $E_i=1/2[E_0-E_1-\dots-E_{i-1}]\ i=2,3,\dots$ ad inf., and $E_1=(1/2)E_0.$ Player $A$ wins if $E_1+E_2+\dots=E_0.$

Is there a method of win for player $A$? If $E_0$ is of power cofinal with $\aleph_0,$ then player $A$ has a method of win. Is it only in this case? In particular, solve the problem if $E_0$ is the set of real numbers.

Addendum. There exists a method of play which will guarantee that the product of the sets is not vacuous. The solution was given by J. Schreier.

The problem is dated August 1, 1935; the addendum is dated August 24, 1935; Schreier's solution (using the well-ordering theorem, see Joel David Hamkins' answer) was published in the paper

J. Schreier, Eine Eigenschaft abstrakter Mengen, Studia Math. 7 (1938), 155–156, eudml.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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