Finite Ramsey theorem via propositional compactness + infinite Ramsey theorem

Question

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.

Answer 1

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.

Answer 2

I think the following corrects and makes more precise the argument illustrated in the question.

The idea is to assume $\neg\mathrm{FRT}$ for some $k_{0}\in\mathbb{N}^{+}$ and then use propositional compactness to show $\neg\mathrm{IRT}$ for $k_{0}$. How do we do this? Well, the statement of $\mathrm{IRT}$ clearly implies that for any $r,p\in\mathbb{N}^{+}$, any $r$-coloring of $[\mathbb{N}]^{p}$ has a homogeneous subset of size $k$ for all $k\in\mathbb{N}^{+}$. In particular, for $k=k_{0}$. Therefore, we want to find a specific $r$-coloring $c$ of $\mathbb{N}$ having no homogeneous subset of size $k_{0}$. One way to do so this is by defining a propositional language $L$ and a set $S_{k_{0}}$ of $L$-formulas encoding $\neg\mathrm{IRT}$ for $k_{0}$ in such a way that satisfiability of $S_{k_{0}}$ will be equivalent to $\neg\mathrm{IRT}$ for $k_{0}$ (i.e. $c$ will have no homogeneous subset of size $k_{0}$) Then using $\neg\mathrm{FRT}$ for $k_{0}$ to show that $S_{k_{0}}$ is finitely satisfiable and propositional compactness will finish the job.

The language $L$ consists of propositional atoms $C_{a_{1}\ldots a_{p}}^{i}$, for all distinct $a_{1},\ldots,a_{p}\in\mathbb{N}$, and $1\leq i\leq r$. Intuitively, $C_{a_{1}\ldots a_{p}}^{i}$ means $c(\{a_{1}\ldots a_{p}\}) = i$ when true.

The set $S_{k_{0}}$ consists of the following $L$-formulas:

1. $\displaystyle\bigvee_{1\leq i\leq r}C_{a_{1}\ldots a_{p}}^{i}$ for all distinct $a_{1},\ldots, a_{p}\in\mathbb{N}$ (each $p$-element subset of $\mathbb{N}$ is assigned at least one color).
2. $\neg(C_{a_{1}\ldots a_{p}}^{i}\wedge C_{a_{1}\ldots a_{p}}^{j})$ for all distinct $a_{1},\ldots, a_{p}\in\mathbb{N}$ and $1\leq i<j\leq r$. (each $p$-element subset of $\mathbb{N}$ is assigned at most one color).
3. $C^{i}_{a_{1}\ldots a_{p}}\Leftrightarrow C^{i}_{a_{f(1)}\ldots a_{f(p)}}$ for all distinct $a_{1},\ldots,a_{p}\in\mathbb{N}$, any permutation $f$ of $\{1,\ldots,p\}$, and $1\leq i\leq r$.
4. $\displaystyle\bigvee_{1\leq j_{1}<\cdots<j_{p}\leq k_{0}}\neg C^{i}_{a_{j_{1}}\ldots a_{j_{p}}}$ for all distinct $j_{1},\ldots,j_{p}\in\mathbb{N}$, and $1\leq i\leq r$ (every $k_{0}$-element subset of $\mathbb{N}$ has at least one $p$-element subset which is not colored by $i$).

Note that 4 expresses that the $r$-coloring $c$ does not have a homogeneous subset of size $k_{0}$.

All that it is left for us to do is showing that $S_{k_{0}}$ is finitely satisfiable. Indeed, let $\Delta\subset S_{k_{0}}$ be a finite subset. Then, there are finitely many $a_{j}\in\mathbb{N}$ mentioned in the sentences of $\Delta$, so there is a largest one, say $a_{m}$, for some $m\in\mathbb{N}$. Let $N>a_{m}$. Since we assume $\neg\mathrm{FRT}$ for $k_{0}$, there is an $r$-coloring $c_{N}:[N]^{p}\rightarrow [r]$ with no homogeneous subset of size $k_{0}$. Define an $L$-assignment $\mu$ by

$$\mu(C_{a_{1}\ldots a_{p}}^{i})=\mathsf{T}\,\text{ if and only if}$$

1. $a_{j}\leq a_{m}$ for all $1\leq i\leq p$, and
2. $c_{N}(\{a_{1},\ldots a_{p}\}) = i$.

Note that since $N>a_{m}$ then the set $[N]$ contains all the $a_{j}$ occurring in $\Delta$. Therefore 2 above makes sense when 1 is true.

The $L$-assignment $\mu$ clearly satisfies 1-5 of $\Delta$, and by propositional compactness, $S_{k_{0}}$ is itself satisfiable, as desired.

I think this argument does not have any major flaws, but any suggestions will be welcome.

---

After I had looked at it some more, I realized that it is possible to simplify matters if we consider the propositional language $L$ to consist of atoms $C^{i}_{a}$, for all $a\in[\mathbb{N}]^{p}$, and $1\leq i\leq r$.

In this language, the set $S_{k}$ is considerably simplified (e.g. there is no need for 3 in the definition of $S_{k_{0}}$), consisting of $L$-formulas:

1. $\displaystyle\bigvee_{1\leq i\leq r}C^{i}_{a}$ for all $a\in[\mathbb{N}]^{p}$ (each $p$-element subet of $\mathbb{N}$ is assigned at least one color).
2. $\neg(C^{i}_{a}\wedge C^{j}_{a})$ for all $a\in[\mathbb{N}]^{p}$ and $1\leq i<j\leq r$. (each $p$-element subset of $\mathbb{N}$ is assigned at most one color)
3. $\displaystyle\bigvee_{a\in[A]^{p}}\neg C^{i}_{a}$ for all $A\in[\mathbb{N}]^{k_{0}}$, and $1\leq i\leq r$ (every $k_{0}$-element subset of $\mathbb{N}$ has at least one $p$-element subset which is not colored by $i$).

Again, 3 expresses that the $r$-coloring $c$ does not have a homogeneous subset of size $k_{0}$.

The idea for the rest of the proof is the same with the appropriate straightforward changes due to how $L$ and $S_{k_{0}}$ are now defined.