Infinite Ramsey's Theorem

From ProofWiki
Jump to navigation Jump to search



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}$ if and only if:

$\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$

$\blacksquare$


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.


Source of Name

This entry was named for Frank Plumpton Ramsey.