Compactness principle via model theory.

307 Views Asked by At

A standard method of getting more concrete results from more abstract ones in Ramsey theory is the so called Compactness Principle. It is best illustrated by example.

Here is the standard version of a Ramsey-theoretic result:

Van der Waerden ("abstract"): Fix length $l$ and number of colours $r$. If $c: \mathbb{N} \to \{1,2,\dots,r\}$ is colouring of $\mathbb{N} $ with $r$ colours, then we can find a monochromatic arithmetic progression of length $l$; i.e. there exists $i \in \{1,2,\dots,r\}$, $a,d \in \mathbb{N}$ such that we have $c(a) = c(a+d) = \dots = c(a+(l-1)d)$.

We can make the statement more concrete by referring to finite (but sufficiently large) bits of $\mathbb{N}$:

Van der Waerden ("concrete"): Fix length $l$ and number of colours $r$. Then there exists $N$ (dependent on $l,r$) such that f $c: \{1,2,\dots,N \} \to \{1,2,\dots,r\}$ is colouring of $\{1,2,\dots,N \}$ with $r$ colours, then we can find a monochromatic arithmetic progression of length $l$.

It is obvious that the "concrete" version of the theorem implies the abstract. The reverse implication is also true, and here we see the compactness principle at work. For a proof by contradiction, suppose the "concrete" version fails, but "abstract" one works. So let $c_n$ stand for the colouring of $\{1,2,\dots,n\}$ free of arithmetic progression of length $r$. Passing to subsequence, we may assume that $c_n(1)$ is constant; denote it by $c(1)$. By subseqent restritions to subsequences, we may assume that $c_n(2) =: c(2)$ is constant, $c_n(3) =: c(3)$ is constant, and so on. We claim that thus constructed $c :\mathbb{N} \to \{1,2,\dots,r\}$ is a colouring of $\mathbb{N}$ without arithmetic progressions, contrary to the known theorem. Indeed, if we fix an arithmetic progression $a,a+d,\dots,a+(l-1)d$, then there is some $n$ such that $c = c_n$ restricted to this progression, so the progression can't be monochrone. This can be said in a simpler way using compactness of $\{1,2,\dots,r\}^{\mathbb{N}}$.

I have recently learnt some model theory, and it seems to me that the compactness principle can be easily derived from model theoretic considerations. Fix $l,r$. Let $\mathcal{T}$ be the theory of $r$-coloured arithmetic progressions without monochromatic arithmetic progressions of length $l$:

  • Language contains symbol $0$, the successor predicate $S(\cdot,\cdot)$ which is supposed to say that one argument is the successor of the other, and predicate $AP(\cdot,\cdot,\cdot)$ that takes $3$ arguments and is supposed to say that the three arguments form an arithmetic progression, and $r$ precidacates $C_i(\cdot)$ saying that argument has colour $i$.

  • Axioms are such that $S$ and $AP$ are interpreted right (this should be simple but mundane, I think....) plus axiom saying that there is not arithmetic progression of length $l$ ($\neg \exists x_1,x_2,\dots,x_l : \ AP(x_1,x_2,x_3) \wedge \dots \wedge AP(x_{l-2},x_{l-1},x_l) \wedge C_i(x_1) \wedge \cdot \wedge C_i(x_l) $ )

Now, the "concrete" version says basically that $\mathcal{T}$ has no finite models of arbitrary large cardinality, and the "abstract" version says that there are no infinite mdels for $\mathcal{T}$. By compactness principle, these are equivalent, so we are done.

Of course, there are two problems: there are some axioms to fill in, and it is not quite shorter than the standard application. For the latter, I believe with less trivial applications, the model theretic approach an become simpler and/or more automatic; at least it shifts the spot that requires work.

Question: 1. Can the missing axioms be filled in, and if so, what is the simplest way? Do I correctly feel that this is essentailly a very simple thing? 2. Would the model-theoretic approach work without major modifications for other theorems (say, Ramsey theorem for hypergraphs, Hindman theorem, etc.)?

1

There are 1 best solutions below

0
On BEST ANSWER

One might be able to get the existence of a finite $N$ by the underspill (or underflow) principle over the hyperreals. See for example the book

Robert Goldblatt (1998). Lectures on the hyperreals. An introduction to nonstandard analysis. Springer

which contains a detailed treatment of some Ramsey theorems.