2 ack horrid typo!

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_i$ 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$ Q can win. Otherwise, if A always chooses $A_i = R_i^c$, then since $\R = \bigcup_i R_i$, $Q$ 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 strongly 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…

1

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_i$ 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 strongly 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…