Ramsey theorem and ultrafilters (II)

This is a continuation of the post Has Ramsey theorem anything to do with the ultrafilter monad?  In this post I want to write the shortest proof of Ramsey theorem (in finite or infinite version) I can make for the moment. This is probably well-known, please tell me if so, with references, and I shall update the post.

The motivation is the fact that I don’t get why one has to reason by compactness and contradiction, so I am looking for a direct proof (which is of course still non constructive).

Notation: for any k \in \mathbb{N} with k > 0,  we denote by [k] the set \left\{ 1, ... , k \right\} and by \lceil k \rceil the set \left\{0,1, ... , k\right\}.

Definition: A function c: \mathbb{N} \times \mathbb{N} \times \mathbb{N} \rightarrow \lceil k \rceil is a kcolor if it has the following distance-like properties

  • it is symmetric, i.e. for any permutation (abc) of the set [3] and for any x, y, z \in \mathbb{N} we have c(x_{a}, x_{b}, x_{c}) = c(x_{1}, x_{2}, x_{3}),
  • it is reflexive, i.e. for any x \leq y \leq z in \mathbb{N}c(x,y,z) = 0 if and only if x=y.

Explanation: a sequence of coloured complete graphs K_{n} is a function c(x,y,n) = c_{n}(x,y), defined for any x<y (in order to colour the non-oriented edge from x to y) and for any y \leq n (because is a colouring of the complete graph with n vertices). We complete the colouring by c(x,x,n) = 0.  In case the color function does not depend on n then it’s just a colouring of K_{\infty}.

Fact. Any color function admits an unique continuous extension to U\mathbb{N}^{3} , which is identified with \left(U\mathbb{N}\right)^{3}.

Proof of Ramsey theorem: for any non-principal ultrafilter \beta \in U\mathbb{N} \setminus \mathbb{N}, there exists and is  unique a colour j \in [k] such that c(\beta, \beta, \beta) = j. By continuity,

\lim_{x \rightarrow \beta} \lim_{y \rightarrow \beta} \lim_{n \rightarrow \beta} c(x,y,n) = j.

Can you see why this is Ramsey theorem? [added: curry and lazy evaluate, so to say, the three limits.]

Advertisements

2 thoughts on “Ramsey theorem and ultrafilters (II)”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s