Refining Ramsey’s theorem with ultrafilters
Published:
Ramsey’s theorem (in its infinite version) states that given any $k$-coloring $f:[\omega]^n \to k$ of a countably infinite set say, $\omega$, there is an infinite subset $A \subseteq \omega$ such that $f([A]^n)$ is constant, in which case we say that $f$ is homogeneous on $A$. In other words, for any coloring of the edges of a graph with countable vertices, there is some infinite subset of vertices whose edges are all of the same color.
Ramsey’s theorem influenced much of modern mathematics, in set theory, for instance, there are various areas of research which draw inspiration from Ramsey-type results (see for instance Halbeisen’s book [2]), the one which I’d like to discuss today tackles how one might reduce the class of sets which holds an infinite homogeneous subset for any choice of coloring of $[\omega]^n$ from ${\{X \subseteq \omega: X \text{ is infinte}\}}$ to something “smaller”. For our purposes we shall look for a non-principal ultrafilter on $\omega$ which satisfies this condition. Formally speaking:
Definition: Let $\mathcal{U}$ be a non-principal ultrafilter on $\omega$. We say that $\mathcal{U}$ is a Ramsey ultrafilter if for evey $n,k \in \mathbb{Z}$ and any $k$-coloring $f:[\omega]^n \to k$ there is some $A \in \mathcal{U}$ such that $f$ is homogeneous on $A$.
The existence of a Ramsey ultrafilter is independent of ZFC, but we can prove it under ZFC+CH or some weaker conditions, such as $\mathfrak{p}=\mathfrak{c}$ or MA(countable) (c.f. [2] for all these assertions). I’m interested in presenting a direct proof of the existence of a Ramsey ultrafilter from Martin’s Axiom, following the arguments of Booth in his 1970 paper [1].
Theorem (ZFC+MA): There exists a Ramsey ultrafilter. Moreover, the set of Ramsey ultrafilters is dense in $\mathcal{U}$.
Proof: Let $\beta \mathbb{N}$ be the topological space of ultrafilters. We define $\mathbb{F}$ to be the set of filters on $\omega$ generated by less than continuum many subsets of $\omega$ and which contain no finite sets, with a partial order given by $G \le F \iff F \subseteq G$. For the moreover assertion, it is a simple matter of noticing that everything we do in the following would work if we would substitute $\omega$ for any infinite subset $A \subseteq \omega$, restrict colorings to $[A]^n$ and work only with filters containing $A$.
By Ramsey’s theorem, given any $n,k \in \mathbb{Z}$ and a $k$-coloring $f$, the set
\[D_f ={ \\{F \in \mathcal{F}: \exists A \in [\omega]^\omega(F \text{ is homogeneous on $A$})\\} }\]is dense in $\mathbb{F}$ (since, given any filter $F \in \mathcal{F}$, there is $A \subseteq \omega$ on which $f$ is homogeneous,…). Likewise, the sets
\[E_A = {\\{F \in \mathcal{F}: A \in F \text{ or } \omega \setminus A \in F\\} }\]for every infinite $A \subseteq \omega$ are also dense (due to the fact that any filter on $\omega$ may be extended to an ultrafilter). As is natural in applications of MA, these sets codify respectively the property satisfied by the above definition and the defining property of ultrafilters, we wish then to find a filter which is generic to the set $\mathcal{D}$ of all these dense sets and taking the union of the elements of this filter construct a Ramsey ultrafilter.
| However, it is not so straight forward since there are continuum many colorings $f:[\omega]^n \to k$, for all choices of $n,k \in \mathbb{Z}$ (since $\bigcup_{k \in \omega} | k | ^{\aleph_0} = 2^{\aleph_0}$). So we won’t use MA as of yet, what we will do is construct our desidered $\mathcal{D}$-generic filter using transfinite induction: First consider and ordering of $\mathcal{D}$ |
Then, we will follow the cases bellow for $\alpha$ an ordinal in $2^{\aleph_0}$.
$\alpha=0$) Choose some $F_0’ \in D_0$ and $F_0 \in E_0$ such that $F_0 \le F_0’$.
$\alpha$ is a successor ordinal) Let $\alpha = \delta^+$ and choose $F_\alpha’ \in D_\alpha$ and $F_\alpha \in E_\alpha$ such that $F_\alpha \le F_\alpha’ \le F_\delta$.
$\alpha$ is a limit ordinal and $\alpha < 2^\aleph_0$) We have a decreasing chain ${ \{F_\delta : \delta \in \alpha\} }$. We will use MA to find a lower bound to this chain: First we define a partial order in which
$\alpha= 2^{\aleph_0}$) For this, we simply use what we just proved and the following Lemma of Booth to achieve this: Lemma (Booth): Let $(P, \le)$ be a partial order and $\kappa$ a regular cardinal. Then, if every decreasing chain of length less than $\kappa$ has a lower bound, and if $\mathcal{D}$ is a set of at most $\kappa$ dense sets, there is a $\mathcal{D}$-generic set for $P$.
(notice we can do this even if $\alpha = 2^{\aleph_0}$ since $2^{\aleph_0}$ is regular and $ .
References
[1] Booth, D., Ultrafilters on a countable set, Annals of Mathematical Logic, Vol. 2 (1), 1-24, 1970.
[2] Halbeisen, L. J., Combinatorial Set Theory With A Gentle Introduction to Forcing, Springer-Verlag, 2012.