1 - Introduction

Summary

Motivation

The Ramsey theory starts with a classical result:

Fact 1.1For every partition of pairs of natural numbers into two classes there is a homogeneous infinite set: a set a ⊂ ω such that all pairs of natural numbers from a belong to the same class.

It is not difficult to generalize this result for partitions into any finite number of classes. An attempt to generalize further, for partitions into infinitely many classes, hits an obvious snag: every pair of natural numbers could fall into its own class, and then certainly no infinite homogeneous set can exist for such a partition. Still, there seems to be a certain measure of regularity in partitions of pairs even into infinitely many classes. This is the beginning of canonical Ramsey theory.

Fact 1.2 (Erdős–Rado (Erdős and Rado 1950)) For every equivalence relation E on pairs of natural numbers there is an infinite homogeneous set: a set a ⊂ ω on which one of the following happens:

1. (i) p E q ↔ p = q for all pairs p, q ∈[a]²;

2. (ii) p E q ↔ min(p) = min(q) for all pairs p, q ∈[a]²;

3. (iii) p E q ↔ max(p) = max(q) for all pairs p, q ∈[a]²;

4. (iv) p E q for all pairs p, q ∈[a]².