Proof of the Infinite Ramsey Theorem

Question

I am looking for a proof of the infinite Ramsey theorem, I have been unable to find such proof.

Infinite Ramsey Theorem:

Given $ n> 0 $ in $ N $ and $ A \subset N $ infinite, for all finite coloration of $ [\omega] ^ {n} $ there exists $ B \subset A $ infinite such that $ [B] ^ { n} $ is monochromatic.

Answer 1

Proof:

For the case $n = 1 $

$c:[x]^{1}\rightarrow r$

$c:x\rightarrow r$ moreover $[x]^{1}=x$

Where $x=\bigcup\limits_{i=1}^{n = 1} c^{- 1} (i)$

Now by the "Pigeonhole principle" there exists a set $B$, infinite, such that:

$ B\subset x = \bigcup\limits_{i=1}^{n = 1} c^{- 1} (i) $.

For the case $n=2$

$c:[A]^{2}\rightarrow r$

We define:

$a_{0}=min\{ A\}$ and $c_{0}=A-\{ a_{0} \}\rightarrow r$

$c_{0}(a)=c\{a_{0},a\}$, exist $A_{1}\subset A-\{a_{0}\}$ monochromatic for $c_{0} $.

Let $a_{1} = min\{A_ {1}\} $ and $c_{1}: A_{1} - \{a_ {1}\} \rightarrow r $

$c_{1}(a) = c (a_{1}, a) $ exists $ A_{2} \in A_ {1} - \{a_ {1}\}$ monochromatic for $c_{1} $.

 Now, in general, we can define:

$a_{n} = min\{A_ {n}\}$ and $c_{n}: A_{n} - \{a_ {n}\} \rightarrow r$

$ c_{n} (a) = c\{a_ {n}, a\}$

We define the set $B ^{*} = \{a_ {0}, a_ {1}, ...\} $ and:

$c \{a_ {0}, a_ {j}\} = const$ with $ 0 <j $

$c \{a_ {1}, a_ {j}\} = const$ this $ 1 <j $ and so on.

$c \{a_ {i}, a_ {j}) = const$ for $ i <j $.

Now, we define

$c^{*}: B^{*}\rightarrow r$, such that:

$c^{*} (a_{i}) = c(a_{i}, a_{j})_{j> i}$, there is $B\subset B^{*}$ monochromatic for $c^{*}$.

Let $x$ and $y \in B$ such that: $c^{*}(x) = c^{*}(y) = const$

such that: $ c\{x, a\}_{a> x} = c\{y, b\}_{b> y} = const$

and

$c\{x, y\} = const$ for $ y> x $ and $ x> y$.

So $ c:[B]^2 \rightarrow r$ $const$

Suppose it is true for $n-1$. Let's see what happens in $n$

We define: $c: [A]^{n} \rightarrow r$

$a_{0} = min\{a\}$ and $c_{0}: [A- \{a_ {0}\}]^{n-1} \rightarrow r$

and:

$c_{0} \{b_{1}, ..., b_{n-1}\} = c \{a_{0}, b_{1}, ..., b_{n-1}\} $

$A_{1} \subset A-\{a_ {0}\}$

$A_{n} = A_{n-1} -\{a_{n-1}\}$

$a_{n} = min \{A_{n}\}$

$ B^{*} = (a, ...)$

Then we have: $c (a_{j_{1}}, a_{j_{2}}, ..., a{j_{n-1}} ) $

and $ B\subset B^{*} $ is a monochromatic subset.

Answer 2

I think this is not true in this formulation. For $n=2$, try coloration $[a,b] \to \text{Red}$ if $a<b $, $[a,b] \to \text{Blue}$ otherwise.

It is true for the finite colouring of $\left( \begin{array}{c} \omega \\ n \\ \end{array} \right) $ only.

Answer 3

Here is a terser proof, also by induction on $n$ using $k$ colors and practically equivalent. If $n=0$, for any $f:\{\emptyset\}\to [k]$ obviously $A$ is monochromatic.

For the inductive case, suppose we have $f:{\omega\choose n+1}\to [k]$. Define a sequence of infinite sets $A_0\supseteq A_1\supseteq\ldots $ elements $b_0,b_1,\ldots$ colors $c_0,c_1,\ldots$ and functions $f_i:{A_i\choose n}\to [k]$ for all $i$ in the following way: let $a_0=0$ and $A_0=A\setminus\{0\}$, and for each $i$ let $f_i(S)=f(S\cup \{b_i\})$. By induction, we can find an infinite subset $A_{i+1}^*\subseteq A_i$ which is monochromatic with respect to $f_i$ with color $c_{i}$. Then take $b_{i+1}=\min(A_{i+1}^*)$ arbitrarily and let $A_{i+1}=A_{i+1}^*\setminus \{b_{i+1}\}$.

By the pigeonhole principle some color $j$ must appear in the sequence $\langle c_i\rangle$ infinitely many times; let $B=\{b_i\mid c_i=j\}$. Then for any $S\subseteq B$ with $|S|=n$, we simply let $\min(S)=b_i$ so $f(S)=f_i(S\setminus\{b_i\})=c_i=j$ since $S\subseteq B_{i+1}$, so indeed $B$ is monochromatic.