Super Ramsey's Theorem

56 Views Asked by At

The following is the infinite version of Ramsey's Theorem

Ramsey's Theorem

Given positive integers $r$ and $n$, if the subsets with $n$ elements of the infinite set $X$ are colored, each with one of $r$ different colors, then there is an infinite homogeneous subset of $X$.

With no much effort one can prove this version of the theorem

Given positive integers $r$ and $n$, if the subsets with at most $n$ elements of the infinite set $X$ are colored, each with one of $r$ different colors, then there is an infinite homogeneous subset of $X$.

I wonder if this super version of the theorem is true

Given the positive integer $r$, if the finite subsets of the infinite set $X$ are colored, each with one of $r$ different colors, then there is an infinite homogeneous subset of $X$.

Here, an homogeneous subset $H\subset X$ is a set such that every colored subset of $H$ has the same color.

1

There are 1 best solutions below

0
On BEST ANSWER

The statement for coloring all finite subsets is false.

Let $X$ be a countably infinite set $\{x_1, x_2, x_3, \dots\}$. For each $k\ge 1$, color the $k$-element subsets of $X$ red and blue as follows: $S$ is red if $x_k \in S$, and blue otherwise.

Suppose for the sake of contradiction that there is an infinite subset $H \subset X$ which is homogeneous in every finite size. Not every $k$-element subset $S \subset H$ can contain $x_k$, so it's impossible for every $k$-element subset of $H$ to be red. Therefore we must ensure that every $k$-element subset of $H$ is blue, which means that $x_k \notin H$. However, since this is true for all $k$, no element of $X$ can be in $H$, which is a contradiction.