No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Theorem
For every number of colours k, every arity ℓ and every size s there is an N such that for every colouring of the ℓ-tuples over a linearly ordered N-element set with k colours there is a subset I of size s on which the colour of a tuple depends only on its order type: any two tuples with entries in I that are arranged in the same way receive the same colour. This is the finite Ramsey theorem for hypergraphs of Erdős and Rado, in the order-type form used in model theory.
Lean source view on GitHub
| 1 | import Lax14.OrderTypes |
| 2 | import Mathlib.Data.Set.Card |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Ramsey's theorem for tuples |
| 7 | type: theorem |
| 8 | --- |
| 9 | For every number of colours *k*, every arity ℓ and every size *s* there is |
| 10 | an *N* such that for every colouring of the ℓ-tuples over a linearly |
| 11 | ordered *N*-element set with *k* colours there is a subset *I* of size *s* |
| 12 | on which the colour of a tuple depends only on its order type: any two |
| 13 | tuples with entries in *I* that are arranged in the same way receive the |
| 14 | same colour. This is the finite Ramsey theorem for hypergraphs of |
| 15 | Erdős and Rado, in the order-type form used in model theory. |
| 16 | |
| 17 | # Formalization notes |
| 18 | |
| 19 | Tuples are arbitrary functions `Fin ℓ → Fin n`, so repeated entries and |
| 20 | every ordering of the entries are allowed. This is stronger than colouring |
| 21 | the ℓ-element *subsets* of the ground set — that classical form is the |
| 22 | special case where the colouring only depends on the increasing |
| 23 | enumeration — and it is the form that applications consume, since the |
| 24 | tuples they colour arise from arbitrary indexed families. |
| 25 | |
| 26 | Homogeneity is stated as "tuples with entries in *I* and equal order types |
| 27 | receive equal colours", rather than as the existence of a function from |
| 28 | order types to colours through which the colouring factors. The two are |
| 29 | equivalent — such a function is obtained by choice — and the stated form |
| 30 | carries no choice and needs no default colour for the order types that no |
| 31 | tuple over *I* realizes. |
| 32 | |
| 33 | The ground set is `Fin n` with its standard linear order, the canonical |
| 34 | carrier of this submission; sizes are `Set.ncard`, stated as "at least". |
| 35 | As in the other statements, no hypothesis is placed on the number of |
| 36 | colours: with `k = 0` there is no colouring at all. |
| 37 | -/ |
| 38 | |
| 39 | namespace Lax14.TupleRamsey |
| 40 | |
| 41 | open Lax14.OrderTypes |
| 42 | |
| 43 | /-- Ramsey's theorem for tuples: every `k`-colouring of the `ℓ`-tuples |
| 44 | over a large enough linearly ordered finite set has a subset of size `s` |
| 45 | on which the colour of a tuple depends only on its order type. -/ |
| 46 | axiom exists_orderType_homogeneous (k ℓ s : ℕ) : |
| 47 | ∃ N : ℕ, ∀ (n : ℕ) (c : (Fin ℓ → Fin n) → Fin k), N ≤ n → |
| 48 | ∃ I : Set (Fin n), s ≤ I.ncard ∧ |
| 49 | ∀ a b : Fin ℓ → Fin n, (∀ i, a i ∈ I) → (∀ i, b i ∈ I) → |
| 50 | orderType a = orderType b → c a = c b |
| 51 | |
| 52 | end Lax14.TupleRamsey |
| 53 |
Formalization notes
Tuples are arbitrary functions , so repeated entries and every ordering of the entries are allowed. This is stronger than colouring the ℓ-element subsets of the ground set — that classical form is the special case where the colouring only depends on the increasing enumeration — and it is the form that applications consume, since the tuples they colour arise from arbitrary indexed families.
Homogeneity is stated as "tuples with entries in I and equal order types receive equal colours", rather than as the existence of a function from order types to colours through which the colouring factors. The two are equivalent — such a function is obtained by choice — and the stated form carries no choice and needs no default colour for the order types that no tuple over I realizes.
The ground set is with its standard linear order, the canonical carrier of this submission; sizes are , stated as "at least". As in the other statements, no hypothesis is placed on the number of colours: with there is no colouring at all.
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments