The proof of General-Finitary Ramsey Theorem as given in Graham et al. sirs’ book is great, but those technical subtleties really kind of clouds the beauty of the Induced-Colouring Method (ICM). I think in the proof of Infinitary Ramsey Theorem, the beauty of ICM is revealed in all its glory. So, the use of compactness principle to conclude the finite version as a corollary of the infinitary version is really sweet. So, in this first blog-post of mine, let’s try to prove the countable (and arbitrary) version of the compactness principle and see how it can be used to transfer the infinitary version to finitary version.

Theorem (Compactness Principle). Let $H=(V,E)$ be a hypergraph where all $X\in E$ are finite, then $\chi(H)>r$ if and only if $\exists W\in [V]^{<\omega}$ such that $\chi(H_W)>r$.

The above is mostly state in the contraposition: If for all finite $W\subseteq V$, $\chi(H_W)\leq r$ (i.e. all finite subhypergraphs of $H$ are $r$-colourable) then $\chi(H)\leq r$ (i.e. the hypergraph $H$ is $r$-colourable).

Let us see an alternative version (an enumerable version) of the principle form which the application is easy.

Theorem. Let $k\in\mathbb{N}$ and let $\mathcal{F}$ be a family of finite subsets of $\mathbb{N}$. If for any $r$-colouring of $[\mathbb{N}]^k$ there exists a member $F$ of $\mathcal{F}$ such that $[F]^k$ is monochromatic (we call $F$ homogeneous), then there exists a least positive integer $n_0(\mathcal{F},r)$ such that for $n\geq n_0(\mathcal{F},r)$, any $r$-colouring of $[n]^k$ contains a member of $\mathcal{F}$ homogeneous under $\chi$.

Let us see how the first implies the second. Indeed, consider the hypergraph $H=([\mathbb{N}]^k,\mathcal{F})$. As per the condition, for any $r$-colouring of vertices of $H$, there exists a monochromatic hyperedge, so $\chi(H)>r$. So we get that $\exists W\in[\mathbb{N}]^{<\omega}$ such that $\chi(H_W)>r$. Now consider the set of elements of $W$, it will contain a largest element, let it be $n=n_0(\mathcal{F},r)$, then for any $r$-colouring of $H$ restricted to vertices $[n]^k$, there exists a monochromatic hyperedge, i.e. a homogeneous member of $\mathcal{F}$.

Before seeing how the infinite version of Ramsey Theorem imply its finite version, let us first see two proofs of the countable version, and at the end we will see a proof of the arbitrary version, the one involving Zorn’s Lemma ($\textsf{ZL}$).

Proof 1 (Countable). ($\Leftarrow$) is trivial, so we do the other direction. ($\Rightarrow$) The case $|V|<\infty$ is tautological, as taking $W=V$ suffices. So let $V\sim \mathbb{N}$, for simplicity let $V=\mathbb{N}$. FTSOC suppose all finite subhypergraphs of $H$ are monochrome-avoiding, i.e. $\chi(H_W)\leq r$ for all finite $W\subseteq V$. Now we will form an infinite, finitely branching rooted tree and use König’s lemma. We grow a tree $T$ as follows: Let $\varnothing$ be the root, there is an edge between the root and all monochrome-avoiding $r$-colourings $[1]\to[r]$. For $n\in\mathbb{N}$, there is an edge between a monochrome-avoiding $r$-colouring $c_n:[n]\to[r]$ and a monochrome-avoiding $r$-colouring $c_{n+1}:[n+1]\to[r]$ if $c_{n+1}|_{[n]}=c_n$. Now it can easily be seen that $T$ is an infinite, finitely branching rooted tree. By König’s Lemma it follows that $T$ has an infinite branch, let it be $(c^{\circ}_1,c^{\circ}_2,\dots)$, this induces an $r$-colouring on $\mathbb{N}$ as $c^*:\mathbb{N}\to[r]$ defined by $c^*|_{[n]}=c^{\circ}_n$ for $n\in\mathbb{N}$. But for this colouring $H$ is monochrome-avoiding, i.e. it does not have any monochromatic hyperedges, indeed suppose it did have a monochromatic hyperedge, as the hyperedges are finite we may select the largest integer $t$ such that $t$ is in the monochromatic hyperedge, but then $\chi(c^{\circ}_t)>r$, which would be a contradiction. Thus we get that $H$ is monochrome-avoiding for the colouring, i.e. $\chi(H)\leq r$, contradiction. $\square$

Proof 2 (Countable). Now a proof of essentially the same idea, only that it neatly avoids weak $\textsf{AC}$. Again let $V=\mathbb{N}$. FTSOC assume $\chi(H_W)\leq r$ for all $W\in[\mathbb{N}]^{<\omega}$. Then for all $n\in\mathbb{N}$, there exists a colouring $\chi_n:[n]\to[r]$ so that no $W\in E$ and $W\subseteq [n]$ is monochromatic. We then define a function $\chi^*:\mathbb{N}\to[r]$ by induction (a different way of defining this function which will avoid weak $\textsf{AC}$). We have that among $\{\chi_1(1),\chi_2(1),\dots\}$, by IPHP, there exists a colour $c_1\in[r]$ such that it occurs infinitely many times in the set, we set $\chi^*(1):=c_1$, and $S_1$ as all colourings $\chi_j$ with $\chi_j(1)=c_1$. Now in the set of colours $\{\chi_j(2):\,\chi_j\in S_1\}$, by IPHP, there exists a colour $c_2\in[r]$ which occurs infinitely many times, let $\chi^*(2):=c_2$ and $S_2$ be the set of colours $\chi_j\in S_1$ with $\chi_j(2)=c_2$. Continuing this way, suppose we have $S_{i-1}$, in the set of colours $\{\chi_j(i):\,\chi_j\in S_{j-1}\}$, by IPHP, there exists a colour $c_i\in[r]$ which occurs infinitely many times, let $\chi^*(i):=c_i$ and $S_i$ be the set of colours $\chi_j\in S_{i-1}$ with $\chi_j^*(i)=c_i$. Notice how the idea of iteratively building $\chi^*$ is same as the earlier proof, only that here we use a sequence of monochrome-avoiding colourings $\chi_n$ instead of considering all monochrome-avoiding colourings for each $[n]$, $n\in\mathbb{N}$. Now it’s clear that $\chi^*$ is the desired $r$-colouring of $H$ for which $\chi(H)\leq r$. Indeed, let $S=\{v_1,\dots,v_m\}_<\in E$, considering $S_{v_m}$, we have that for $i\in[v_m],$ $\chi^*(i)=\chi_j(i)$ for all $\chi_j\in S_{v_m}$, as $S$ is not monochromatic under $\chi_j$, so is it not monochromatic under $\chi^*$. As $S\in E$ is any arbitrary finite edge, we get that $\chi^*$ is a monochrome-avoiding $r$-colouring of $H$, i.e. $\chi(H)\leq r$, contradiction. $\square$

Now let us see how infinitary Ramsey Theorem implies the finitary version. But before that, let us state the two theorems (or principles).

Theorem (Infinitary Ramsey Theorem). For $k,r\in\mathbb{N}$, any $S\in[\mathbb{N}]^{\omega}$, and any $r$-colouring $\chi:[S]^{k}\to[r]$, there exists $H\in[S]^{\omega}$ such that $H$ is homogeneous under $\chi$.

Theorem (Finitary Ramsey Theorem). For $r,k,m\in\mathbb{N}$, there exists $n\in\mathbb{N}$ such that for any $r$-colouring $\chi:[n]^k\to[r]$, there exists $H\in[n]^m$ homogeneous under $\chi$.

We use the second version of compactness principle on the family $\mathcal{F}:=\{[S]^k:\,S\in[\mathbb{N}]^m\}$. It can easily be then seen that the infinitary version then implies the finitary version.

Now we give a proof of the arbitrary case, assume $V$ is not countable. Let us state $\textsf{ZF}$ for the sake of completeness.

Zorn’s Lemma ($\textsf{ZL}$). If $P$ is a non-empty poset and every chain of it has an upperbound, then $P$ contains a maximal element (an element $x\in P$ such that $x\leq y \Rightarrow x=y$).

$\textsf{ZL}$ is equivalent to $\textsf{AC}$, but we don’t show it here and just use it.

Proof (Arbitrary). We prove the contraposition, i.e. for all $W\in[V]^{<\omega}$, $\chi(H_W)\leq r\implies \chi(H)\leq r$. Suppose $H$ having the property that all its finite subhypergraphs are $r$-colourable is denoted by $P(H)$. Consider the set of extensions of $H$ all having the said property, i.e. $S:=\Big\{(V,F):\, F\subseteq E,\, P\big((V,F)\big)\Big\}$. Consider the poset structure on $S$ by hyperedge-inclusion, $\mathfrak{S}=(S,\subseteq_{\text{hyperedge}})$. For any chain $\{A_i\}_{i\in I}$ in $\mathfrak{S}$, we have that $\bigg(V,\bigcup_{i\in I}E(A_i)\bigg)\in\mathfrak{S}$, indeed suppose it was not, then some hyperedge of it is monochromatic, now the hyperedges are finite so taking large enough $A_i$ gives us $\chi(A_i)>r$, contradiction. So we get that every chain in $\mathfrak{S}$ has an upperbound. By $\textsf{ZL}$ it follows that $\mathfrak{S}$ contains a maximal element, let it be $M$, and it satisfies $P(M)$. So $M$ being maximal implies that any addition of hyperedge would hinder property $P$. Now we consider the non-adjacency relation, denoted by $\neg\textsf{adj}$, between the vertices as: distinct $a,b\in V$, then $a\,\neg\textsf{adj}\,b\implies$ $a,b$ don’t lie in any hyperedge in $F$, we consider $a\,\neg\textsf{adj}\, a$ (it will be clear soon why so). We will show that the non-adjacency relation is an equivalence relation. Indeed, reflexivity and symmetricity are trivial, so we show transitivity, $a\,\neg\textsf{adj}\, b$ and $b\,\neg\textsf{adj}\, c$ implies $a\,\neg\textsf{adj}\, c$. Indeed, assume $a\,\neg\textsf{adj}\, b$ and $b\,\neg\textsf{adj}\, c$. Now consider all subhypergraphs of $M$ containing $a,b$, we get that there must exist a subhypergraph $M_{ab}$ which has in all its $r$-colouring $a$ and $b$ of same colour, as otherwise if there are no such subhypergraphs, then there must be a colouring with $a$ and $b$ different, we may then add an hyperedge containing $a,b$, contradicting the maximality of $M$. Similarly we get the existence of a subhypergraph $M_{bc}$ which has in all its $r$-colouring $b$ and $c$ of same colour. Now consider the subhypergraph $M_{ab}\cup M_{bc}$, it is finite and so is $r$-colourable, and it contains subhypergraphs as $M_{ab}$ and $M_{bc}$, so by construction we get that $(a,b)$ and $(b,c)$ receives same colour for all $r$-colouring of it, and hence $a\,\neg\textsf{adj}\, c$ (this same colouring idea is why we defined $a\,\neg\textsf{adj}\, a$). As non-adjacency is an equivalence relation in $M$, we get that adjacency is an equivalent relation in the hyperedge-complement of $M$, say $M^{\circ}$. So we get that $M^{\circ}$ comprises of disjoint complete subhypergraphs $K^h_j$‘s. If there are more than $r$ many $K^h_i$‘s, then we may select $r+1$ distinct vertices from $V(K^h_i),$they being non-adjacent in $M^{\circ}$ implies they being adjacent in $M$, forcing $M$ to be not $r$-colourable, contradiction (we have $r$ many colours but $r+1$ many adjacent vertices). Thus we have at most $r$ many $K^h_i$‘s, we may colour each of them with different colours, then it is a proper $r$-colouring of $M$ as they were all adjacent in $M^{\circ}$ and hence non-adjacent in $M$, thus we get $\chi(M)\leq r$. As $H$ is but a subhypergraph of $M$, so taking restriction gives us $\chi(H)\leq r$. $\square$