# 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 ${\u27e8{n}_{i}\u27e9}_{i\in \omega}$ and a sequence of infinite subsets of $\omega $, ${\u27e8{S}_{i}\u27e9}_{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 |