Infinite Ramsey's Theorem
Theorem
For any set $S$, let $S^{(n)}$ denote the set $\{\{s_1, \dots, s_n\} : \text{each }s_i \in S\}$ of cardinality $n$ subsets of $S$.
If $X$ is an infinite set, then for every partition $P$ of $X^{(n)}$ into $k$ many components, there is an infinite subset $Y \subseteq X$ such that each member of $Y^{(n)}$ is in the same component of $P$.
Note
The case $n=1$ of this theorem is often referred to as an infinite Pigeonhole Principle, since it essentially says that if an infinite set is partitioned into finitely many components, there are infinitely many elements that are sent to the same component.
Partition theorems like this one are commonly stated in terms of graph colorings. Using this language, this theorem could be stated as "For any coloring of a graph whose vertices correspond to the size $n$ subsets of an infinite set $X$ by $k$-many colors, there is an infinite subset $Y\subseteq X$ such that each vertex corresponding to a size $n$ subset of $Y$ is colored the same."
Proof
We will prove the theorem for fixed $k$ by induction on $n$.
- Base case $n=1$ ("Infinite Pigeonhole Principle"):
In this case, $X^{(n)}$ is the set of singletons of elements of $X$, and so to ease exposition, we will identify $X^{(n)}$ with $X$ and just speak of partitions of $X$.
Let $P$ be a partition of $X$ into $k$ many components $X_1, \dots, X_k$.
We have $X = X_1 \cup \cdots \cup X_k$.
If each $X_i$ were finite, then $X$ would be a finite union of finite sets, and hence finite.
Thus, at least one of the $X_i$ must be infinite.
But, taking $Y$ to be an infinite $X_i$ gives us the required subset for the theorem.
- Inductive step. Suppose the theorem holds for all $i < n$. We prove it holds for $n$:
Since $X$ is infinite, there is an injection of $\mathbb{N}$ into $X$. Again, to ease exposition, since all we need to do to prove the theorem is find an infinite subset of $X$, we will view $\mathbb{N}$ as a subset of $X$ and find an infinite subset of $\mathbb{N}$.
Write the components of $P$ as $S_1, \dots, S_k$.
For each $a \in \mathbb N$, let $P_a$ be the partition on $(\mathbb N - \{a\})^{(n-1)}$ into $k$ components $S_{a,1}, \dots, S_{a,k}$ defined by assigning $\{b_1, \dots, b_{n-1}\} \in (\mathbb N - \{a\})^{(n-1)}$ to $S_{a,j}$ if and only if $\{a, b_1, \dots, b_{n-1}\} \in {\mathbb N}^{(n)}$ is in $S_j$.
Note that the theorem holds for $P_a$ by the inductive hypothesis.
Now, we inductively define $a_0 < a_1 < \dots$ and infinite sets $X_0 \supseteq X_1 \supseteq \cdots$ such that $a_i$ is the smallest element of $X_i$.
Let $a_0 = 0$, and let $X_0 = \mathbb N$.
Once $X_i$ and $a_i$ are defined,
let $X_{i+1}$ be an infinite subset of $X_i - \{a_i\}$ satisfying the theorem for the partition $P_{a_i}$ of $n-1$ size subsets, which exists by the inductive hypothesis, and
let $a_{i+1}$ be the smallest element of $X_{i+1}$, which exists by the Well-Ordering Principle.
Note that $a_{i+1} > a_i$ since $X_{i+1}$ is a subset of $X_i$ not containing the smallest element $a_i$ of $X_i$.
We constructed each $X_{i+1}$ so that each element of $X_{i+1}^{(n)}$ is in the same component of $P_{a_i}$.
So, we may consider the sequence $(k_i)_{i\in\mathbb N}$ where each $k_i$ is such that all elements of $X_{i+1}^{(n)}$ are in the component $S_{a_i, k_i}$ of $P_{a_i}$.
Since each $k_i$ is one of $1,\dots, k$, but there are infinitely many $i\in \mathbb N$, this forms a partition of $\mathbb N$ to which we can apply the base case of this proof.
This means that there is some $c$ among $1,\dots, k$, there is an infinite set $I = \{i \in \mathbb N : k_i = c\}$.
Define $Y = \{a_i : i \in I\}$.
$Y$ is infinite since $I$ is infinite and each $a_i$ is distinct by construction.
We now verify that each element of $Y^{(n)}$ is in the same component $S_c$ of $P$.
Let $\{y_1, \dots, y_n\} \in Y^{(n)}$. We may take $y_1 < \cdots < y_n$ by relabeling if necessary.
There is some $i\in I$ for which $y_1 = a_i$. By construction, $y_1 = a_i$ is the least element of $X_i$, each $y_2, \dots, y_n$ is in $X_i$, and each element of $X_i^{(n-1)}$ is in the component $S_{a_i, c}$ of the partition $P_{a_i}$.
But then, by definition of $P_{a_i}$, since $\{y_2, \dots, y_n\} \in S_{a_i , c}$, we have $\{y_1, y_2, \dots, y_n\} = \{a_i, y_2, \dots, y_n\} \in S_c$.
$\blacksquare$
