ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1172 · PARTIAL

Erdős problem 1172 — wave 8h

(d), recorded audit fact. Date of audit: 2026-07-28 UTC.

Outcome

\[ \mathsf{GCH}\quad\Longrightarrow\quad \omega_3\to(\omega_2,\omega_1+2)^2. \]

\[ \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)/(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:

(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: author-hosted scan.

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: primary scan. 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.

  1. (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. \]

  1. (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. \]

  1. (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:

arXiv:2410.14359 (submitted 2024).

of Large Cardinals*, Math. Ann. 325 (2003), 583–623, publisher page and abstract.

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\)70510-5), Logic Colloquium '80 (1982), 173–180, and Hajnal–Larson, Partition Relations, §4.5. This history also appears as the known-results note on Erdős problem

  1. 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:

\[ \omega_3\to(\omega_2+\xi)^2_2; \]

\[ \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.

on p. 272.

and third live-page clauses verbatim among its open GCH problems, and ends its Theorem 4.1 construction with the single point \(\pi(N)\).

\(\kappa^2+1\) theorem with hypotheses \(\kappa^{<\kappa}=\kappa\) and a \(\kappa\)-dense ideal.

Theorem, says its ideals imply GCH, and concludes the relevant successor ideal is dense.

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:

substitution used above;

\(+1\) theorem cannot be shrunk to the requested \(+2\);

\(R(3,3)=6\) and downward arrow monotonicity as a finite semantics regression test;

Eskew–Hayut, and original Erdős–Hajnal sources, plus the Hajnal–Larson handbook account; and

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.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger