Logic – Finite Ramsey Theorem via Propositional Compactness

compactnesslogicpropositional-calculusramsey-theory

Consider the following statements:

Finite Ramsey Theorem ($\mathrm{FRT}$): For any $k,r,p\in\mathbb{N}^{+}$, there exists $N\in\mathbb{N}$ such that every function $c:[N]^{p}\rightarrow [r]$ has a homogeneous subset of size $k$.

By $[r]$ we mean the set $\{1,\ldots r\}$, and by $[A]^{p}$ we mean the set of $p$-element subsets of $A$. If $A=[N]$ we simply denote $[[N]]^{p}$ by $[N]^{p}$. A subset $H\subseteq A$ is homogeneous for $c$ if $c|_{[H]^{p}}$ is constant. Finally, the function $c:[A]^{p}\rightarrow [r]$ is called an $r$-coloring of $[A]^{p}$

Infinite Ramsey Theorem ($\mathrm{IRT}$): For any $r,p\in\mathbb{N}^{+}$, any $r$-coloring $c$ of $[\mathbb{N}]^{p}$ has an infinite homogeneous subset.

I am trying to prove that $\mathrm{IRT}\Rightarrow\mathrm{FRT}$ via the Compactness Theorem for propositional logic.

The idea is to conclude that $\mathrm{IRT}$ fails if $\mathrm{FRT}$ fails for some $k$. Indeed, assume $\neg\mathrm{FRT}$. That is, for any arbitrarily large $N\in\mathbb{N}$ there is an $r$-coloring $c_{N}$ of $[N]^{p}$ having no homogeneous subset of size $k$. Define a propositional language $L$ whose atoms are $C^{i}_{a_{1}\ldots a_{p}}$, for all $a_{1},\ldots,a_{p}\in\mathbb{N}$ and $1\leq i\leq r$ (intuitively $C^{i}_{a_{1}\ldots a_{p}}$ means $\{a_{1},\ldots,a_{p}\}$ will be $i$-colored when true). Then we define a set $S_{k}$ to be the set of $L$-sentences:

  1. $C^{i}_{a_{1}\ldots a_{p}}\Leftrightarrow C^{i}_{a_{f(1)}\ldots a_{f(p)}}$ for all $a_{1},\ldots,a_{p}\in\mathbb{N}$, any permutation $f$ of $\{1,\ldots,p\}$, and $1\leq i\leq r$.
  2. $\displaystyle\bigvee_{1\leq a_{1}<\cdots<a_{p}\leq k}\neg C^{i}_{a_{1}\ldots a_{p}}$ for all $a_{1},\ldots,a_{p}\in\mathbb{N}$, and $1\leq i\leq r$ (every $k$-element subset of $\mathbb{N}$ has at least one $p$-element subset which will not $i$-colored).
  3. $\displaystyle\bigvee_{1\leq a_{1}<\cdots<a_{p}\leq k}C^{i}_{a_{1}\ldots a_{p}}$ for all $a_{1},\ldots,a_{p}\in\mathbb{N}$, and $1\leq i\leq r$ (every $k$-element subset of $\mathbb{N}$ has at least one $p$-element subset which will be $i$-colored).

With 3 and 4 together I am trying to state that there will not be a homogeneous $k$-element subset for the $r$-coloring of $[\mathbb{N}]^{p}$.

Did I define the language $L$ and the set $S_{k}$ appropriately?

If $\mathrm{FRT}$ fails for $k$, then $S_{k}$ is satisfiable. Indeed, suppose that $\Delta$ is a finite subset of $S_{k}$. Then the elements $a_{i}$ mentioned in $\Delta$ form a finite set. As a consequence, there is a largest $m\in\mathbb{N}$ for which $a_{m}$ occurs in one of the finitely many atoms of $\Delta$. Since the $\mathrm{FRT}$ fails for $k$, there is $N\geq m+1$ such that $c_{N}:[N]^{p}\rightarrow [r]$ has no homogeneous subset of size $k$. In fact, WLOG we can say $[N]=\{0,\ldots,m\}\cup\{m+1,m+2,\ldots\}$. Therefore, we can define a truth assignement
$$\mu(C^{i}a_{1}\ldots a_{p})=\mathsf{T}\text{, for $a_{1},\ldots,a_{p}\leq m$ iff $c_{N}(\{a_{1},\ldots a_{p}\}) = i$}.$$

I then try to show that $\mu$ must satisfy $\Delta$ by showing it satisfies formulas 1-3, but I run into trouble. What is wrong with my definition of $\mu$?

Once I can show that $\Delta$ is satisfiable, the compactness theorem implies that $S_{k}$ is satisfiable. But this means there is an $r$-coloring $c$ of $[\mathbb{N}]^{p}$ having no homogeneous subset of size $k$. Since $\mathrm{IRT}$ states that every $r$-coloring of $[\mathbb{N}]^{p}$ must have an infinite homogeneous subset, it must have a finite homogeneous subset of every size. Therefore, $\neg\mathrm{FRT}\Rightarrow\neg\mathrm{IRT}$, as desired.

This question is related.

Best Answer

I find that moving from IRT to FRT is easier and more teaching if you use the bellow method.

The reason I think it is more teaching is because it gives you results both using compactness and using infinitary combinatorics, and direct usage of compactness are usually very similar, tasting infinitary combinatorics early on is much more productive:

Lemma 1: Assume compactness for propositional logic, then every set is linearly orderable

Proof:

Let $X$ be any set and define $L_X$ be the language $\{c_{i,j} \mid i,j\in X\}$ together with the axioms:
1) $¬c_{i,i}$ for each $i\in X$
2) $c_{i,j}⇒¬c_{j,i}$ for each $i,j\in X$
3) $c_{i,j}∧c_{j,k}⇒c_{i,k}$ for each $i,j,k\in X$
4) $c_{i,j}∨c_{j,i}$ for each $i≠j\in X$
Intuitively $c_{i,j}$ represent $i<j$. Easy compactness argument shows that this is finitely satisfiable, hence satisfiable, which gives a linear order

This result is a textbook result of compactness and is very useful, for example:

Lemma 2: if every set is linearly order then whenever $X$ is a set and $R$ is a relation on $X$ such that:

  1. $∀x∈X∃y∈X (Rxy)$ (every element is in relation to something)
  2. $\{y\in X\mid Rxy\}$ is finite for every $x\in X$ (the set of elements $x$ is in relation with is finite)

Then there exists a sequence $(a_i\mid i\in ℕ)$ of elements in $X$ such that $Ra_ia_{i+1}$ for each $i\inℕ$

Proof:

Let $<$ be a linear order on $X$, and let $a_0$ be any element of $X$, then define recursively $a_{i+1}$ be the minimal element of $\{y\in X\mid Ra_iy\}$ [this set has a unique minimal element because it is a finite linear order]

Lemma 2 can be viewed as a weakening version of Dependent Choice.

Using only lemma 2 (which is much much weaker than compactness) we can now prove IRT⇒FRT:

Assume FRT fails, so there exists $n,m,p\in ℕ$ such that for each (large enough) $k∈ℕ$ there exists a colouring of $[k]^n$ to $m$ colours without homogeneous subset of size $p$.

Let $C_k$ be the set of such colouring, note that for each (large enough) $k$, $C_k$ is finite non-empty set.

Let $C_k^1$ be the set of colouring in $C_k$ that can be extend to a colouring in $C_{k+1}$, similarly $C_k^2$ to be the set of colouring in $C_{k}$ that can be extend to a colouring in $C_{k+2}$ and so on.

Note that if $c\in C_{k+i}$ for some $i∈ℕ$, then $c$ restricted to the subsets of $k+j$ is in $C_{k+j}$ for all $j\le i$, hence $C_k^1 \supseteq C_k^2\supseteq C_k^3\supseteq \cdots$ is a decreasing sequence of non-empty finite sets, in particular $C_k^ω=\bigcap_{i\in ℕ}C_k^i$ is a non-empty subset of $C_k$ such that if $c\in C_k^ω$, and $q>k$ is any number, then $c$ can be extend to colouring on $[q]^n$ without homogeneous subset of size $p$.

Take some (large enough) $k$ and define the following relation on $\bigcup_{i≥k}C_i^ω$: $Rc_0c_1$ if $c_0$ is a colouring on $[q]^n$, $c_1$ is a colouring on $[q+1]^n$ and $c_0$ can be extended to $c_1$.

This relation clearly satisfy the requirement for Lemma 2, so let $(g_i\mid i∈ℕ)$ be a sequence of colouring such that $Rg_ig_{i+1}$ for all $i∈ℕ$. Define $g=\bigcup_{i∈ℕ}g_i$, it is not hard to see that this is a colouring on $[ℕ]^n$, if $A⊆ℕ$ is an homogeneous set of size $p$ then take $b=1+\max A$ and you get that $A$ is an homogeneous subsets of size $p$ for the colouring $g_{b}$, which is a contradiction.

Related Question