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

Consider the following game, played by two players, called Q and A, in a time frame t = 1, 2, .... At every time point i, Q mentions some $Q_i \subset \mathbb{R}$, after which A mentions $A_i$ such that either $A_i = Q_i$ or $A_i = Q_i^c$.

Define $C(i) = \bigcap_{k \lt i} A_i$ and $C(\infty) = \bigcap_{k \in \mathbb{N}} A_i$.

Player Q is declared winner if either:

1) $C(i)$ has only one element for some $i < \infty$

or

2) $C(\infty)$ is empty.

(Player A wins in all other cases.)

Question: Which player (if any) has a winning strategy?

Edit: Some additional explanatory remarks:

This question occurred to me while thinking about Brouwer style choice sequences in connection with Borel sets.

Before posting, I was not 100% sure yet, but pretty confident that player A has a winning strategy when Q is restricted to giving Borel sets. This has been confirmed, in the meantime, in one of the answers below. (More generally A has a winning strategy when Q is restricted to sets having the Baire property.)

The general case is still open, though.

Some easy observations that might help to clarify the puzzle:

a) Player Q obviously has a strategy to make sure that $C(\infty)$ has at most one element. But that's not enough to win the game.

b) Whenever $C(i)$ is countable for some (finite) $i$, player Q can win the game, by (from time $i$ onwards) eliminating the elements of that countable set, one by one.

c) Player A has an easy strategy to make sure that $C(i)$ is uncountable for all (finite) $i$. But that's not enough to describe a winning strategy for player A. For example, when $Q_i = A_i = (0, 1/i)$ for every $i$, then $C(i)$ is uncountable for every (finite) $i$, but $C(\infty)$ is empty, and therefore A loses the game.

share|improve this question
    
What is the exponent $c$ supposed to be? –  Hans Stricker Feb 18 '11 at 15:34
    
I suppose $A^c$ is the complement of $A$. –  Emil Jeřábek Feb 18 '11 at 15:35
1  
I think I have seen a similar game as an exercise in some famous Real Analysis book.(Goldberg?) (Could you provide a ref if it's not made up?) –  Unknown Feb 18 '11 at 16:00
add comment

5 Answers 5

up vote 11 down vote accepted

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

  • $Q_t\subseteq B_s$ for some $s\in2^{<\omega}$, $|s|\ge|t|$.

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:

  • $\overline{Q_{t\smallfrown0}^\sigma}\cap\overline{Q_{t\smallfrown1}^\sigma}=\varnothing$.

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.

share|improve this answer
    
Very nice! Thanks very much. Any ideas on how to prove that A doesn't have a winning strategy in the general case? –  Herman Jurjus Feb 18 '11 at 19:17
1  
Great! Now let's go for the ZFC situation. –  Joel David Hamkins Feb 19 '11 at 11:57
    
This looks ok to me at first (and second) glance. Just one question: in the first part of the proof, you talk about an ultrafilter F. What is it used for? The condition on Q directly implies the alternative (in the last line of the first part), right? –  Herman Jurjus Feb 22 '11 at 19:07
    
The point is simply that $\sigma$ has to make the same choices for $Q\smallfrown R$ and for $Q\smallfrown\{\alpha\}\smallfrown R$. I guess the ultrafilter is not really needed, as you say, but find it helpful to see what's going on (the argument more or less boils down to there being no non-principal $\aleph_1$-complete ultrafilter). There may be other suboptimal parts in the proof. –  Emil Jeřábek Feb 22 '11 at 19:26
    
I have accepted this answer - after three checks, I didn't find a mistake. So, unless anyone else sees a glitch, this seems to solve it, right? –  Herman Jurjus Feb 22 '11 at 19:36
show 6 more comments

I claim that Q can have no winning strategy, even in the fully general game where there is no restriction on the complexity of sets to be played.

To see this, suppose that we have a strategy $\sigma$ for player Q. That is, $\sigma$ is a function that tells Q what to do after any finitely many moves have been played. Consider the tree $T$ of all finite plays that accord with $\sigma$. Thus, we may imagine that each node in the tree is labeled with the set $Q_i$ that player Q played at that stage, and the tree branches according to the two possible responses of player A. Nodes in the tree correspond to game positions, determined by how player A responded to Q's strategy $\sigma$.

Since the tree is finitely branching, it has only countably nodes altogether, and so there are only countably many nodes in the tree for which $C(i)$ at that node is a singleton. Thus, there must be a real number $z$ that does not appear as a singleton $C(i)$ in any play according to $\sigma$. The real $z$ determines a play for player A, namely, player A should always choose the set containing $z$. This strategy for player A will defeat $\sigma$, since it will avoid all the singleton $C(i)$'s that could possibly arise, while still ensuring that $C(\infty)$ is non-empty. Thus, $\sigma$ is not a winning strategy for player Q.

share|improve this answer
2  
An excellent partial answer! Thanks very much. (How to mark something as 'accepted as partial answer'?) –  Herman Jurjus Feb 18 '11 at 23:30
    
Thanks! Your comment is clear enough; it is too soon to accept anything yet, in my opinion, since the problem is still not settled. –  Joel David Hamkins Feb 19 '11 at 0:07
    
Isn't this a full answer? Since Player 1 doesn't have a winning strategy, Player 2 must have by determinacy (of Gale-Stewart games). This at least if the winning set is Borel. Am I missing something? –  Matteo Mio Feb 19 '11 at 13:07
1  
Matteo, the Borel determinacy result (proved by Martin), applies to games where the plays are integers, but here we have the plays consisting of entire sets of reals. Thus, the determinacy of the game does not seem to follow even from the axiom of determinacy, nor even from $AD_{\mathbb{R}}$. –  Joel David Hamkins Feb 19 '11 at 13:55
1  
@Matteo: Yes, we agree on that. To elaborate, start the game at $i=0$, play on the unit interval [0,1), fix from the start the $A_i$ Q plays, and let $x_i$ be A's decision ($x_i=1$ if he accepts $A_i$, and 0 otherwise). Set $x=x_0.x_1x_2\ldots$ (binary expansion). If we let $A_i$ ($i\ge1$) be the numbers with a 1 in the i'th binary digit, then A wins if $x\in A_0\cup(1+[0,1)\setminus A_0)$ (modulo repeating 1's). As you are using the discrete topology on $\mathcal{P}(\mathbb{R})$ the Borel sets restricts to the standard Borel sets on $x\in[0,2)$. If $A_0$ is not Borel, then the winning –  George Lowther Feb 19 '11 at 16:22
show 10 more comments

Partial answer: It is consistent with ZF that Q has a non-deterministic winning strategy.$\newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}}$

First note that if $C(n)$ is ever reduced to a countable set $\{x_i\ |\ i \in \N\}$, then Q can win just by going through the singletons $\{x_i\}$ one by one; A must reject each in turn to avoid making $C(n+i)$ a singleton, and so in the end $C(\infty)$ is empty.

Now, suppose that the reals can be expressed as a countable union of countable sets, $\R = \bigcup_{i \in \N}R_i$. (This is consistent with ZF.)

Then Q can start out by listing the sets $R_i$. If A ever chooses $A_i = R_i$, then $C(i)$ is reduced to a subset of $R_i$, so is countable, so by the first note above, Q can win. Otherwise, if A always chooses $A_i = R_i^c$, then since $\R = \bigcup_i R_i$, Q wins in the end as $C(\infty)$ is empty.

Note, however, the non-determinism required: Q cannot choose a full deterministic strategy in advance, since that would require choosing an enumeration of each $R_i$; and this cannot exist, since it would render $\R$ countable.


I suspect that even with choice and looking just at deterministic strategies, it’s consistent that either player has a winning strategy or not. Or, if there is a winner, my money would be strongly on A…

share|improve this answer
    
I think that you can show there's no winning deterministic strategy for Q with or without choice. Your answer did cause to me to think about my method though (I'll post an answer when I have a moment) to check it doesn't contradict this. I do tend to agree that it is likely independent of ZFC whether A has a winning strategy, but it's not clear to me. –  George Lowther Feb 18 '11 at 21:01
    
This makes me wonder: in the absense of AC, is there an agreed upon definition of "non-deterministic strategy"? –  Herman Jurjus Feb 22 '11 at 19:34
1  
While I was commenting in another thread, I came across this paper: projecteuclid.org/euclid.pl/1235417276 , where these are defined under the name “quasistrategies”. They are only used there under the assumption of DC, though. However, despite violating DC, Peter's strategy has the key property that for every sequence of moves of A there exists a play following the strategy, so I guess it is fine. –  Emil Jeřábek Feb 22 '11 at 19:42
1  
I realized that this notion is too weak: a quasistrategy only allows to make nondeterministic moves based on previous moves of the two players, but otherwise it's stateless. Here, we need to nondeterministically fix certain auxiliary data (namely, an enumeration of $R_i$) which determines subsequent moves of Q, but which is not itself encoded in any move. It's not hard to formalize this concept in a definition, but I have no idea whether it's in common use, though it seems quite natural (the strategy I gave above for the Baire property restriction is also of this kind if we only have ZF + DC). –  Emil Jeřábek Feb 23 '11 at 12:21
    
What happens when in the formulation of AD the notion of 'strategy' is changed in one of these ways? Do you know of any references for that? Or any people who might know more about that? –  Herman Jurjus Feb 23 '11 at 14:44
add comment

