Ultrafilter proof of the infinite Ramsey Theorem

Question

The Infinite Ramsey Theorem ($\mathsf{RT}$) is the statement

For any $r,p\in\mathbb{N}^{+}$ and any infinite set $A$, any $r$-coloring $c$ of $[A]^{p}$ has an infinite homogeneous subset.

Where $[r] = \{1,\ldots r\}$, and $[A]^{p}$ is the set of $p$-element subsets of $A$. A function $c:[A]^{p}\rightarrow [r]$ is called an $r$-coloring of $[A]^{p}$, and a subset $H\subseteq A$ is homogeneous for $c$ if $c$ is constant on ${[H]^{p}}$.

I am trying to prove $\mathsf{RT}$ by induction on $p$, but I am stuck in the general induction step. Here is what I have so far:

The case $p=1$, $r\in\mathbb{N}^{+}$ is simply the infinite pigeonhole principle and it is clear.

The case $p=2$, $r\in\mathbb{N}^{+}$ (which I thought solving would help me understand how to use an ultrafilter in the general induction step) goes as follows: Apply the Ultrafilter Theorem to extend the non-principal filter defined by the collection of all cofinite subsets of $A$ to a non-principal ultrafilter $U$ on $A$.

For each $a\in A$ and each color $i\in[r]$, let $A_{i}^{a} = \{b\in A-\{a\}:c(\{a,b\})=i\}$. Then, for each $a\in A$ we have a partition $\{A_{1}^{a},\ldots,A_{r}^{a},\{a\}\}$ of $A$, and since $U$ is a non-principal ultrafilter we must have exactly one of the $A_{i}^{a}\in U$. For each $a\in A$, let $i_{a}$ denote the unique color such that $A_{i_{a}}^{a}\in U$. The function $f:a\mapsto i_{a}$ is an $r$-coloring of $[A]^{1}$, and therefore there is an infinite homogeneous subset $X\in U$ for $f$. Let $k=f(X)$ (another way of seeing this is that sets $\{a\in A:i_{a}=1\},\ldots,\{a\in A:i_{a}=r\}$ form a partition of $A$. Therefore, exactly one of them is in $U$ since $U$ is an ultrafilter. Let $k$ denote the unique color such that $X = \{a\in A: i_{a} = k\}\in U$).

This set $X$ may already be homogeneous for $c$? In any case, since it is infinite we can pick $a_{0}\in X$. Let $X_{1}=X\cap A_{k}^{a_{0}}$. Since $U$ is a filter, $X_{1}\in U$ and is infinite, and there is $a_{1}\in X_{1}$. Note that $a_{0}$ and $a_{1}$ are distinct. Continue this process to obtain $a_{i}\in X_{i}=X\cap\bigcap_{j<i}A_{k}^{a_{i}}$, where $X_{i}\in U$ and is infinite.

We claim that the set $H=\{a_{i}:i\geq 0\}$ is homogeneous for $c$. Indeed, for all $i<j$ it is clear that $a_{j}\in A_{k}^{a_{i}}$. Therefore, $c(\{a_{i},a_{j}\})=k$, as desired.

Question 1: Have I made any mistakes so far?

Now, let $p\geq 2$ and the result to hold for all $r\in\mathbb{N}^{+}$ and for $p$. Let $c:[A]^{p+1}\to[r]$ be an $r$-coloring of $[A]^{p+1}$. Let $U$ be the same non-principal ultrafilter on $A$.

Question 2: How do I proceed?

---

Update

Here is an idea: For each $a\in A$ and each color $i\in[r]$, let $A_{i}^{a} = \{B\in [A-\{a\}]^{p}:c(B\cup\{a\})=i\}$. Then, for each $a\in A$ the sets $\{A_{1}^{a},\ldots,A_{r}^{a}\}$ partition $[A-\{a\}]^{p}$, which defines an $r$-coloring $c_{a}$ of $[A-\{a\}]^{p}$. Therefore, by the induction hypothesis, for each $a\in A$ there is a homogeneous subset $H_{a}\subseteq A-\{a\}$ for $c_{a}$. Since $U$ is a non-principal ultrafilter, for each $a\in A$ we have $H_{a}\in U$ is infinite. For each $a\in A$, let $k_{a} = c_{a}([H_{a}]^{p})$. The set $\{k_{a}:a\in A\}$ is indexed by an infinite set $A$, but is is a subset of $[r]$. Therefore, by the infinite pigeonhole principle there is $k\in[r]$ such that $k=k_{a}$ for infinitely many $a\in A$. Let $$H = \bigcup_{k_{a}=k}H_{a},$$ which is clearly in $U$ and is therefore infinite. We claim that $H$ is homogeneous for $c$. Indeed, let $H'\in[H]^{p+1}$. Pick any $a\in H'$. Then the set $H'-\{a\}\in [A-\{a\}]^{p}$, and $c_{a}(H'-\{a\}) = k$ hmm.. no there is something wrong here. This is not true necessarily...

