Erdős problem 1172 — wave 8h
(d), recorded audit fact. Date of audit: 2026-07-28 UTC.
Outcome
- (b), proved modulo the Erdős–Rado theorem quoted on the problem page: the first GCH clause is true:
\[ \mathsf{GCH}\quad\Longrightarrow\quad \omega_3\to(\omega_2,\omega_1+2)^2. \]
- (b), relative consistency modulo two named theorems: if a huge cardinal is consistent, then there is a model of ZFC+GCH satisfying
\[ \omega_2\to(\omega_1+\omega)^2_2. \]
In fact the same model satisfies
\[ \omega_2\to(\xi)^2_2 \qquad\text{for every }\xi\leq\omega_1^2+1. \]
This is a large-cardinal upper bound, not a proof of consistency relative to bare ZFC.
- (b)/(a): the second clause is reduced exactly to a cofinal-branch statement for a colouring-generated end-extension tree.
- (b)/(a): the third clause is reduced exactly to extending the Baumgartner–Hajnal–Todorčević red set by one additional common red cap.
(b)/(d). The second and third GCH clauses, and the uniform assertion for every
\(\xi<\omega_2\), remain unresolved by this run. Thus the bundled problem is
not being declared solved.
0. Mandatory live-page gate
(d), browser-verified. I fetched the live page and its LaTeX view through
the Bright Data browser, not datacenter curl. On 2026-07-28 the page showed:
- status
OPEN; 0 claimed proofs for this problem;Interested in collaborating: None;Currently working on this problem: None;- two comments; and
- last edit 11 April 2026.
(d). Therefore no stop condition was present.
The following is the verbatim statement from the live LaTeX view:
Establish whether the following are true assuming the generalised continuum hypothesis:\[\omega_3 \to (\omega_2,\omega_1+2)^2,\]\[\omega_3\to (\omega_2+\omega_1,\omega_2+\omega)^2,\]\[\omega_2\to (\omega_1^{\omega+2}+2, \omega_1+2)^2.\]Establish whether the following is consistent with the generalised continuum hypothesis:\[\omega_2\to (\omega_1+\omega)_2^2,\]or even $\omega_2 \to (\xi)_2^2$ for all $\xi<\omega_2$.
The page's listed known result, also copied verbatim, is:
A problem of Erd\H{o}s and Hajnal. The Erd\H{o}s-Rado partition theorem \cite{ErRa56} states that\[(2^{\kappa})^+ \to (\kappa^++1)_\kappa^2\]for every infinite cardinal $\kappa$.
(d), browser-verified. The January 2026 comment says that the left side of
the last relation is visible in the original Erdős–Hajnal paper even though
it was missing from a truncated copy of Vaught. The April 2026 comment says
the wording had to be “consistent with GCH,” not “true assuming CH”; the live
page incorporates that correction. Neither comment claims a proof.
(d), source-verified. The original source is Erdős and Hajnal, *Unsolved and solved problems in set
theory*, Proceedings of Symposia in Pure Mathematics 25 (1974), pp. 269–287,
especially p. 272:
1. Conventions and one elementary rule
(a), definition. Write \(c:[\lambda]^2\to2\), with colour \(0\) red and colour \(1\) blue.
Then
\[ \lambda\to(\alpha,\beta)^2 \]means that every such \(c\) has either a red subset of order type \(\alpha\)
or a blue subset of order type \(\beta\).
(a), elementary-rigorous (downward monotonicity). If
\(\lambda\to(\alpha,\beta)^2\), \(\alpha'\leq\alpha\), and
\(\beta'\leq\beta\), then
\(\lambda\to(\alpha',\beta')^2\): take the appropriate initial suborder of
the homogeneous witness. Every “shrink” below uses only this rule.
2. The first GCH clause is an immediate theorem
Proposition 1 (b). Assuming GCH,
\[ \omega_3\to(\omega_2,\omega_1+2)^2. \]Proof. Apply the page's stated Erdős–Rado theorem with
\(\kappa=\omega_1\):
\[ (2^{\omega_1})^+\to(\omega_2+1)^2_{\omega_1}. \]Under GCH, \(2^{\omega_1}=\omega_2\), so the resource is \(\omega_3\).
Any two-colouring is also an \(\omega_1\)-colouring, hence it has a
homogeneous set \(H\) of order type \(\omega_2+1\). If \(H\) has colour
\(0\), shrink it to type \(\omega_2\); if it has colour \(1\), shrink it to
type \(\omega_1+2\). This is exactly the desired relation. \(\square\)
(b), with (d) source verification. The named input is Erdős and Rado, A partition calculus in set theory,
Bulletin of the AMS 62 (1956), 427–489:
The specialization after that theorem is (a).
3. A large-cardinal relative-consistency answer to the
\(\omega_1+\omega\) clause
Proposition 2 (b). If ZFC plus “there is a huge cardinal” is consistent,
then so is
\[ \mathsf{ZFC}+\mathsf{GCH} +\left[\omega_2\to(\xi)^2_2 \text{ for every }\xi\leq\omega_1^2+1\right]. \]In particular, this gives
\(\omega_2\to(\omega_1+\omega)^2_2\).
Proof.
1. (b) Eskew and Hayut's Main Theorem gives, relative to a huge
cardinal, a model in which for every regular \(\mu\) there is a normal
ideal \(I\) on \(\mu^+\) with
\[ \mathcal P(\mu^+)/I\cong \mathcal B(\operatorname{Col}(\mu,\mu^+)). \]
Immediately after the theorem they state that the existence of these
ideals implies GCH and that the ideal on \(\mu^+\) is
\(\mu^+\)-dense. Taking \(\mu=\omega\) gives an
\(\omega_1\)-dense ideal on \(\omega_1\) in a GCH model.
2. (a) GCH, in particular CH, gives
\[ \omega_1^{<\omega_1}=\omega_1. \]
Indeed the only infinite cardinal exponent below \(\omega_1\) is
\(\omega\), and
\[ \omega_1^\omega=(2^\omega)^\omega =2^{\omega\cdot\omega}=2^\omega=\omega_1. \]
3. (b) Foreman and Hajnal prove that if
\(\kappa^{<\kappa}=\kappa\) and \(\kappa\) carries a
\(\kappa\)-dense ideal, then
\[ \kappa^+\to(\kappa^2+1,\alpha)^2 \qquad(\alpha<\kappa^+). \]
Apply this at \(\kappa=\omega_1\). For any
\(\xi\leq\omega_1^2+1\), choose \(\alpha=\xi\) and shrink the first
goal:
\[ \omega_2\to(\omega_1^2+1,\xi)^2 \quad\Longrightarrow\quad \omega_2\to(\xi,\xi)^2. \]
4. (a) Since
\(\omega_1+\omega<\omega_1^2+1<\omega_2\), the particular choice
\(\xi=\omega_1+\omega\) proves the displayed consistency relation.
\(\square\)
(d), source-verified. The two named inputs were checked against these primary sources:
- Monroe Eskew and Yair Hayut, Dense ideals, Main Theorem,
arXiv:2410.14359 (submitted 2024).
- Matthew Foreman and András Hajnal, *A partition relation for successors
of Large Cardinals*, Math. Ann. 325 (2003), 583–623,
Scope warning (a). This settles the displayed consistency clause only
relative to a huge cardinal. If “consistent” is intended to demand
\(\operatorname{Con}(\mathsf{ZFC})\Rightarrow \operatorname{Con}(\mathsf{ZFC}+\mathsf{GCH}+\cdots)\), Proposition 2 does
not supply that sharper lower-assumption result.
(b), historical context. Laver's 1982 saturated-ideal construction was
the first large-cardinal relative consistency result in this direction;
Hajnal and Larson's handbook chapter records the consequence
\(\omega_2\to(\omega_1\cdot2+1,\alpha)^2\) for all
\(\alpha<\omega_2\). Foreman–Hajnal increased the fixed first goal to
\(\omega_1^2+1\). See Richard Laver,
[*An \((\aleph_2,\aleph_2,\aleph_0)\)-saturated ideal on
\(\omega_1\)*](https://doi.org/10.1016/S0049-237X(09)70510-5), Logic
Colloquium '80 (1982), 173–180, and Hajnal–Larson,
§4.5. This history also appears as the known-results note on Erdős problem
1170. The explicit GCH route in Proposition 2 uses Eskew–Hayut instead.
4. Exact frontier for the second GCH clause
Let
\[ \lambda=(2^{<\kappa})^+. \](b). Baumgartner, Hajnal and Todorčević (BHT) prove:
\[ \tag{BHT 3.1} \lambda\to(\kappa+\xi)^2_k \quad(k<\omega,\ \xi<\log\kappa), \]and
\[ \tag{BHT 4.1} \lambda\to \bigl(\kappa^{\omega+2}+1,(\kappa+n)_k\bigr)^2 \quad(n,k<\omega). \](d), source-verified. Their source explicitly lists
\[ \omega_3\to(\omega_2+\omega_1,\omega_2+\omega)^2 \]among the open GCH questions. The exact source is James E. Baumgartner,
András Hajnal and Stevo Todorčević,
Extensions of the Erdős–Rado Theorem,
Theorems 3.1 and 4.1.
(a). Under GCH at \(\kappa=\omega_2\),
\[ 2^{<\omega_2}=\omega_2,\qquad \log\omega_2=\omega_1,\qquad \lambda=\omega_3. \]Consequently:
- (b) for every \(\xi<\omega_1\),
\[ \omega_3\to(\omega_2+\xi)^2_2; \]
- (b) for every finite \(n\),
\[ \omega_3\to (\omega_2+\omega_1,\omega_2+n)^2. \]
The latter follows from BHT 4.1 with \(k=1\), because
\[ \omega_2+\omega_1 <\omega_2^2 <\omega_2^{\omega+2}+1. \]
(b)/(a). Thus the desired relation simultaneously asks for the limit of the
countable red tails in the first family and the limit of the finite blue
tails in the second family. Neither theorem supplies that simultaneous
limit.
A precise tree reduction
Fix \(c:[\omega_3]^2\to2\) with no blue set of type
\(\omega_2+\omega\). Define a tree \(T_c\) of height \(\omega_1\). Its
level \(\xi\) consists of all increasing maps
\[ t:\omega_2+\xi\longrightarrow\omega_3 \]whose ranges are red-homogeneous; order the maps by extension.
Lemma 3 (b). Every level of \(T_c\) is nonempty.
Proof. If \(\omega\leq\xi<\omega_1\), BHT 3.1 supplies a homogeneous
copy of \(\omega_2+\xi\). A blue copy would contain a blue initial suborder
of type \(\omega_2+\omega\), contrary to the choice of \(c\), so it is red.
For \(\xi<\omega\), restrict a red node from level \(\omega\). \(\square\)
Lemma 4 (a). For such a colouring \(c\), there is a red set of type
\(\omega_2+\omega_1\) if and only if \(T_c\) has a cofinal branch.
Proof. A red increasing enumeration of
\(\omega_2+\omega_1\) restricts to a branch. Conversely, the union of a
cofinal branch is red and has domain
\[ \bigcup_{\xi<\omega_1}(\omega_2+\xi) =\omega_2+\omega_1 \]by continuity of ordinal addition in its right argument. \(\square\)
Therefore:
Exact reduction (b).
\[ \omega_3\to(\omega_2+\omega_1,\omega_2+\omega)^2 \]under GCH is equivalent to the assertion that every \(T_c\) constructed
above from a colouring with no blue \(\omega_2+\omega\) has a cofinal
branch.
(c), structural diagnosis. Levelwise nonemptiness alone has no general
branch compactness principle at height \(\omega_1\). A successful proof must
extract additional coherence from the fact that the nodes are homogeneous
enumerations for one common colouring. The missing lemma is precisely:
> Every colouring-generated tree \(T_c\) above has a cofinal branch.
(d), search result only. No such coherence lemma was found in the checked sources.
5. Exact frontier for the third GCH clause
Put
\[ \rho=\omega_1^{\omega+2}. \](b). Under GCH, BHT 4.1 at \(\kappa=\omega_1\), \(n=2\), \(k=1\) gives the exact
neighbour
\[ \tag{1} \omega_2\to(\rho+1,\omega_1+2)^2. \]The requested relation is
\[ \tag{2} \omega_2\to(\rho+2,\omega_1+2)^2. \]Lemma 5 (a). For a colouring with no blue copy of
\(\omega_1+2\), (2) holds exactly when one can choose a red set \(H\) of
type \(\rho+1\) and a point \(y>\sup H\) such that every edge from \(y\) to
\(H\) is red.
Proof. Such \(H\cup\{y\}\) has red order type \(\rho+2\).
Conversely, remove the last point from any red copy of \(\rho+2\).
\(\square\)(b), source-verified boundary. The conclusion of the BHT proof builds
\(\omega_1\) consecutive blocks of type
\(\omega_1^{\omega+1}\) and then adds one common point \(\pi(N)\):
\[ \omega_1^{\omega+1}\cdot\omega_1+1 =\omega_1^{\omega+2}+1. \](c), structural diagnosis. The existing proof therefore supplies one
cap. Reaching (2) requires a second point that is simultaneously red to all
blocks and to the first cap. The exact missing input is a two-cap (or
two-model coherence) strengthening of BHT Claim 4.4. Merely iterating the
printed one-cap conclusion is invalid because its stationary/model choices
need not remain coherent for a second cap.
6. Why the “all \(\xi<\omega_2\)” clause is still beyond these results
(b). Proposition 2 gives one uniform initial segment:
\[ \forall\xi\leq\omega_1^2+1\quad \omega_2\to(\xi)^2_2. \](a). Foreman–Hajnal cannot be shrunk to a symmetric goal
\(\xi>\omega_1^2+1\), because its first goal is fixed at
\(\omega_1^2+1\). Thus neither their theorem nor the Eskew–Hayut ideal
construction proves the requested statement for every
\(\xi<\omega_2\).
(c), exact missing uniformity. One needs, in a single GCH model, first
goals cofinal in \(\omega_2\) (or another theorem directly yielding the
symmetric arrows) while retaining every target \(\xi<\omega_2\). A list of
separate forcing models for bounded \(\xi\) would not establish the one-model
universal assertion.
7. Literature audit
The following items were checked rather than inferred from search snippets.
- (d) The 1974 Erdős–Hajnal scan contains the final consistency question
on p. 272.
- (d) The BHT TeX source contains Theorems 3.1 and 4.1, lists the second
and third live-page clauses verbatim among its open GCH problems, and ends
its Theorem 4.1 construction with the single point \(\pi(N)\).
- (d) The Foreman–Hajnal publisher abstract states the
\(\kappa^2+1\) theorem with hypotheses
\(\kappa^{<\kappa}=\kappa\) and a \(\kappa\)-dense ideal.
- (d) The Eskew–Hayut TeX source states the huge-cardinal relative Main
Theorem, says its ideals imply GCH, and concludes the relevant successor
ideal is dense.
- (d) Hajnal and Larson's Partition Relations, §4.5, records the Laver
and Foreman–Hajnal consistency frontiers and repeats the second clause as
a question.
(d), search limitation. Exact-formula searches across arXiv, publisher
indexes, and the live problem site did not locate a later primary source
settling the second clause, the \(+2\) third clause, or the universal
\(\xi<\omega_2\) clause. A search miss is not a theorem of nonexistence; the
live page's status remains the authoritative status used here.
8. Reproducible verification
(d). The standalone checker is
erdos1172_wave8h_reverify.py. It uses
only the Python standard library.
Run the full audit from the repository root:
python runs/erdos1172_wave8h_reverify.py --online --live-page
(d), reproduced on this VM. Observed output:
Symbolic side-condition audit: PASS
Finite arrow audit through K_6: PASS
BHT source SHA256: 36fc0417cc4e1d889167e26db9d1ca356265f129a54d637fb4a1628ec7c669db
Dense ideals source SHA256: 1e8f8c6ce153c38bf32bf20f1077b35b853cd221d768c34db1793028264af5b2
Erdos--Hajnal PDF SHA256: 5fe543a67751902b388e352996b13e979199ab243bcd4f52409589da30c19778
Hajnal--Larson PDF SHA256: 521d87f3e070b3f0bf65e7f7c7a005f02d50afd268b9360f1c08efe20be13338
Source-text audit: PASS
Bright Data live-page audit: PASS
ALL CHECKS PASSED
The checker independently:
- (a) verifies every ordinal comparison and GCH cardinal-index
substitution used above;
- (a) checks the arrow-shrinking certificates and confirms that the BHT
\(+1\) theorem cannot be shrunk to the requested \(+2\);
- (d) exhausts all \(2^{15}=32768\) two-colourings of \(K_6\), rebuilding
\(R(3,3)=6\) and downward arrow monotonicity as a finite semantics
regression test;
- (d) downloads and text-checks the BHT, Foreman–Hajnal,
Eskew–Hayut, and original Erdős–Hajnal sources, plus the
Hajnal–Larson handbook account; and
- (d) repeats the live status and exact-statement audit through Bright
Data.
(c), methodological wall. The finite \(K_6\) computation is a checker of the encoded arrow semantics,
not evidence for an uncountable partition relation. The named infinite
theorems remain explicit external inputs. There is no honest larger finite
enumeration, and hence no meaningful core-hour estimate, that decides the
remaining consistency/branch-coherence questions: the missing work is a
forcing or uncountable compactness theorem, not more brute force.
PARTIAL: Under GCH the first arrow follows from Erdős–Rado, and relative to a huge cardinal GCH is consistent with all symmetric arrows through \(\omega_1^2+1\); the other two GCH arrows and uniformity for every \(\xi<\omega_2\) remain at the exact branch/coherence gaps isolated above.