18
$\begingroup$

Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$.

Alice's color is red and Bob's color is blue. In each step, for each $s\in S$, a player will choose finitely many uncolored elements in $R\times\{s\}$ and color them with its color (of the player). Alice is the first to play and from then on the players alternate, with Alice starting in each limit step. Bob wins the game if, at any time, for all $s_1, s_2\in S$ there is $r\in R$ such that both $(r, s_1)$ and $(r, s_2)$ are colored blue.

Is there a winning strategy for Bob?

Of course, this game might take infinitely many steps, but notice Alice can force the game to end after at most $|R|$ steps (but no earlier) by making sure $R\times S$ is completely colored by the end of it. Also, it would take no more than $|S|$ steps for Bob to color blue a pair $(r, s_1)$, $(r, s_2)$ for all $(s_1, s_2)\in S^2$, therefore, Bob does have a winning strategy if $|R|\ge|S|$.

General case seems very difficult. I'm mostly interested in the case where $|R|=\aleph_0$ and $|S|=\mathfrak c:=2^{\aleph_0}$.

$\endgroup$
2
  • 5
    $\begingroup$ If $|S|<|R|$, then Bob can win on his first move, since Alice places only $|S|$ colors altogether, which therefore can't use every element $r\in R$, and so there is a free column $\{r\}\times S$ for Bob to color completely blue. $\endgroup$ Commented Feb 28 at 16:25
  • 1
    $\begingroup$ Assume $|R|=\mathbb{N}$. Supposing a player has decided on a strategy, then that player could supplement that strategy with an extra step, where if $(r,s)$ is colored, and $(r',s)$ is uncolored with $r'<r$, then they also color $(r',s)$. This extra step cannot hurt them in any way. So, we may assume that both players follow this extra supplement. So, rather than color random finite subsets, they both color consecutive blocks. In other words, the coloring in each column $R\times \{s\}$ is determined by a list of integers. This suggests some sort of connection to the axiom of determinacy. $\endgroup$ Commented Mar 5 at 15:43

1 Answer 1

11
$\begingroup$

The following partial answer (inspired by Pace Nielsen's deleted answer) addresses only the instances where $|R|=\aleph_0$ and $|S|\gt2^{\aleph_0}$. I claim that it's consistent (relative to the consistency of a measurable cardinal) that Alice has a winning strategy in these cases.

Given an infinite cardinal $\kappa$, let $G(\kappa)$ denote the game played by Alice and Bob on $R\times S$ where $R=\mathbb N$ and $|S|=\kappa$, but with the payoff modified in Bob's favor as follows: The set $S$ is partitioned into disjoint sets $S_1$ and $S_2$ with $|S_1|=|S_2|=\kappa$; Alice wins iff there exist $s_1\in S_1$ and $s_2\in S_2$ such that, for each $r\in R$, at least one of $(r,s_1)$ and $(r,s_2)$ is colored red. Plainly, if Alice wins this "bipartite" game, then she also wins the original game.

In fact I will show that Alice has a winning strategy in the game $G(\kappa)$ on the assumption that White has a winning strategy in a certain game $U(\kappa)$ which was suggested (in a slightly different form) on pp. 346–347 of S. Ulam, Combinatorial analysis in infinite sets and some physical theories, SIAM Review 6 (1964) 343–355, and discussed by F. Galvin and M. Scheepers, Baire spaces and infinite games, Arch. Math. Logic 55 (2016), 85–104.

The game I call $U(\kappa)$ is $\mathbf{UG}(\aleph_0,\kappa)$ in the notation of G & S, whose exposition of unpublished work of J. Baumgartner, C. Gray, R. Laver, M. Magidor, and R. Solovay (the history is summarized in Section 4 of the paper) includes the following results:

Theorem 11. White has no winning strategy in $U(2^{\aleph_0})$.

Theorem 17. If it's consistent that there is an uncountable measurable cardinal, then it's consistent that $2^{\aleph_0}=\aleph_1$ and White has a winning strategy in $U(\aleph_2)$.

Definition. The game $U(\kappa)$ is played on a set $E$ of cardinality $\kappa$. First White partitions $E$ into $\aleph_0$ pieces (some of which may be empty) and Black chooses one of those pieces, call it $B_1$. Then Black partitions $B_1$ into $\aleph_0$ pieces and White chooses one of them, call it $W_1$. Then White partitions $W_1$ into $\aleph_0$ pieces, and so on. White wins if the sequence $B_1\supseteq W_1\supseteq B_2\supseteq W_2\supseteq\cdots$ (of length $\omega$) has a nonempty intersection.

Theorem. If White has a winning strategy in $U(\kappa)$, then Alice has a winning strategy in $G(\kappa)$.

Proof. We may assume that the game $G(\kappa)$ is played in the following way: in the $n^\text{th}$ inning, first Alice chooses a function $f_n:S\to\mathbb N$ and colors red all uncolored points $(r,s)$ with $r\le\max\{n,f_n(s)\}$, and then Bob chooses a function $g_n:S\to\mathbb N$ and colors blue all uncolored points $(r,s)$ with $r\le g_n(s)$. (So everything will be colored after $\omega$ moves.)

Alice's strategy works independently on $S_1$ and $S_2$. To keep the notation simple I'll describe what happens on $S_1$; the play on $S_2$ is similar. Let $\sigma$ be a winning strategy for White in $U(S_1)$, the game $U(\kappa)$ played on the set $S_1$. As the game $G(\kappa)$ proceeds, Alice will imagine a branching tree of $\sigma$-plays of $U(S_1)$.

First, Alice partitions $S_1$ into $\aleph_0$ pieces $P_1,P_2,\dots$ according to the strategy $\sigma$, and then chooses an unbounded function $f_1:S_1\to\mathbb N$ which is constant on each piece. (Of course $P_i\ne\varnothing$ since $\sigma$ is a winning strategy.) We don't know which piece Black will choose, so each $P_i$ becomes a "parallel world"; further play on $P_i$ proceeds as if $P_i$ had been chosen by Black in $U(S_1)$.

Next, Bob chooses a function $g_1:S_1\to\mathbb N$. Alice imagines that Black has partitioned each P_i into $\aleph_0$ smaller pieces $P_{i,j}$ on which $g_1$ in constant. For each $i$ she chooses a piece $P_{i,j}$ according to the strategy $\sigma$. From now on Alice doesn't care what happens on the unchosen pieces, but she partitions each chosen piece $P_{i,j}$ into $\aleph_0$ pieces $P_{i,j,k}$ according to $\sigma$, and so forth.

I've described a strategy for Alice in $G(\kappa)$. To show that Alice wins, I will construct for each $i\in\{1,2\}$ a $\sigma$-play of $U(S_i)$ and let $s_i$ be a point in the (nonempty) intersection of the chosen sets.

First, let's make Black's first move in $G(S_1)$ by choosing (arbitrarily) one of the pieces $P_i$ from White's initial partition; call the chosen piece $B^1_1$. After Black chose $B^1_1$ he partitioned it into $\aleph_0$ pieces (level sets of $g_1|B^1_1$) and White chose one of them which we call $W^1_1$. Now we have $B^1_1\supseteq W^1_1$; $f_1$ is constant on $B^1_1$ and $g_1$ is constant on $W^1_1$.

Next we make Black's first move in $G(S_2)$, choosing $B^2_1$ so that $f_1(B^2_1)\ge g_1(W^1_1)$, thus ensuring for all $s_1\in W^1_1$ and $s_2\in B^2_1$, and for all $r\in\mathbb N$, that if $(r,s_1)$ was colored blue on Bob's first turn, then $(r,s_2)$ was colored red on Alice's first turn.

Next Black partitioned $B^2_1$ into $\aleph_0$ pieces and White chose one them, call it $W^2_1$, on which $g_1$ is constant. Going back to $S_1$, White partitioned $W^1_1$ into $\aleph_0$ pieces on which $f_2$ is constant; we make Black's next move in $U(S_1)$, choosing a piece $B^1_2\subseteq W^1_1$ with $f_2(B^1_2)\ge g_1(W^2_1)$, thus ensuring for all $s_1\in B^1_2$ and $s_2\in W^2_1$ and for all $r\in\mathbb N$, that if $(r,s_2)$ was colored blue on Bob's first turn, then it was colored red on Alice's second turn, if not sooner.

Continuing in this way, we construct plays of $G(S_1)$ and $G(S_2)$ which are won by White, so we can find a point $s_1\in B^1_1\cap W^1_1\cap B^1_2\cap\cdots$ and a point $s_2\in B^2_1\cap W^2_1\cap B^2_2\cap\cdots$, and for each $r\in\mathbb N$ at least one of the points $(r,s_1)$ and $(r,s_2)$ will be colored red.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .