proof of Ramsey’s theorem

$$\omega \to {(\omega )}_k^n$$

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 \to {(\omega )}_k^n$$

then we can show that

$$\omega \to {(\omega )}_k^{n+1}$$

Let $f$ be some coloring of ${[S]}^{n+1}$ by $k$ where $S$ is an infinite subset of $\omega$. Observe that, given an , we can define $f^x:{[S\setminus \{x\}]}^n\to 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 ${⟨n_i⟩}_{i\in \omega }$ and a sequence of infinite subsets of $\omega$, ${⟨S_i⟩}_{i\in \omega }$ by induction. Let $n_0=0$ and let $S_0=\omega$. Given $n_i$ and $S_i$ for $i\le j$ we can define $S_j$ as an infinite homogeneous set for $f^{n_i}:{[S_{j-1}]}^n\to 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\le i$.

Title	proof of Ramsey’s theorem
Canonical name	ProofOfRamseysTheorem
Date of creation	2013-03-22 12:55:52
Last modified on	2013-03-22 12:55:52
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	8
Author	mathcam (2727)
Entry type	Proof
Classification	msc 05D10