Ramsey’s theorem

Ramsey’s theorem states that a particular arrows relation,

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

holds for any integers $n$ and $k$ .

In words, if $f$ is a function on sets of integers of size $n$ whose range is finite then there is some infinite $X\subseteq\omega$ such that $f$ is constant on the subsets of $X$ of size $n$ .

As an example, consider the case where $n=k=2$ , and $f\colon[\omega]^{2}\rightarrow\{0,1\}$ is defined by:

f(\{x,y\})=\left\{\begin{array}[]{ll}1&\text{ if ~{}}x=y^{2}\text{ or ~{}}y=x^% {2}\\ 0&\text{otherwise}\end{array}\right.

Then let $X\subseteq\omega$ be the set of integers which are not perfect squares. This is clearly infinite, and obviously if $x,y\in X$ then neither $x=y^{2}$ nor $y=x^{2}$ , so $f$ is homogeneous on $X$ .

Title	Ramsey’s theorem
Canonical name	RamseysTheorem
Date of creation	2013-03-22 12:55:49
Last modified on	2013-03-22 12:55:49
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	9
Author	mathcam (2727)
Entry type	Theorem
Classification	msc 05D10
Related topic	RamseysTheorem2
Related topic	GraphTheory