Lax14.TupleRamsey

Ramsey's theorem for tuples

concepts/Lax14/TupleRamsey.lean · lax-14

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Evidence

    Each proof establishes this claim relative to its assumptions.

    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

    1import Lax14.OrderTypes
    2import Mathlib.Data.Set.Card
    3
    4/-!
    5---
    6title: Ramsey's theorem for tuples
    7type: theorem
    8---
    9For every number of colours *k*, every arity ℓ and every size *s* there is
    10an *N* such that for every colouring of the ℓ-tuples over a linearly
    11ordered *N*-element set with *k* colours there is a subset *I* of size *s*
    12on which the colour of a tuple depends only on its order type: any two
    13tuples with entries in *I* that are arranged in the same way receive the
    14same colour. This is the finite Ramsey theorem for hypergraphs of
    15Erdős and Rado, in the order-type form used in model theory.
    16
    17# Formalization notes
    18
    19Tuples are arbitrary functions `Fin ℓ → Fin n`, so repeated entries and
    20every ordering of the entries are allowed. This is stronger than colouring
    21the ℓ-element *subsets* of the ground set — that classical form is the
    22special case where the colouring only depends on the increasing
    23enumeration — and it is the form that applications consume, since the
    24tuples they colour arise from arbitrary indexed families.
    25
    26Homogeneity is stated as "tuples with entries in *I* and equal order types
    27receive equal colours", rather than as the existence of a function from
    28order types to colours through which the colouring factors. The two are
    29equivalent — such a function is obtained by choice — and the stated form
    30carries no choice and needs no default colour for the order types that no
    31tuple over *I* realizes.
    32
    33The ground set is `Fin n` with its standard linear order, the canonical
    34carrier of this submission; sizes are `Set.ncard`, stated as "at least".
    35As in the other statements, no hypothesis is placed on the number of
    36colours: with `k = 0` there is no colouring at all.
    37-/
    38
    39namespace Lax14.TupleRamsey
    40
    41open Lax14.OrderTypes
    42
    43/-- Ramsey's theorem for tuples: every `k`-colouring of the `ℓ`-tuples
    44over a large enough linearly ordered finite set has a subset of size `s`
    45on which the colour of a tuple depends only on its order type. -/
    46axiom 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
    52end Lax14.TupleRamsey
    53
    Show Proof

    Formalization notes

    Tuples are arbitrary functions FinFinnFin ℓ → Fin n, 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 FinnFin n with its standard linear order, the canonical carrier of this submission; sizes are Set.ncardSet.ncard, stated as "at least". As in the other statements, no hypothesis is placed on the number of colours: with k=0k = 0 there is no colouring at all.

    Used by

    none

    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

    Loading discussion…