Proof of `Ramsey's theorem for tuples`

groundedproofs/Lax14Proofs/TupleRamsey.lean · lax-14

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Every colouring of the -tuples over a large enough linearly ordered finite set with kk colours admits a subset of size ss on which the colour of a tuple depends only on its order type: the finite Ramsey theorem for hypergraphs of Erdős and Rado, in the order-type form.

Proof strategy

The mathematical content is the ported Lax14Proofs.TupleCore.tupleRamseyAtSizeLax14Proofs.TupleCore.tupleRamseyAtSize. That development first proves Ramsey for strict-monotone tuples by the Erdős–Rado chain-building induction on the arity: for arity m+1m + 1 one repeatedly extracts the minimum vv of the current set, applies the arity-mm statement to the colouring bc(v::vb)b ↦ c (v ::ᵥ b) on the rest, and thereby colours the elements of a long chain by the colour their tuples receive; a pigeonhole on that colouring of elements produces the homogeneous set. An arbitrary tuple is then factored as a=eσa = e ∘ σ with σ:FinFinmσ : Fin ℓ → Fin m surjective (its rank pattern, determined by the order type) and ee strict-monotone, and the strict-monotone statement is applied once per shape (m,σ)(m, σ) — a finite type — shrinking the set each time. The resulting set is homogeneous for every shape at once, so the colour of a tuple is read off its shape alone.

Two bridges lead from there to the submitted statement. The ground set is taken to be all of FinnFin n, so the ported hypothesis NfinS.cardNfin ≤ S.card becomes NfinnNfin ≤ n and the returned FinsetFinset is coerced to a SetSet with Set.ncardcoefinsetSet.ncard_coe_finset. And the ported statement concludes with a function ff from OrderingOrdering-valued order types to colours through which the colouring factors, while the submitted statement says instead that tuples with equal PropProp-valued order types get equal colours. The lemma otpeqoforderTypeeqotp_eq_of_orderType_eq closes that gap in the direction needed: if the strict-order patterns of two tuples agree then so do their OrderingOrdering-valued patterns, because in a linear order ai=aja i = a j holds exactly when neither ai<aja i < a j nor aj<aia j < a i does. Both colours are then rewritten through ff and coincide.

The submitted statement carries no positivity hypothesis on the number of colours, whereas the ported one needs one to have a default colour available. The case k=0k = 0 is split off first and closed outright: with N:=1N := 1 the carrier FinnFin n is nonempty, so the assumed colouring applied to the constant tuple produces an element of Fin0Fin 0, which is absurd.

Attribution

The proof is ported from the proof package of the submission Monadic dependence and neighborhood complexity (Lax5Proofs/TupleRamsey.leanLax5Proofs/TupleRamsey.lean). The theorem is due to Erdős and Rado, Combinatorial theorems on classifications of subsets of a given set (Proc. London Math. Soc. 1952); the order-type formulation followed here is the one of Mählmann, Monadically stable and monadically dependent graph classes (PhD thesis, TU Wien 2024), Section 4.