Infinite Ramsey's Theorem

== Theorem ==
Let $k, n \in \N$.
For any set $S$, let $S^{\paren n}$ denote the set $\set {\set {s_1, \ldots, s_n}: \text{each } s_i \in S}$ of cardinality $n$ subsets of $S$.
Let $X$ be an infinite set.
Then:
:for every partition $P$ of $X^{\paren n}$ into $k$ many components
:there is an infinite subset $Y \subseteq X$
such that:
:each member of $Y^{\paren n}$ is in the same component of $P$.
== Proof ==
We will prove the theorem for fixed $k$ by induction on $n$.
=== Basis for the Induction ===
The case $n = 1$ ("Infinite Pigeonhole Principle"):
In this case, $X^{\paren n}$ is the set of singletons of elements of $X$.
So to ease exposition, we will identify $X^{\paren 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.
This is the basis for the induction.
=== Induction Hypothesis ===
The induction hypothesis is that:
For every partition $P$ of $X^{\paren {n - 1} }$ into $k$ many components
:there is an infinite subset $Y \subseteq X$
such that:
:each member of $Y^{\paren {n - 1} }$ is in the same component of $P$.
It is to be proved that:
For every partition $P$ of $X^{\paren n}$ into $k$ many components
:there is an infinite subset $Y \subseteq X$
such that:
:each member of $Y^{\paren n}$ is in the same component of $P$.
=== Induction Step ===
This is the induction step:
Suppose the theorem holds for all $i < n$.
It is to be proved that it holds for $n$.
Since $X$ is infinite, there is an injection of $\N$ into $X$.
All that is needed to be done to prove the theorem is to find an infinite subset of $X$
So, to ease exposition, $\N$ will be viewed as a subset of $X$.
The proof will proceed by finding an infinite subset of $\N$.
Write the components of $P$ as $S_1, \ldots, S_k$.
For each $a \in \N$, let $P_a$ be the partition on $\paren {\N \setminus \set a}^{\paren {n - 1} }$ into $k$ components:
:$S_{a, 1}, \dots, S_{a, k}$
defined by assigning:
:$\set {b_1, \ldots, b_{n - 1} } \in \paren {\N \setminus \set a}^{\paren {n - 1} }$
to $S_{a, j}$ :
:$\set {a, b_1, \ldots, b_{n - 1} } \in \N^{\paren n}$ is in $S_j$
Note that the theorem holds for $P_a$ by the induction 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 = \N$.
Once $X_i$ and $a_i$ are defined:
Let $X_{i + 1}$ be an infinite subset of $X_i \setminus \set {a_i}$ satisfying the theorem for the partition $P_{a_i}$ of $n - 1$ size subsets.
This exists by the induction hypothesis.
Let $a_{i + 1}$ be the smallest element of $X_{i+1}$.
This 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}^{\paren {n - 1} }$ is in the same component of $P_{a_i}$.
So, we may consider the sequence $\sequence {k_i}_{i \mathop \in \N}$ where each $k_i$ is such that all elements of $X_{i + 1}^{\paren {n - 1} }$ are in the component $S_{a_i, k_i}$ of $P_{a_i}$.
Since each $k_i$ is one of $1, \ldots, k$, but there are infinitely many $i \in \N$, this forms a partition of $\N$ to which we can apply the base case of this proof.
This means that there is some $c$ among $1, \ldots, k$, there is an infinite set $I = \set {i \in \N : k_i = c}$.
Define $Y = \set {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^{\paren n}$ is in the same component $S_c$ of $P$.
Let $\set {y_1, \ldots, y_n} \in Y^{\paren 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^{\paren {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 $\set {y_2, \ldots, y_n} \in S_{a_i , c}$, we have:
:$\set {y_1, y_2, \ldots, y_n} = \set {a_i, y_2, \ldots, y_n} \in S_c$
== Also known as ==
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.
== Also defined as ==
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.
Category:Ramsey Theory