We write N for the set $\{1, 2, 3, . . . \}$ of positive integers. For any positive integer n, we write $[n] = \{1, 2, . . . , n\}$. For any set X, we denote the set $\{A ? X : |A| = r\}$ of subsets of X of size r by $X^{(r)}$
By a k-colouring of $N^{(r)}$, we mean a map c : $N^{(r)}$ ? [k]. We say that a set M ? N is monochromatic for c if $c|_{M^{(r)}}$ is constant.
Ramsey?s Theorem:
Whenever $N^{(2)}$ is 2-coloured, there exists an infinite monochromatic set.
Proof.
Pick $a_1 ? N$. There are infinitely many edges from $a_1$, so we can find an infinite set $M_1 ? N ? \{a_1\}$ such that all edges from a_1 to $M_1$ are the same colour $c_1$.
Now choose $a_2 ? M_1$. There are infinitely many edges from $a_2$ to points in $M_1 ? \{a_2\}$, so we can find an infinite set $M_2 ? M_1 ? \{a_2\}$ such that all edges from $a_2$ to $M_2$ are the same colour, $c_2$.
Continue inductively. We obtain a sequence $a_1, a_2, a_3, . . .$ of distinct elements of N, and a sequence $c_1, c_2, c_3$ of colours such that the edge $a_ia_j (i < j)$ has colour $c_i$. Plainly we must have $c_{i_1} = c_{i_2} = c_{i_3} = \cdots$ for some infinite subsequence. Then $M=\{a_{i_1} , a_{i_2} , a_{i_3} , \cdots\}$ is an infinite monochromatic set.
The result follows.
Remarks
1. The same proof shows that if $N^{(2)}$ is k-coloured then we get an infinite monochromatic set. Alternatively, we could view ?1? and ?2 or 3 or . . . or k? as a 2-colouring of $N^{(2)}$, and then apply above Theorem and use induction on k.
2. An infinite monochromatic set is much more than having arbitrarily large finite monochromatic sets. For example, consider the colouring in which all edges within each of the sets {1, 2}, {3, 4, 5}, {6, 7, 8, 9}, {10, 11, 12, 13, 14}, {15, 16, 17, 18, 19, 20}, . . . are coloured blue and all other edges are coloured red. Here there is no infinite blue monochromatic set, but there are arbitrarily large finite monochromatic blue sets.
Example. Any sequence $(x_n)_{n?N}$ in a totally ordered set has a monotone
subsequence: colour $N^{(2)}$ by giving $ij (i < j)$ colour UP if $x_i < x_j$ and colour
DOWN otherwise; the result follows by above Theorem.
