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
2 mention consistency
1