2
$\begingroup$

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.)?

$\endgroup$
8
  • $\begingroup$ What do you mean "some axioms"? $\endgroup$
    – Asaf Karagila
    May 31, 2013 at 0:03
  • $\begingroup$ At a point, I say I throw axioms that make $S$ and $AP$ work as desired. Things like $S(x,z) = S(y,z) \Rightarrow x = y$ or $\neg S(x,0)$, and so on. These are these axioms that I'm referring to. $\endgroup$ May 31, 2013 at 0:06
  • $\begingroup$ Ah. Also the successor function is usually a one-place function symbol. That is, $S(x)$, not $S(x,y)$. The latter would be a relation, not a function. Function symbols are interpreted as functions, i.e. they return objects, not truth value (true/false); on the other hand $S(x,y)$ saying that $y$ is the successor of $x$ is a binary predicate. $\endgroup$
    – Asaf Karagila
    May 31, 2013 at 0:07
  • $\begingroup$ Yes, I know. But here I want to allow for the interval to terminate. So there will be (at most) one element with no successor. $\endgroup$ May 31, 2013 at 0:08
  • $\begingroup$ It doesn't matter for the intended interpretation, and one can always add an axiom stating that the relation $S$ is functional, but if one wants to refer to it in terms and formulas then it's easier to use it as a function symbol. Unless, of course, you have a good reason to prefer a predicate (i.e. you have to use induction over formulas and you want to save yourself the trouble of induction over the terms as well). $\endgroup$
    – Asaf Karagila
    May 31, 2013 at 0:13

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .