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 with , we denote by the set and by the set .
Definition: A function is a –color if it has the following distance-like properties
- it is symmetric, i.e. for any permutation of the set and for any we have ,
- it is reflexive, i.e. for any in , if and only if .
Explanation: a sequence of coloured complete graphs is a function , defined for any (in order to colour the non-oriented edge from to ) and for any (because is a colouring of the complete graph with vertices). We complete the colouring by . In case the color function does not depend on then it’s just a colouring of .
Fact. Any color function admits an unique continuous extension to , which is identified with .
Proof of Ramsey theorem: for any non-principal ultrafilter , there exists and is unique a colour such that . By continuity,
Can you see why this is Ramsey theorem? [added: curry and lazy evaluate, so to say, the three limits.]