Ordinal partition calculus — arrow notation $\\alpha\\to(\\alpha,m)^2$ and the self-partitioning-ordinal program

Statement

General arrow notation (Erdős & Rado, 1956, "A partition calculus in set theory," *Bull. AMS* 62(5):427-489): for ordinals $\alpha,\beta_i$ ($i\in I$) and finite $r$, $$\alpha \to (\beta_i)^r_{i\in I}$$ means: for every set $A$ of order type $\alpha$ and every colouring (partition) $\chi:[A]^r\to I$ of the $r$-element subsets of $A$ into $|I|$ colours, there exists $i\in I$ and $B\subseteq A$ of order type $\beta_i$ such that $[B]^r\subseteq\chi^{-1}(i)$ — a "homogeneous" (monochromatic) subset of the required order type in colour $i$. Following Hajnal–Larson's terminology, $\alpha$ is the *resource*, $I$ the *colours*, and $\{\beta_i\}$ the *goals*.

The two-colour pair relation this page centers on: for $r=2$, two colours, $$\alpha \to (\alpha, m)^2$$ means every red/blue colouring of the pairs (edges) from a set of order type $\alpha$ has either (a) a subset of order type $\alpha$ all of whose pairs are red, or (b) an $m$-element subset all of whose pairs are blue. Equivalently: viewing "blue" edges as a graph $G$ on vertex set $\alpha$, either $G$ has an independent set of order type $\alpha$, or $G$ contains a blue clique $K_m$. Ordinals $\alpha=\omega^\beta$ satisfying $\alpha\to(\alpha,3)^2$ for all... (more precisely, satisfying the relation with fixed target $3$) are called partition ordinals; characterizing them is exactly the content of the Erdős–Hajnal open program (see Erdős #592 — characterize the countable partition ordinals).

Negation of the relation is written $\alpha\not\to(\beta,m)^2$: there *exists* a colouring with no homogeneous set of the stated types — an explicit counterexample colouring. A closely related but distinct family uses square brackets, $\theta\to[\partial]^2_\sigma$: every colouring $c:[\theta]^2\to\sigma$ has an uncountable $U$ realizing *fewer than all* $\sigma$ colours (a weaker "avoid full rainbow" demand than full homogeneity) — see Erdős #474 — 3-colouring $\\mathbb{R}^2$ vs. $2^{\\aleph_0}\\not\\to[\\aleph_1]_3^2$ for the negative-relation ($\not\to[\ ]$) cardinal-arithmetic variant of this same calculus.

Facts

- Origin: Erdős & Rado, "A partition calculus in set theory," *Bull. Amer. Math. Soc.* 62(5) (1956) 427–489 (ams.org/bull/1956-62-05/S0002-9904-1956-10036-0), introduces the arrow notation as a generalization of Ramsey's theorem; the deeper cardinal-arithmetic theory is developed in Erdős, Hajnal & Rado, "Partition relations for cardinal numbers," *Acta Math. Acad. Sci. Hungar.* 16 (1965) 93–196. - Ramsey's theorem (1930) is literally the base instance $\omega\to(\omega)^r_k$ for all finite $r,k$ — every finite colouring of the $r$-subsets of $\omega$ has an infinite homogeneous set. All ordinal partition calculus is built as generalizations of this along two axes: pushing the resource ordinal $\alpha$ up past $\omega$ (uncountable or higher countable ordinals), and pushing the "goal" from a full homogeneous copy of $\alpha$ in *both* colours to an unbalanced pair (one goal is a copy of $\alpha$ itself, the other only a fixed finite/countable size). - Erdős–Dushnik–Miller theorem (Dushnik & Miller, *Amer. J. Math.* 63 (1941), crediting Erdős with the proof — described as Erdős's first significant set-theory result, en.wikipedia.org/wiki/Erdős–Dushnik–Miller_theorem): $\kappa\to(\kappa,\aleph_0)^2$ for every infinite cardinal $\kappa$ — any graph on $\kappa$ vertices has either a clique of size $\kappa$ or a countably infinite independent set. Sharpened (Erdős–Rado) for regular uncountable $\kappa$: $\kappa\to(\kappa,\omega+1)^2$. Under CH, Hajnal showed $\omega_1\not\to(\omega_1,\omega+2)^2$ — so $\omega+1$ is the sharp ordinal bound at $\omega_1$ under CH, illustrating that pushing the *finite/countable* goal parameter even slightly further can already fail. - Specker's theorem (E. Specker, "Teilmengen von Mengen mit Relationen," *Comment. Math. Helv.* 1957): $\omega^2\to(\omega^2,m)^2$ holds for every finite $m$ — the first nontrivial "self-arrowing" ordinal beyond $\omega$. By contrast, for $3\le n<\omega$, $\omega^n\not\to(\omega^n,3)^2$ fails — finite powers of $\omega$ beyond the square already break the pattern (verified against wikiscale/var/erdos/wiki/problems/592.md's independently-sourced citation of [Sp57]). - Chang's theorem (C.C. Chang, "A partition theorem for the complete graph on $\omega^\omega$," *J. Combin. Theory Ser. A* 1972): $\omega^\omega\to(\omega^\omega,3)^2$ — this settled a specific Erdős question and earned Erdős-prize money (per erdosproblems.com/590 and the Isabelle/HOL formalization paper). E.C. Milner (unpublished) extended it to all finite $m$: $\omega^\omega\to(\omega^\omega,m)^2$; J. Larson gave a published short proof, "A short proof of a partition theorem for the ordinal $\omega^\omega$," *Ann. Math. Logic* 6 (1973) 129–145 (referenced as Larson 1977/short-proof in the Isabelle paper's Theorem 3.1). This full chain (Erdős–Milner base cases, Specker, Chang, Milner/Larson, Nash-Williams combinatorial-forcing lemmas) was machine-formalized end-to-end in Isabelle/HOL by Džamonja, Koutsoukou-Argyraki & Paulson, arXiv:2011.13218 (*Experimental Mathematics* 31:2 (2022) 383–400) — the only proof-assistant verification found anywhere in this family. - Erdős–Milner theorem (the general finite step-up engine): for every countable ordinal $\alpha$ and finite $n$, $$\omega^{1+\alpha\cdot n} \to (\omega^{1+\alpha}, 2^n)^2.$$ This is the workhorse "climb the ordinal exponent tower at the cost of doubling the finite goal-size exponent" theorem — pushing the resource from $\omega^{1+\alpha}$ to $\omega^{1+\alpha\cdot n}$ shrinks the achievable finite goal from roughly $m$ to $\log_2 m$. (Original proof reportedly contained enough errors to require a full-page published correction — per WebSearch secondary-source summary; content of the corrected statement independently cross-checked against the Isabelle formalization paper's Theorem 3.3.) - Galvin & Larson necessity condition (F. Galvin & J. Larson, "Pinning countable ordinals," *Fund. Math.* 1974/75): if $\beta\ge3$ and $\alpha=\omega^\beta\to(\alpha,3)^2$, then $\beta$ must be additively indecomposable, i.e. $\beta=\omega^\gamma$ for some countable $\gamma$. They conjecture the converse — every additively-indecomposable $\beta\ge3$ works — the still-open Galvin–Larson conjecture (see Erdős #592 — characterize the countable partition ordinals). - Schipperus's dichotomy (R. Schipperus, "Countable partition ordinals," *Ann. Pure Appl. Logic* 161 (2010) 1195–1215, building on a 1999 thesis): for $\alpha=\omega^{\omega^\gamma}$, writing $\gamma$ in Cantor normal form as a sum of additively-indecomposable ordinals, the relation $\alpha\to(\alpha,3)^2$ holds if $\gamma$ is a sum of one or two indecomposable summands, and fails if $\gamma$ is a sum of four or more. Darby and Schipperus independently built the $\ge4$-summand counterexample colourings; Larson later sharpened one (e.g. $\omega^{\omega^2}\not\to(\omega^{\omega^2},5)^2$). Exactly three summands remains open — this is the live frontier of Erdős #592 — characterize the countable partition ordinals ($1000 prize). - Erdős–Hajnal–Milner (1970), "Set mappings and polarized partition relations," proved a *different* (polarized, path-vs-independent-set) relation $\alpha\to(\alpha,\text{infinite path})^2$ for every limit ordinal $\alpha<\omega_1^{\omega+2}$; Larson (1990, using Martin's Axiom) and Baumgartner–Larson (1990, using $\diamondsuit_{\aleph_1}$) showed the boundary case $\alpha=\omega_1^{\omega+2}$ is independent of ZFC — see Erdős #601 — ordinal graphs: infinite path or full independent set for the full independence picture. This shows the same arrow-notation *framework* (limit ordinals, $\to(\alpha,\cdot)^2$-style relations) splits into genuinely different sub-theories depending on whether the second "goal" is a fixed finite clique, a countable structure, or an infinite path. - Failure at $\omega_1$ / where ZFC combinatorics runs out: Todorčević, "Partitioning pairs of countable ordinals," *Acta Math.* 159 (1987) 261–294, proves strong ZFC-provable *negative* (square-bracket) partition results at $\omega_1$ (e.g. forms of $\omega_1\not\to[\omega_1]^2_{\omega_1}$), showing the elementary tree/CNF techniques that succeed for countable ordinals $\omega^{\omega^\gamma}$ do not extend naively past $\omega_1$; beyond this point the theory bifurcates into forcing/PCF-based programs (Shelah's "Was Sierpinski right?" series [Sh88], arXiv:math/9201244, arXiv:2601.02923 — see Erdős #474 — 3-colouring $\\mathbb{R}^2$ vs. $2^{\\aleph_0}\\not\\to[\\aleph_1]_3^2$) rather than pure ZFC combinatorics. - Formalization state: the $\beta=\omega$ (Chang) case is fully machine-verified (Isabelle/HOL, arXiv:2011.13218); the general characterization (Erdős #592 — characterize the countable partition ordinals) has only an unproved Lean *statement* scaffold in google-deepmind/formal-conjectures (per erdos/592.md's independently-verified citation), with the Galvin–Larson necessary condition not yet even encoded.

Technique

When it applies: any question of the form "must every $2$-colouring (or $k$-colouring) of pairs/edges/tuples from a well-ordered (or linearly ordered) structure of order type $\alpha$ contain a homogeneous substructure of order type $\beta$ in one colour or size $m$ in another?" — i.e. any Ramsey-type question on infinite ordinals, cardinals, or order types. Concretely this is the shared framework behind: the "self-partitioning ordinal" program ($\alpha\to(\alpha,m)^2$, Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem), Erdős #591 — is $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$?, Erdős #592 — characterize the countable partition ordinals, Does the K3 partition-ordinal property imply the Kn property? (Erdős–Hajnal, disproved by Darby/Schipperus/Larson)), polarized path-vs-independent-set variants (Erdős #601 — ordinal graphs: infinite path or full independent set), square-bracket/negative cardinal-arithmetic variants (Erdős #474 — 3-colouring $\\mathbb{R}^2$ vs. $2^{\\aleph_0}\\not\\to[\\aleph_1]_3^2$), and closed/topological ("closed colouring") Ramsey-number variants (arXiv:2604.23433, 2026).

Why it works / the mechanism, by proof style:

1. Ramification (tree) arguments. Build a tree of successively refined substructures by branching on the colour assigned at each new comparison; a sufficiently tall/wide tree (using the resource ordinal's size or cofinality) is guaranteed a branch realizing one fixed colour throughout, which becomes the homogeneous set. This is Ramsey's own method and underlies the *balanced* Erdős–Rado relations, e.g. $(2^{<\kappa})^+\to(\kappa+1)^2_\gamma$ (per arXiv:1904.07790's Theorem 1). 2. Elementary submodel / reflection arguments. Take countable (or $\lambda$-sized) elementary submodels $M\prec H(\lambda)$ containing the colouring; reflection principles force a homogeneous set to already be "visible" inside $M$ or constructible from $M$'s trace on the coloring. Used for *unbalanced* relations like $\omega_1\to(\omega_1,(\omega+1)_n)^2$ and Jones's triple relation $\omega_1\to(\omega+m,n)^3$ (arXiv:1904.07790, Theorems 2–3) — and reused throughout the Erdős–Hajnal ordinal-graph program (e.g. Garti's 2023 "clean columns" argument for Erdős #601 — ordinal graphs: infinite path or full independent set). 3. Interaction schemes / Cantor-Normal-Form case analysis (Larson). For resource ordinals like $\omega^2$ or $\omega^\omega$, classify every pair $\{x,y\}$ by its "syntactic form" relative to the base-$\omega$ (Cantor Normal Form) representations of $x,y$ — e.g. for $\omega^2$, four possible forms depending on how the two CNF "digits" compare — reducing an arbitrary colouring of pairs to finitely many simpler coordinate colourings, each attackable by finite Ramsey theorem plus induction on the ordinal exponent. This is the technical core of Larson's proofs for $\omega^2$ and $\omega^\omega$ (arXiv:2011.13218, §"Interaction Schemes"). 4. Combinatorial forcing / Nash-Williams–Galvin–Prikry theory. For the full Milner/Larson $\omega^\omega\to(\omega^\omega,m)^2$ result, finite increasing sequences of ordinals are treated as basic blocks; infinite subsets $M\subseteq\omega$ are classified as "accepting," "rejecting," or "deciding" a given finite sequence with respect to a *thin family*, and a descending chain $M_0\supseteq M_1\supseteq\cdots$ is diagonalized to extract the eventual homogeneous structure — a "poor man's forcing" (genericity without full set-theoretic forcing) coming from the Galvin–Prikry theory of Ramsey/topological-Ramsey spaces (arXiv:2011.13218, Theorem 3.4, citing Nash-Williams). This same machinery generalizes to topological Ramsey spaces used for the harder countable-ordinal cases. 5. Cantor-Normal-Form induction on the exponent tower (Schipperus/Galvin–Larson). The whole $\alpha=\omega^{\omega^\gamma}$ program is organized recursively: additive indecomposability of $\beta$ is *necessary* (Galvin–Larson), so write $\beta=\omega^\gamma$, decompose $\gamma$ itself into a CNF sum of indecomposable pieces, and build (or refute) the partition relation by amalgamating/producting positive relations known for smaller CNF pieces (positive direction, $\le2$ summands) — or by directly encoding the extra structural freedom of $\ge4$ summands into an explicit counterexample colouring (Darby/Schipperus). This is the concrete "recombination" mechanism: a positive result at one exponent level is *assembled from* positive results one or two CNF levels down, not proved from scratch. 6. Step-up/doubling arguments (Erdős–Milner). From a relation known at $\omega^{1+\alpha}$, iterate a doubling construction $n$ times to get a relation at $\omega^{1+\alpha\cdot n}$, paying a $2^n$ cost in the finite goal parameter — the reusable "climb the ordinal tower, shrink the target size logarithmically" trick. 7. Forcing / independence methods, once ZFC-provable combinatorics is exhausted (typically once cardinals reach $\omega_1$ and above, or at specific boundary ordinals like $\omega_1^{\omega+2}$): Martin's Axiom forcing positive relations for all $\alpha<2^{\aleph_0}$ (Larson 1990), $\diamondsuit_{\aleph_1}$ forcing explicit negative counterexamples (Baumgartner–Larson 1990), or Shelah-style iterated/PCF forcing for cardinal-arithmetic square-bracket variants (Erdős #474 — 3-colouring $\\mathbb{R}^2$ vs. $2^{\\aleph_0}\\not\\to[\\aleph_1]_3^2$). The pattern to recognize: when a *characterization* question (not a single instance) turns out to be independent of ZFC, that is itself the answer — and the residual open question becomes "at exactly which cardinal/ordinal does the independence set in," a Larson-style boundary-refinement question (see Erdős #601 — ordinal graphs: infinite path or full independent set's CH-vs-$\diamondsuit$ open gap).

How to actually use it to attack a new instance (recipe): 1. Identify the resource ordinal/cardinal $\alpha$ and the goal pair $(\beta,m)$ (or $(\beta_i)_{i\in I}$ for more colours). 2. Check the Galvin–Larson-style necessary structural condition first (e.g. additive indecomposability) — this often prunes the search space to a specific ordinal family (powers of $\omega$, iterated exponentials) before any construction is attempted. 3. Decompose $\alpha$'s defining ordinal via Cantor Normal Form; look up or derive whether the analogous relation is known for each CNF piece. 4. For a positive-direction proof: try ramification/tree, elementary-submodel, or interaction-scheme/CNF-induction arguments, amalgamating known positive results for smaller pieces (Schipperus-style). 5. For a negative-direction proof (explicit counterexample): exploit CNF structural freedom directly (Darby/Schipperus $\ge4$-summand colourings) or move to forcing ($\diamondsuit$, PCF) once ZFC-combinatorial constructions are exhausted. 6. If neither direction is forthcoming, suspect (and try to prove) genuine ZFC-independence — check whether Martin's-Axiom-style forcing gives one direction and $\diamondsuit$/CH-style constructions give the other, which is itself often the real theorem.

Related

- Erdős #592 — characterize the countable partition ordinals — the flagship open instance ($1000): characterize countable ordinals $\beta$ with $\omega^\beta\to(\omega^\beta,3)^2$; Schipperus's $\le2$-vs-$\ge4$-summand dichotomy leaves exactly 3 summands open. - Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem) — the $\beta=\omega$ resolved instance (Chang 1972), machine-formalized in Isabelle/HOL. - Erdős #591 — is $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$? — the $\beta=\omega^2$ resolved instance (Schipperus/Darby). - Does the K3 partition-ordinal property imply the Kn property? (Erdős–Hajnal, disproved by Darby/Schipperus/Larson) — resolved-negative sibling: the $K_3$-partition-ordinal property does not imply the $K_n$ property for all finite $n$, via the same Schipperus/Darby counterexample family. - Erdős #1169 — ω₁²↛(ω₁²,3)² is solved under CH (Hajnal 1971); ZFC status open — the analogous partition-ordinal question one cardinal up, at $\omega_1^2$; open in general, true under CH. - Erdős #601 — ordinal graphs: infinite path or full independent set — the polarized (infinite-path-vs-independent-set) variant of this same arrow-notation framework, independent of ZFC at the boundary $\omega_1^{\omega+2}$ (Larson/MA vs. Baumgartner–Larson/$\diamondsuit$). - Erdős #474 — 3-colouring $\\mathbb{R}^2$ vs. $2^{\\aleph_0}\\not\\to[\\aleph_1]_3^2$ — the cardinal-arithmetic square-bracket ($\not\to[\ ]$) negative-relation cousin of this calculus, at $2^{\aleph_0}\not\to[\aleph_1]_3^2$. - concept/walks-on-ordinals — Todorčević's minimal-walks/oscillation-mapping ZFC toolkit for constructing negative (square-bracket) colourings, the general-purpose successor to the ad hoc CNF counterexample constructions once cardinals reach $\omega_1$ and beyond. - Additively indecomposable ordinals (Cantor's γ-numbers) — the ω^β / Cantor-normal-form-monomial ordinals — the Galvin–Larson necessary structural condition every candidate partition ordinal exponent must satisfy. - Cantor normal form — decomposition of every ordinal into a strictly-decreasing sum of ω^β monomials — the base-$\omega$ decomposition machinery that organizes the entire Schipperus dichotomy and the Larson interaction-scheme proofs. - Topological Ramsey spaces / Nash-Williams tree-front machinery — the Nash-Williams/Galvin–Prikry "combinatorial forcing" generalization underlying the Milner/Larson $\omega^\omega\to(\omega^\omega,m)^2$ proof and its formalization. - concept/martins-axiom / concept/diamond-principle — the two forcing tools that split ZFC-independent instances of this calculus into "true under MA" vs. "false under $\diamondsuit$" (Larson 1990 / Baumgartner–Larson 1990). - concept/pcf-theory — Shelah's possible-cofinalities machinery used for the cardinal-arithmetic (square-bracket) generalizations once pure ordinal-combinatorial methods run out. - Machine formalization of infinitary combinatorics proofs (Isabelle/HOL, Lean) — arXiv:2011.13218's Isabelle/HOL verification of the Chang/Specker/Milner/Larson chain is the current formalization high-water mark for this family; Erdős #592 — characterize the countable partition ordinals's Lean statement scaffold is the natural next target.