A good hint would do :)

Answer 1

After staring at the case $p=2$ long enough I think I have a solution which generalizes this case, and it does not need induction after all. Here it goes:

Let $p,r\in\mathbb{N}^{+}$, $p>1$, and let $c$ be an $r$-coloring of $[A]^{p}$. Let $U$ be the same non-principal ultrafilter on $A$ we used in the case $p=2$.

The idea is to use $U$ and $c$ in order to define for each $1\leq m\leq p$ an $r$-coloring $c_{m}$ of $[A]^{m}$. We do this recursively:

Let $c_{p}=c$. Next, for each $B\in[A]^{p-1}$ and each $i\in[r]$ define a set $A^{p-1}_{i}(B)=\{a\in A-B:c_{p}(B\cup\{a\}) = i\}$. Then, for each $B\in[A]^{p-1}$ we have a partition $\{A^{p-1}_{1}(B),\ldots,A^{p-1}_{r}(B), B\}$ of $A$. Since $U$ is a non-principal ultrafilter there must be exactly one $i_{B}\in[r]$ such that $A^{p-1}_{i_{B}}(B)\in U$, and we can define for each $B\in[A]^{p-1}$ $c_{p-1}(B)=i_{B}$.

In general, once the $r$-coloring $c_{m+1}$ of $[A]^{m+1}$ has been defined, we define for each $B\in[A]^{m}$ and each $i\in[r]$ the set $A_{i}^{m}(B)=\{a\in A-B:c_{m+1}(B\cup\{a\})=i\}$. The exact same argument using the ultrafilter $U$ yields for each $B\in[A]^{m}$ a unique $i_{B}\in[r]$ we use to define an $r$-coloring $c_{m}$ of $[A]^{m}$.

We continue this process until we have eventually defined an $r$-coloring $c_{1}$ of $A$, i.e. a partition $\{a\in A:c_{1}(1)=1\},\ldots,\{a\in A:c_{1}(a)=r\}$ of $A$. Our good friend the ultrafilter tells us that there is exactly one $k\in[r]$ such that the set $X=\{a\in A:c_{1}(a)=k\}\in U$. Note that $X$ is thus infinite.

Ok, now what? Well, we will use $X$ and the load of dribble above to construct a set $H$ with the property that

for each $1\leq m\leq p$ and every $B\in[H]^{m}$, we have $c_{m}(B)=k$.

That will certainly show that $H$ is homogeneous for $c$!

We construct $H$ recursively. Since $X$ is infinite, pick $a_{0}\in X$ and let $H_{0}=\{a_{0}\}$. Next, let $$X_{1} = X\cap A_{k}^{1}(\{a_{0}\})$$ Since $U$ is a non-principal ultrafilter and each set in the intersection is in $U$ then $X_{1}$ is also in $U$ and is thus infinite (note $a_{0}\not\in X_{1}$). Pick $a_{1}\in X_{1}$ and let $H_{1}=\{a_{0},a_{1}\}$.

We continue this process, and once $H_{n}=\{a_{0},\ldots a_{n}\}$ has been defined, the set $X_{n+1}$ will have the form $$X_{n+1} = X\cap\left(\bigcap_{b\in H_{n}}A_{k}^{1}(\{b\})\right)\cap\left(\bigcap_{B\in[H_{n}]^{2}}A_{k}^{2}(B)\right)\cap\cdots\cap\left(\bigcap_{B\in[H_{n}]^{p-1}}A_{k}^{p-1}(B)\right)$$

(Of course, if $n$ is less than $p$, the expression above is truncated, and after $n$ goes beyond $p$ we do not add additional big-parenthesis terms)

In any case, this intersection is finite and each term is in $U$, guaranteeing that $X_{n+1}\in U$ and is thus infinite. Pick $a_{n+1}\in X_{n+1}$.

Continue this process ad infinitum to add a distinct element at each step to our growing set of $a_{n}$'s and simply define $H=\cup_{n\ge 0}H_{n}=\{a_{n}:n\geq 0\}$. It is clear from the construction that $H$ has the desired property highlighted above, and is thus infinite homogeneous for $c$. And done! What a little industrious ultrafilter $U$ has been :)

A final though (see the comments to the question): Constructing $H$ assumes the infinite set $X$ has a countable subset, and the statement $(\mathsf{C})$ -Every infinite set has a countable subset- is a (weak) form of the axiom of choice. Therefore, if I have not made any mistakes, we have that $\mathsf{UT}+\mathsf{C}\Rightarrow\mathsf{RT}$ over $\mathsf{ZF}$.