2
$\begingroup$

Let $I \subseteq 2^\omega$ be any $F_\sigma$ ideal containing every finite sets :

  • $\forall X \in I\ \forall Y \subseteq X\ \text{ we have } Y \in I$
  • $\forall k\ \forall X_1,\dots,X_k \in I\ X_1 \cup \dots \cup X_k \in I$

Let $f:[\omega]^{2} \rightarrow \{0,1,2\}$ be an instance of $\mathrm{RT}^2_{3,2}$, that is, the following weakening on Ramsey's theorem for pairs :

  • $f$ colors the unordered pairs of integers to by $0, 1$ or $2$.
  • A solution to $f$ is an infinite set $X$ and a color $i \in \{0,1,2\}$ such that every pair in $X$ avoids the color $i$

The existence of a solution to $f$ is guarantied by Ramsey's theorem for pair. The question is :

can we always make sure that $f$ has a solution outside of $I$ ?

It is not the case if one wants a solution to have exactly one color : one can for instance easily design a computable coloring such that every solution is sparse enough to fall in the $\Sigma^0_2$ ideals of elements $\{X\ :\ \sum_{n \in X} 1/(n+1) \text{ is finite}\}$.

But what about the above weakening of Ramsey theorem for pairs ?

$\endgroup$

1 Answer 1

2
$\begingroup$

Well, a positive answer would have been nice, but unfortunately I think there is an easy argument to build a computable instance of $\mathrm{RT^2_{3,2}}$ whose every solution falls in the summable ideal:

Erdös showed $R(n,n) > n^3$ for $n$ large enough : the minimum $m$ such that every coloring of pairs of integer smaller than $m$ have a homogeneous set of size at least $n$, is bigger than $n^3$.

Let $M_{n+1} = M_n + (n+1)^3$. Let $f$ be the computable coloring such that every pair of integers between $M_n$ and $M_{n+1}$ is colored by $0$ or $1$ in such a way that any homogeneous set has size smaller than $n$. For every $x \in [M_n, M_{n+1}]$ and every $y > M_{n+1}$ we set $f(x,y) = 2$.

Every infinite set must have pairs of color $2$. If such a set always avoid one of the other color, then it have at most $n$ integers in each $[M_n, M_{n+1}]$ and the sum of $1/x$ for each of these integer is bounded by $n/n^3 = 1/n^2$. Thus the overall sum is finite.

$\endgroup$

You must log in to answer this question.

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