Proof of `Ramsey's theorem for colourings of pairs`
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 unordered pairs of a large enough finite set with colours admits a monochromatic subset of size : the multicolour Ramsey theorem for pairs, over the canonical carriers and with no hypothesis on the number of colours.
Proof strategy
The mathematical content is the ported , which asks for a list of requested sizes, one per colour, and produces a monochromatic in the colour whose entry it meets. That statement is proved by induction on the list of colours from the two-colour graph form (Erdős–Szekeres neighbourhood splitting): the first colour is turned into a graph, a clique in it is monochromatic of the first colour, and an independent set carries a colouring by the remaining colours to which the induction hypothesis applies.
The bridge to the submitted statement instantiates the list as , so that all colours request the same size , and transports along , precomposing the given colouring with in one direction and casting the returned colour index back in the other. The carrier is , whose is , and the returned is coerced to a , its cardinality translated by .
The submitted statement carries no positivity hypothesis on the number of colours, whereas the ported one needs a nonempty list. The case is therefore split off first and closed outright: with the carrier is nonempty, so the assumed colouring produces an element of , which is absurd.
Attribution
The proof is ported from the proof package of the submission Monadic dependence and neighborhood complexity (), where it appears as Theorems 3.7 and 3.8 of the source lecture notes. The theorem is due to Ramsey, On a problem of formal logic (Proc. London Math. Soc. 1930); the two-colour induction used here is the Erdős–Szekeres argument.