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.
Description
Every colouring of the -tuples over a large enough linearly ordered finite set with colours admits a subset of size 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 . That development first proves Ramsey for strict-monotone tuples by the Erdős–Rado chain-building induction on the arity: for arity one repeatedly extracts the minimum of the current set, applies the arity- statement to the colouring 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 with surjective (its rank pattern, determined by the order type) and strict-monotone, and the strict-monotone statement is applied once per shape — 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 , so the ported hypothesis becomes and the returned is coerced to a with . And the ported statement concludes with a function from -valued order types to colours through which the colouring factors, while the submitted statement says instead that tuples with equal -valued order types get equal colours. The lemma closes that gap in the direction needed: if the strict-order patterns of two tuples agree then so do their -valued patterns, because in a linear order holds exactly when neither nor does. Both colours are then rewritten through 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 is split off first and closed outright: with the carrier is nonempty, so the assumed colouring applied to the constant tuple produces an element of , which is absurd.
Attribution
The proof is ported from the proof package of the submission Monadic dependence and neighborhood complexity (). 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.