# Games and Ramsey's theorem

Here, we identify subsets of $$\mathbb{N}$$ with sequences obtained by listing the members of the set in strictly increasing order. Suppose that we have some set $$\mathcal{F}$$ of sets (sequences) of the form $$(m_n, l_n)_{n=1}^t$$. We let $$\mathcal{U}$$ denote the set of all $$(m_n, l_n)_{n=1}^\infty$$ such that $$(m_n, l_n)_{n=1}^t\in \mathcal{F}$$ for all $$t\in\mathbb{N}$$. We let $$\mathcal{V}$$ denote the set of all $$(m_n)_{n=1}^\infty$$ such that there exists $$(l_n)_{n=1}^\infty$$ such that $$(m_n, l_n)_{n=1}^\infty \in \mathcal{U}$$.

It is easy to see that $$\mathcal{U}$$ is closed and $$\mathcal{V}$$ is analytic (in either the Cantor or Ellentuck topology). Suppose also that for every infinite subset $$K$$ of $$\mathbb{N}$$, there exists a further, infinite subset $$M$$ of $$L$$ such that every infinite subset of $$M$$ lies in $$\mathcal{V}$$.

Is it known that the latter property is equivalent to a winning strategy for a certain player in some two player game?

• I don't get it. In the first sentence you talk about subsets of $\mathbb N$. So how is $(m_n,l_n))_{n=1}^t$ a subset of $\mathbb N$? Isn't it a subset of $\mathbb N\times\mathbb N$? – bof Jun 24 '19 at 4:24
• The object of interest is $\mathcal{V}$, which consists of subsets of $\mathbb{N}$. – user78375 Jun 24 '19 at 11:08
• Voted to close as unclear what you're asking because I had the same question as @bof and the OP refused to answer it. – Steven Landsburg Jun 24 '19 at 17:21

If you mean completely Ramsey sets there is the following characterization using the Kastanas game. Let's start with some definitions :

1. Here the letters $$a, b, c, ...$$ vary over finite subsets of $$\mathbb{N}$$ and $$A, B, C, ...$$ over infinite subsets of $$\mathbb{N}$$.

• Let $$a$$ and $$A$$, we write $$a if $$a=\emptyset$$ or $$max(a).

• For $$a, let $$[a, A]=\{S\in [\mathbb{N}]^{\aleph_{0}} : a\subseteq S\subseteq a\cup S \}= \{a\cup C\in [\mathbb{N}]^{\aleph_{0}} : a Note that $$[\emptyset, A]=[A]^{\aleph_{0}}$$

• A set $$X\subseteq [\mathbb{N}]^{\aleph_{0}}$$ is called Ramsey if there is $$A$$ with $$[\emptyset, A]\subseteq X$$ or $$[\emptyset, A]\subseteq\hspace{0.1cm}\sim X$$, here $$\sim X$$ denotes the complement of $$X$$.

• A set $$X\subseteq [\mathbb{N}]^{\aleph_{0}}$$ is called completely Ramsey if for every $$a there is $$B\subseteq A$$ with $$[a, B]\subseteq X$$ or $$[a, B]\subseteq\hspace{0.1cm} \sim X$$.

2. Let $$A \subseteq [\omega]^{\omega}$$ = the set of infinite sets of integers. Then $$A$$ has a homogeneous set $$H$$ if, by definition, $$H \in [\omega]^{\omega}$$ and either every infinite subset of $$H$$ belongs to $$A$$ or every infinite subset of H belongs to the complement of $$A$$. $$A$$ has the Ramsey property iff it has a homogeneous set.

3. Kastanas's game. For $$\varphi\subseteq [\omega]^{\omega}$$ we define the game $$G_{\varphi}$$ as follows :

Player I wins if $$\{n_{0}, n_{1}, \cdots \}\in\varphi$$

Theorem (Kastanas)

a.) Player I has a winning strategy in $$G_{\varphi}$$, iff there is a homogeneous set in $$\varphi$$ (i.e. an infinite $$H$$ such that every infinite subset of it belongs to $$\varphi$$)

b.) Player II has a winning strategy in $$G_{\varphi}$$ iff for every $$A$$ there is a subset of it homogeneous in $$[\omega]^{\omega}\setminus \varphi$$.

For the information of the bibliography we have the following article "On the Ramsey Property for Sets of Reals" Author: Ilias G. Kastanas.

• This is about as far as I had gotten. The hypothesis that for every infinite subset $K$ of $\mathbb{N}$, there exists a further subset $M$ which is homogeneous in $\mathcal{V}$. If we write $M=(m_n)_{n=1}^\infty$, this means there exists $(l_n)_{n=1}^\infty$ such that $(m_n, l_n)_{n=1}^t\in \mathcal{F}$ for all $t$. However, this is only good enough to let me choose $(l_n)_{n=1}^\infty$ after all $(m_n)_{n=1}^\infty$ have been chosen. – user78375 Jun 24 '19 at 0:47
• Since whether or not a sequence $(m_n, l_n)_{n=1}^\infty$ lies in $\mathcal{V}$ depends only on its initial segments, I would like to know if it is possible to choose the $l_n$ sequence in a game without future information. That is, if every $A$ has a subset homogeneous in $\mathcal{V}$, is it possible to write down game where Players take turns choosing infinite subsets and $m_n, l_n$ values, and one of the players wins if $(m_n, l_n)_{n=1}^\infty\in \mathcal{U}$ (equivalently, $(m_n, l_n)_{n=1}^t\in \mathcal{F}$ for all $t$? Basically, can we choose the $l_n$ concurrently with the $m_n$? – user78375 Jun 24 '19 at 0:51