I don't know enough logic to know if the reals possess a countably complete nonprincipal ultrafilter, but A has a winning strategy if the game is played on a set which has one. Choosing such an ultrafilter that contains the co-finite filter, A can always make their choice such that $\bigcap_{k\leq i} A_k$ is in the ultrafilter, since either $Q_i$ or $Q_i^c$ is in the ultrafilter and the filter is closed under finite intersections. Since it is countably complete, it is closed under countable intersections and so $\bigcap_{k \in \mathbb{N}} A_i$ lies in the ultrafilter as well. The intersection has infinitely many elements since the ultrafilter contains the co-finite filter, thus Q never does not win when A uses the strategy "pick whichever set is in the ultrafilter".

Edit: Thanks to those below who pointed out that $\mathbb{R}$ does not, in fact have a countably complete nonprincipal ultrafilter. This gives a cute proof of another partial result: Call a winning strategy for A strong if the choice of $A_i$ depends only on $Q_i$ and not on the previous state of the game. Then A has no strong winning strategy, for if A did, then the sets A would choose form a countably complete nonprincipal ultrafilter (the axioms are fairly easy to prove from the definition of the game).

If one could prove that a winning strategy for A implied the existence of a strong winning strategy for A, this would then show A has no winning strategy, but this seems beyond me.

share|improve this answer
    
@Dan: This is equivalent to the cardinal being measurable, which cannot be proved from ZFC (I recently learned a bit about such things from David Joel Hamkins in some comments to a different answer of mine). The continuum is not measurable according to proposition 1.12.43 of Bogachev, Measure theory. books.google.co.uk/… –  George Lowther Feb 18 '11 at 23:01
    
Actually, I think it is equivalent to the cardinal being at least as large as the smallest measurable cardinal. Still, the existence of measurable cardinals is equivalent to the existence of a countably complete nonprincipal ultrafilter. –  George Lowther Feb 18 '11 at 23:08
2  
And, more importantly, the smallest measurable cardinal is provably greater than $2^{\aleph_0}$. –  François G. Dorais Feb 18 '11 at 23:32
1  
Perhaps more direct: Suppose that such a filter exists on $\mathbb{R}$. Then for at least one $z \in \mathbb{Z}$, $(z, z+1)$ would be in the filter. Then by consecutively dividing intervals, we could form a sequence of intervals, each in the filter, converging to some real, and the singleton set containing this real would then be in the filter, i.e. the filter would not be non-trivial (or 'non-principal', as Dan seems to call it). Or am I overlooking something? –  Herman Jurjus Feb 18 '11 at 23:41
    
Herman: Nice. (Also, apologies to Joel for transposing his first two names in my comment above. I wish we could edit comments.) –  George Lowther Feb 19 '11 at 0:57
add comment

Hi,

Because of some problems with my account (my own mistake, btw), I can't add comments. Apologies for the inconvenience.

To Elohemahab Solomon: This question is not from a book. It was something that occurred to me while thinking about Brouwer style choice sequences in connection with Borel sets.

I'm pretty confident (but not 100% sure yet) that the following holds: When player Q is restricted to give Borel sets, then player A has a winning strategy.

To Denis Serre: Emil is right, I'm afraid. Of course, player Q has a strategy to make sure that $C(\infty)$ has one element. But that's not enough to win the game. Also, as Emil says, when $C(i)$ is ever countable for finite i, then Q can win the game, by eliminating the elements of that countable set, one by one.

Player A has an easy strategy to make sure that $C(i)$ is uncountable for all (finite) i. But that's not enough to describe a winning strategy for player A. For example, when $Q_i = A_i = (0, 1/i)$ for every i, then $C(i)$ is uncountable for every (finite) i, but $C(\infty)$ is empty, and therefore A loses the game.

Dos this help to clarify the problem?

share|improve this answer
    
Two things: 1) The folks over on meta (link in the top right) should be able to help you out with account issues. 2) A lot of this could/should go back in the original question once it all gets worked out. –  Cam McLeman Feb 18 '11 at 17:17
    
@Hermann: even if you don’t have enough rep to add comments, can you still access the account that you used to post the question, and edit these clarifications into the question? That shouldn’t require any rep. Also, I agree with you that I think A has a strategy if Q is restricted to Borel sets — certainly if the restriction is to closed or open sets… –  Peter LeFanu Lumsdaine Feb 18 '11 at 17:27
    
I edited the question, but I'm not sure whether the result is ok, now? –  Herman Jurjus Feb 18 '11 at 19:47
    
I merged the two accounts. There shouldn't be any reason for you to be locked out of the account that posted the question. Even if you lose the password to your OpenID or something similar, you can always click the "Is this your account?" link on your profile page (mathoverflow.net/users/5901). If you remember and can access the email account you provided, you can always get back into your account. –  Anton Geraschenko Feb 22 '11 at 18:12
    
That was the problem: there was a typo in the email address, so I couldn't receive emails sent to that one (my provider changed its domain name, so it didn't allow me to temporarily create an email alias for the wrong address). BTW - Thanks for merging! –  Herman Jurjus Feb 22 '11 at 18:49
add comment

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.