## Return to Answer

6 explicit diagonalization

This can be arranged as follows. Let `$Q_i=V\vartriangle M$` be given, where $V$ is open and $M$ is meagremeager. If `$I_{i-1}\cap V\ne\varnothing$`, A choses 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 theopen 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}$`.

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$ `$\bigcap_{i\in\omega}A_i\supseteq\bigcap_{i\in\omega}P_i$` is nonempty by compactness.

In order to prove the theorem, observe that there are $2^\omega$ \mathfrak c=2^\omega$perfect subsets of$2^\omega$, and each of them has cardinality$2^\omega$, hence by an obvious diagonalization so we can construct$X\subseteq2^\omega$such that neither$X$nor enumerate them as `$X^c$ contains a perfect subset \{P_\alpha\mid\alpha<\mathfrak c\}$`. (this This is the place which does not work breaks in ZF + DC, we need$2^\omega$to be well ordered)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.

5 measurable sets

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"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.

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<2^{<\omega}\}$t\in2^{<\omega}\}$` such that

4 minor corrections

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 meagre. If `$I_{i-1}\cap V\ne\varnothing$`, A choses $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 theopen 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.

In ZFC, neither player has a winning strategy. 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<2^\omega\}$<2^{<\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 $2^\omega$ perfect subsets of $2^\omega$, and each of them has cardinality $2^\omega$, hence by an obvious diagonalization we can construct $X\subseteq2^\omega$ such that neither $X$ nor $X^c$ contains a perfect subset (this is the place which does not work in ZF + DC, we need $2^\omega$ to be well ordered). 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.

3 the game is not determined

My guess is that neither

Neither player has a winning strategy. Since arbitrary subsets of reals are allowed, there is absolutely no structure in the problem, and I can't imagine a winning strategy based on cardinalities alonesee below.

In the restricted game, we can write $A_i=U_i\triangle\bigcup_jM_{p(i,j)}$, A_i=U_i\vartriangle\bigcup_jM_{p(i,j)}$, where$U_i$is open,$M_k$are nowhere dense, and$p\colon\omega^2\to\omega$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

This can be arranged as follows. Let `$Q_i=V\triangle Q_i=V\vartriangle M$` be given, where $V$ is open and $M$ is meagre. If `$I_{i-1}\cap V\ne\varnothing$`, A choses $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 theopen 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}$`.

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.

In ZFC, neither player has a winning strategy. 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$ 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, 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<2^\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 $2^\omega$ perfect subsets of $2^\omega$, and each of them has cardinality $2^\omega$, hence by an obvious diagonalization we can construct $X\subseteq2^\omega$ such that neither $X$ nor $X^c$ contains a perfect subset (this is the place which does not work in ZF + DC, we need $2^\omega$ to be well ordered). 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.

2 mention consistency

My guess is that neither player has a winning strategy. Since arbitrary subsets of reals are allowed, there is absolutely no structure in the problem, and I can't imagine a winning strategy based on cardinalities alone.

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\triangle\bigcup_jM_{p(i,j)}$, where $U_i$ is open, $M_k$ are nowhere dense, and $p\colon\omega^2\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\triangle M$` be given, where $V$ is open and $M$ is meagre. If `$I_{i-1}\cap V\ne\varnothing$`, A choses $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 theopen 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 winning strategy in the unrestricted game.

1

My guess is that neither player has a winning strategy. Since arbitrary subsets of reals are allowed, there is absolutely no structure in the problem, and I can't imagine a winning strategy based on cardinalities alone.

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\triangle\bigcup_jM_{p(i,j)}$, where $U_i$ is open, $M_k$ are nowhere dense, and $p\colon\omega^2\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\triangle M$` be given, where $V$ is open and $M$ is meagre. If `$I_{i-1}\cap V\ne\varnothing$`, A choses $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 theopen 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 258, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9286906719207764, "perplexity_flag": "middle"}