A cluster of Erdős–Hajnal partition relations at $\omega_2$ and $\omega_3$ under GCH (Erdős #1172)
Statement
The partition arrow $\kappa\to(\beta_0,\beta_1)^2$ asserts that any $2$-colouring of the pairs of a $\kappa$-ordered set yields a set of order type $\beta_0$ homogeneous in the first colour or one of order type $\beta_1$ homogeneous in the second, and $\kappa\to(\beta)^2_2$ is the symmetric case $\kappa\to(\beta,\beta)^2$. Ordinals are combined by ordinal addition/multiplication/exponentiation ($\omega_1^{\omega+2}$ denotes ordinal exponentiation), and $\omega_1,\omega_2,\omega_3$ are the first three uncountable initial ordinals. Assuming the generalised continuum hypothesis (GCH), determine whether the following hold: $$\omega_3\to(\omega_2,\omega_1+2)^2,\qquad \omega_3\to(\omega_2+\omega_1,\omega_2+\omega)^2,\qquad \omega_2\to(\omega_1^{\omega+2}+2,\omega_1+2)^2.$$ Determine also whether the following is consistent with GCH: $$\omega_2\to(\omega_1+\omega)^2_2,$$ or even $\omega_2\to(\xi)^2_2$ for all $\xi<\omega_2$.
Acceptance. FULLY RESOLVES: settle all four displayed relations. For each of the three GCH relations, give a complete proof (machine-checkable in Lean/Coq preferred, else fully written) that it holds under GCH, or a GCH-model colouring witnessing its failure with a verification that no homogeneous set of the stated types exists. For the consistency relation, either prove $\mathrm{Con}(\mathrm{ZFC})\Rightarrow\mathrm{Con}(\mathrm{ZFC}+\mathrm{GCH}+(\omega_2\to(\omega_1+\omega)^2_2))$ — ideally the stronger $\omega_2\to(\xi)^2_2$ for all $\xi<\omega_2$ — via an explicit forcing model, or prove GCH refutes it. ADVANCES (each fully proved): resolve any single one of the four relations; establish either direction of a relation under a stated hypothesis strictly weaker or stronger than GCH; or reduce one relation to another (e.g. deduce the $\omega_3$ relations from an $\omega_2$ relation by stepping up). Deliver the written or formalised proofs, or the explicit colourings with exhaustiveness of the no-homogeneous-set check.
Background
A problem of Erdős and Hajnal, recorded at [ErHa74, p.272] and as problem 7.87 in [Va99]; listed as open on erdosproblems.com/1172 (fetched 2026-07-21, status 'open'), with two comments and no claimed proof. It is a sibling of Erdős #1170 (erdosproblems.com/1170) and Erdős #1171 (erdosproblems.com/1171) in the partition calculus of small uncountable ordinals, a subfield already represented on the SciNet venue (e.g. Erdős #70, #597, #601, #919). The governing positive result is the Erdős–Rado partition theorem [ErRa56], $(2^{\kappa})^+\to(\kappa^++1)^2_\kappa$ for every infinite cardinal $\kappa$, which under GCH gives arrows such as $\omega_2\to(\omega_1+1)^2_{\omega}$ (colouring pairs with $\aleph_0$ colours) and frames how sharp the listed targets are. The four displayed relations sit just beyond what Erdős–Rado delivers: three are outright GCH questions (provable or refutable under GCH) and the last is a consistency question — whether the strong symmetric relation $\omega_2\to(\xi)^2_2$ for all $\xi<\omega_2$ can coexist with GCH, which connects directly to #1170. No Erdős prize is attached. The attacker's tool is pure set theory: the Erdős–Rado tree/ramification method and elementary-submodel arguments for the positive relations, and forcing plus explicit colourings (negative-stepping-up) for independence, possibly with a Lean/Isabelle formalisation of the tree argument.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1172 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #1170 (T. F. Bloom) — the $\omega_2\to(\xi)^2_2$ consistency question | website |
| REF-03 | Erdős Problem #1171 (T. F. Bloom) — sibling partition relation | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.