# proof of Ramsey’s theorem

 $\omega\rightarrow(\omega)^{n}_{k}$

is proven by induction on $n$.

If $n=1$ then this just states that any partition of an infinite set into a finite number of subsets must include an infinite set; that is, the union of a finite number of finite sets is finite. This is simple enough to prove: since there are a finite number of sets, there is a largest set of size $x$. Let the number of sets be $y$. Then the size of the union is no more than $xy$.

If

 $\omega\rightarrow(\omega)^{n}_{k}$

then we can show that

 $\omega\rightarrow(\omega)^{n+1}_{k}$

Let $f$ be some coloring of $[S]^{n+1}$ by $k$ where $S$ is an infinite subset of $\omega$. Observe that, given an $x<\omega$, we can define $f^{x}\colon[S\setminus\{x\}]^{n}\rightarrow k$ by $f^{x}(X)=f(\{x\}\cup X)$. Since $S$ is infinite, by the induction hypothesis this will have an infinite homogeneous set.

Then we define a sequence of integers $\langle n_{i}\rangle_{i\in\omega}$ and a sequence of infinite subsets of $\omega$, $\langle S_{i}\rangle_{i\in\omega}$ by induction. Let $n_{0}=0$ and let $S_{0}=\omega$. Given $n_{i}$ and $S_{i}$ for $i\leq j$ we can define $S_{j}$ as an infinite homogeneous set for $f^{n_{i}}\colon[S_{j-1}]^{n}\rightarrow k$ and $n_{j}$ as the least element of $S_{j}$.

Obviously $N=\bigcup\{n_{i}\}$ is infinite, and it is also homogeneous, since each $n_{i}$ is contained in $S_{j}$ for each $j\leq i$.

Title proof of Ramsey’s theorem ProofOfRamseysTheorem 2013-03-22 12:55:52 2013-03-22 12:55:52 mathcam (2727) mathcam (2727) 8 mathcam (2727) Proof msc 05D10