I think my question applies to most games, but for the sake of concreteness, I shall consider one specific game in this question. We consider the game posed by Ilias Kastanas in his paper On the Ramsey property for sets of reals: We first fix some $X \subseteq [\omega]^\omega$.

  1. Player I start by choosing an infinite subset $A_0 \subseteq \omega$.
  2. Player II responds by choosing $x_0 \in A_0$, and then some $B_0 \subseteq A_0$ with $x_0 < \min(B_0)$.
  3. Player I responds by choosing some $A_1 \subseteq B_0$.
  4. Player II responds by choosing $x_1 \in A_1$, and then some $B_1 \subseteq A_1$ with $x_1 < \min(B_1)$.
  5. Etc.

Player I wins iff $\{x_0,x_1,\dots\} \in X$.

Assume that Player I has a winning strategy $\sigma$. If $(A_0,x_0,B_0,\dots,A_n,x_n,B_n)$ is a partial play, then clearly the only things that determine what Player I should respond with are the finite sequence $(x_0,\dots,x_n)$ and $B_n$, Player II's last played set. However, it appears to me that we cannot assume that $\sigma$ satisfies this property. Let's say that $\sigma$ is uniform if $\sigma(A_0,x_0,B_0,\dots,A_n,x_n,B_n)$ only depends on $x_0,x_1,\dots,x_n,B_n$.

If Player I has a winning strategy, does Player I necessarily have a uniform strategy?

I'm also interested in how much the axiom of choice plays a part in the above statement.


1 Answer 1


This is a great question — definitely enjoyed.

Assuming the axiom of choice, then the answer is yes.

Theorem. Assume there is a well ordering of the real numbers. If player I has a winning strategy, then there is a uniform winning strategy.

Proof. Suppose that $\sigma$ is a winning strategy for player I. Fix a well ordering of the collection of sets $B\subseteq\omega$.

Now, suppose that we are playing the game, faced with the actual position $(A_0, x_0, B_0, \ldots,A_n,x_n,B_n)$. But let us look now only at the allowed information for a uniform strategy $(x_0,\ldots,x_n,B_n)$. Consider the least with respect to the well ordering subset $B_n'\subseteq B_n$, such that there is an imaginary play of $B_i'$ that accords with $\sigma$ and the data $(x_0,\ldots,x_n,B_n')$, such that furthermore each $B_i'\subseteq A_i'$ is chosen as least at that stage, subject to being compatible with the data up to $n$. Let $\sigma$ respond to this imaginary play to give us a set $A_{n+1}$, which we now play as the result for this new strategy.

Since the play depended only on $(x_0,\ldots,x_n,B_n)$, I have described a uniform strategy. Let me prove that it is winning. What I claim is that every sequence $x_0,x_1,x_2,\ldots$ arising from a play according to this uniform strategy can be realized as arising in a play according to $\sigma$. The key point is that as $n$ increases, the imaginary sets $B_i'$ will eventually stabilize for each $i$. To see this, consider what happens at stage $n+1$, after we've played $A_{n+1}$. The actual play will respond with some $x_{n+1}\in A_{n+1}$ and $B_{n+1}\subseteq A_{n+1}$, and we will forget about the actual $B_n$ and find some minimal $B_{n+1}''\subset B_{n+1}$ and new imaginary sets $B_i''$ that produce a play according with $\sigma$ and the data $(x_0,\ldots,x_{n+1},B_{n+1}'')$, and is minimal at each stage $i$. But the point now is that the requirement on $B_i''$ is a bit lighter than that on the imaginary set $B_i'$ chosen at stage $n$, provided that $x_{n+1}$ is in $B_n$, which it is. Earlier, we needed $B_i'$ to contain $B_n'$, but now we only need it to contain $B_{n+1}''$, which is strictly smaller. So the set $B_i''$ will be either equal to $B_i'$ or preceed it in the well order. But it can only go down in the well order finitely often, and so eventually, for any given $i$, the imaginary versions of $B_i'''$ will stabilize. In other words, if we have an infinite play according to the uniform strategy, we can find choices of $B_i'''$ that give rise to the whole play. And since this imaginary play accords with $\sigma$, the set $\{x_0,x_1,\ldots\}$ will be in $X$, as desired. $\Box$

  • $\begingroup$ Thanks Joel, very nice! Do you have any clue on how necessary choice is? $\endgroup$ Aug 24 at 3:03
  • $\begingroup$ This argument clearly uses choice in a fundamental way. I don't have a good idea for what happens when choice fails. $\endgroup$ Aug 24 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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