Erdős problem 598 — live-page audit, relative consistency, and a sharper threshold reduction

Date: 2026-07-28 (UTC)

0. Mandatory live-page gate

I fetched the live page through the Bright Data browser route, not datacenter curl. I also opened the linked discussion thread and revision history.

Live URL: <https://www.erdosproblems.com/598>

The current page's statement, verbatim, is:

Let \(m\) be an infinite cardinal and \(\kappa\) be the successor cardinal of \(2^{\aleph_0}\). Can one colour the countable subsets of \(m\) using \(\kappa\) many colours so that every \(X\subseteq m\) with \(\lvert X\rvert=\kappa\) contains subsets of all possible colours?

Live status snapshot:

• status: OPEN;
• claimed proofs: 0;
• currently working: None;
• interested in collaborating: None;
• comments: 8;
• formalised statement: Yes;
• revision history shows the same statement in the current version and in the

2025-10-20 version.

Therefore the mandatory stop condition is not triggered.

What the eight comments say

The mathematical assertions in comments are expressly unverified by the site. Accordingly, this subsection records what is present on the page, not what has yet been accepted as correct. These are label (c) until independently checked below.

1. Zeraoulia Rafik, 2026-03-15. Gives the stationary-set colouring for

\(m=\kappa=(2^{\aleph_0})^+\): split \(E^\kappa_\omega\) into \(\kappa\) stationary pieces and colour by the piece containing the supremum.

1. Terence Tao, 2026-03-15. Links a ChatGPT review that reports a fixable

issue in that proof, says the case follows from work of Garti--Hayut, and identifies large \(m\) as the difficulty. It also links a DeepResearch review reporting expert belief in independence.

1. Przemek Chojecki, 2026-04-22. Links an AI-assisted note, *A Threshold

Consistency Theorem for Erdős Problem 598*, and a Lean file; says the result remains open in ZFC because large-cardinal hypotheses are used.

1. Nat Sothanaphan, 2026-04-22. Says the formalisation link is wrong.
2. Przemek Chojecki, 2026-04-22. Says it has been corrected.
3. Nat Sothanaphan, 2026-04-22. Reports citation issues and slight

mismatches between the Lean assumptions and the literature.

1. Nat Sothanaphan, 2026-05-30. Points out that the forcing-extension

theorem is not formalised: the linked file literally contains theorem threshold_model_description : True := trivial.

1. Fanxin Wu, 2026-06-07. Links the MathOverflow discussion and reports

relative independence: the positive answer in \(L\), and a relatively consistent negative answer from rank-into-rank strength; the exact strength is reported open and at least \(0^\sharp\).

I fetched the corrected Lean file and confirmed item 7 at lines 842--845. I also found one precise citation typo underlying item 6: the note/Lean comments cite Garti--Hayut Claim 1.3(c) for \(2^{\aleph_0}<\alpha_M\), but Claim 1.3(c) is \(\alpha_J\leq\alpha_M\); the continuum inequality is Claim 1.3(d) and is repeated in Corollary 1.6. This is a citation error, not a failure of that inequality.

Discussion URL: <https://www.erdosproblems.com/forum/thread/598>

1. Conventions and claim labels

For a set \(A\), let \([A]^\omega\) mean its countably infinite subsets. If "countable" on the live page is taken to include finite sets, every colouring below extends arbitrarily to the finite subsets, so nothing changes.

Write

when there is a map \(c:[A]^\omega\to\kappa\) such that

For a cardinal \(\lambda\), write \(\operatorname{Col}_\omega(\lambda,\kappa)\) for any set of size \(\lambda\). In square-bracket partition notation this is

Claim labels used below:

• (a) elementary-rigorous: proved in this report from elementary set/cardinal

arguments;

• (b) rigorous-modulo-named-theorem: the reduction here is complete, with

an explicitly named external theorem as input;

• (c) plausible/structural-unverified: not used as a theorem;
• (d) computational-only: exhaustively checked only in the stated finite

range.

2. Primary-source audit

2.1 Original source

The live page identifies [Er87] as:

P. Erdős, “Some problems on finite and infinite graphs,” Logic and Combinatorics (Arcata, 1985), Contemporary Mathematics 65 (1987), 223--228, MR 891250.

I fetched the scan from Erdős's publication archive: <https://www.renyi.hu/~p_erdos/1987-28.pdf>. Problem 8 on printed pages 225--226 asks the same question and explicitly says “for every infinite \(m\).” Thus the universal quantifier over \(m\) is not an inference from the tracker metadata.

2.2 Magidor-cardinal inputs

I checked the full texts, not only search snippets, of:

1. S. Garti and Y. Hayut, “Magidor cardinals,” J. Math. Soc. Japan 70

(2018), 1--23, arXiv:1508.04903, <https://arxiv.org/abs/1508.04903>.

1. S. Garti and Y. Hayut, “The first omitting cardinal for Magidority,”

Math. Log. Quart. 65 (2019), 95--104, arXiv:1801.00239, <https://arxiv.org/abs/1801.00239>.

The first paper defines a Magidor cardinal by

defines the first omitting cardinal \(\alpha_M(\lambda)\), and proves in Claim 1.3(d) that

It also records that an \(I1\) embedding produces a Magidor cardinal.

The second paper's Claim 1.10(a) states that, from the stated large-cardinal assumptions, for every successor ordinal \(\beta\) one can force a Magidor \(\lambda\) with

Taking \(\beta=1\) gives \(\alpha_M(\lambda)=\aleph_2\).

These papers really exist, have the bibliographic data above, and contain the numbered assertions used here. The relative-consistency argument in Section 6 is label (b) because Claim 1.10 is a forcing theorem, not reproved here.

2.3 Current, problem-specific discussion

The May 2026 MathOverflow thread is: <https://mathoverflow.net/questions/511508/on-erd%C5%91s-problem-598>. Its answer gives the \(0^\sharp\) lower bound and the \(I1\) upper bound on consistency strength. The April 2026 note linked on the Erdős page is: <https://www.ulam.ai/research/erdos598.pdf>.

Exact-title, exact-statement, partition-notation, and Magidor-cardinal searches located no additional peer-reviewed paper devoted specifically to problem 598. This is a search result, not a proof of nonexistence, so it is label (c). The relevant peer-reviewed mathematical inputs I found are the two Garti--Hayut papers above.

3. Verified positive constructions

Throughout this section

In particular, \(\kappa\) is regular and uncountable.

3.1 The base case \(m=\kappa\)

Proposition 3.1 (b, modulo the Solovay--Ulam stationary splitting theorem). \(\operatorname{Col}_\omega(\kappa,\kappa)\) holds.

Proof. The set

is stationary. By stationary splitting, choose pairwise disjoint stationary sets \(S_\xi\), \(\xi<\kappa\), whose union is \(E^\kappa_\omega\). Define

The second line is the small totality repair missing from the March forum comment.

If \(X\in[\kappa]^\kappa\), regularity makes \(X\) unbounded. Its limit points form a club. For every \(\xi<\kappa\), choose a limit point \(\delta\in S_\xi\). Since \(\operatorname{cf}(\delta)=\omega\), there is a countably infinite \(a\subseteq X\cap\delta\) cofinal in \(\delta\). Then \(c(a)=\xi\). \(\square\)

3.2 Downward monotonicity

Lemma 3.2 (a). If \(A\) injects into \(B\) and \(\operatorname{Col}_\omega(B,\kappa)\), then \(\operatorname{Col}_\omega(A,\kappa)\). Consequently, failure is upward monotone in cardinality.

Proof. For an injection \(e:A\to B\) and a witness \(c\) on \(B\), set \(d(a)=c(e''a)\). If \(X\in[A]^\kappa\), then \(e''X\in[B]^\kappa\), and the desired equality of colour images follows. The failure statement is the contrapositive. \(\square\)

3.3 Disjoint-sum closure

The following is the “thick/thin” construction from the linked April note. It is included with a complete proof because it drives the new sharpening in Section 4.

Theorem 3.3 (a). Let \(I\) be a set and \(\langle A_i:i\in I\rangle\) be pairwise disjoint. If

then

Proof. Fix a witness \(d:[I]^\omega\to\kappa\), local witnesses \(c_i:[A_i]^\omega\to\kappa\), and a well-order of \(I\). For \(a\in[\bigsqcup_iA_i]^\omega\):

• if \(a\cap A_i\) is infinite for some \(i\), let \(i(a)\) be the least such

\(i\) and put \(c(a)=c_{i(a)}(a\cap A_{i(a)})\);

• otherwise every \(a\cap A_i\) is finite, so

\(\operatorname{supp}(a)=\{i:a\cap A_i\ne\varnothing\}\) is countably infinite; put \(c(a)=d(\operatorname{supp}(a))\).

Fix \(X\) of size \(\kappa\) and a colour \(\xi\).

If \(|X\cap A_i|=\kappa\) for some \(i\), use the local witness to take an \(a\in[X\cap A_i]^\omega\) of colour \(\xi\).

Otherwise every \(|X\cap A_i|<\kappa\). The set

has size at least \(\kappa\): if \(|I_X|<\kappa\), regularity of \(\kappa\) would make the union of the \(<\kappa\) many sets \(X\cap A_i\), each of size \(<\kappa\), have size \(<\kappa\). Choose \(Y\in[I_X]^\kappa\). The witness \(d\) supplies \(J\in[Y]^\omega\) with \(d(J)=\xi\). Pick one point \(x_j\in X\cap A_j\) for each \(j\in J\). Then \(a=\{x_j:j\in J\}\) is thin, has support \(J\), and has colour \(\xi\).

\(\square\)

3.4 Countable-product closure

Theorem 3.4 (a). Suppose \(\kappa\) is regular uncountable and

If \(\operatorname{Col}_\omega(A_n,\kappa)\) for every \(n<\omega\), then

Proof. Let \(\pi_n\) be the \(n\)-th projection and \(c_n\) a local witness. For a countably infinite \(a\) in the product, let \(n(a)\) be the least \(n\) for which \(\pi_n''a\) is infinite, if it exists, and set

Use colour \(0\) if no such coordinate exists.

Let \(X\) have size \(\kappa\). Some coordinate projection has size \(\kappa\). Otherwise regularity gives \(\mu=\sup_n|\pi_n''X|<\kappa\), while

a contradiction. Let \(n_*\) be the first coordinate whose projection has size \(\kappa\).

Partition \(X\) by equality of all coordinates below \(n_*\). There are \(<\kappa\) classes because this is a finite product of cardinals below \(\kappa\). Some class \(Y\) has \(|\pi_{n_*}''Y|=\kappa\); otherwise regularity would make the union of all those projections have size \(<\kappa\). For a prescribed \(\xi<\kappa\), choose \(b\in[\pi_{n_*}''Y]^\omega\) with \(c_{n_*}(b)=\xi\), and lift one point of \(Y\) over each member of \(b\). The resulting countable set has all earlier coordinates constant and \(n_*\)-th projection \(b\), hence its colour is \(\xi\). \(\square\)

For the present \(\kappa\), the cardinal-arithmetic hypothesis is automatic: if \(\mu<\kappa\), then \(\mu\leq2^{\aleph_0}\), so

Combining Proposition 3.1, Theorem 3.4, and downward monotonicity gives the known bound

This is label (a) apart from the stationary-splitting input in the base case.

4. New structural sharpening: the first bad cardinal is regular and

\(\aleph_0\)-closed

The linked April note proves only that a least counterexample \(\lambda_*\), if one exists, satisfies \(\operatorname{cf}(\lambda_*)>\kappa\) and \(\lambda_*>\kappa^\omega\). The two closure theorems above imply the strictly sharper conclusion below.

I did not find this sharper consequence stated in the note or the exact-search results. The proof is elementary; this is a statement about what was found, not a claim of publication priority.

Theorem 4.1 (a). Assume that failure occurs for some cardinal, and let

Then:

1. \(\lambda_*\) is a regular cardinal;
2. \(\lambda_*\) is \(\aleph_0\)-closed:

\[ \mu^\omega<\lambda_*\qquad\text{for every cardinal }\mu<\lambda_*; \]

1. in particular, \(\kappa^\omega<\lambda_*\);
2. by monotonicity,

\[ \operatorname{Col}_\omega(m,\kappa) \quad\Longleftrightarrow\quad m<\lambda_*. \]

Proof. Every cardinal below \(\lambda_*\) is good: this is vacuous below \(\kappa\) and follows from minimality from \(\kappa\) onward.

Suppose first that \(\lambda_*\) is singular. Write it as a disjoint union

with \(|A_i|<\lambda_*\). Every \(A_i\) is good by minimality. Also \(\theta<\lambda_*\), so the index set is good by minimality (or vacuously if \(\theta<\kappa\)). Theorem 3.3 makes their disjoint union good, a contradiction. Thus \(\lambda_*\) is regular.

Now fix \(\mu<\lambda_*\). The cardinal \(\mu\) is good. Apply Theorem 3.4 to the constant sequence \(A_n=\mu\); it follows that \(\mu^\omega\) is good. If \(\mu^\omega\geq\lambda_*\), upward monotonicity of failure would make \(\mu^\omega\) bad. Hence \(\mu^\omega<\lambda_*\). Proposition 3.1 shows \(\kappa<\lambda_*\), so taking \(\mu=\kappa\) gives item 3. Item 4 is minimality plus upward monotonicity. \(\square\)

This is the main new verifiable progress of this run. It replaces the cofinality lower bound \(\operatorname{cf}(\lambda_*)>\kappa\) by exact regularity and adds closure under all countable powers below the threshold.

5. The positive side: failure implies \(0^\sharp\)

This section independently fills in the reduction reported on MathOverflow.

Use the convention that

means every \(\kappa\)-colouring of the \(\tau\)-subsets has a \(\kappa\)-set omitting a colour. Thus this arrow is failure of the desired polychromatic colouring.

5.1 From countable subsets to finite subsets

Lemma 5.1 (a). For uncountable \(\kappa\),

Proof by contrapositive. Suppose \(g:[\lambda]^{<\omega}\to\kappa\) takes every colour on every \(\kappa\)-subset. Define \(F:[\lambda]^\omega\to\kappa\) as follows. If the order type of \(a\) is \(\omega+n\), let \(t(a)\) be its final \(n\) points and put \(F(a)=g(t(a))\); use a default colour on other order types.

Given \(X\in[\lambda]^\kappa\), let \(b\) be its first \(\omega\) points. The part of \(X\) strictly above \(\sup b\) still has size \(\kappa\). For any \(\xi<\kappa\), choose a finite \(t\) in that tail with \(g(t)=\xi\). Then \(b\cup t\) has order type \(\omega+|t|\) and \(F(b\cup t)=\xi\). Thus \(F\) is onto on every \(\kappa\)-subset.

\(\square\)

5.2 The elementary-submodel consequence

Lemma 5.2 (a, using standard Skolemisation). If \(\lambda\rightarrow[\kappa]^{<\omega}_\kappa\), then for every countable-language structure \((M,P,\ldots)\) with \(|M|=\lambda\) and \(|P|=\kappa\), there is \(N\prec M\) with

Proof. Identify the universe with the ordinal \(\lambda\), identify \(P\) with \(\kappa\), and Skolemise. Enumerate all Skolem-term schemes \(t_j\) (including substitutions/repetitions of variables), let \(r_j\) be the number of distinct increasing parameters used by \(t_j\), and choose distinct positive natural numbers \(N_j\geq r_j\).

Define a finite-set colouring \(g\) as follows. On a set \(s\) of size \(N_j\), evaluate \(t_j\) on the final \(r_j\) points of \(s\). If its value lies in \(P=\kappa\), use that value as the colour; otherwise use \(0\). Use \(0\) on unused sizes and on the empty set.

Take \(A\in[\lambda]^\kappa\) omitting some colour \(\xi\). Since \(0\) always occurs, \(\xi\ne0\). Let \(D\) be the first \(\omega\) points of \(A\), and let \(B\) be the size-\(\kappa\) tail above \(\sup D\). Every \(P\)-valued Skolem term on a finite tuple from \(B\) is the colour of a finite subset of \(A\): pad that tuple on the left by the required \(N_j-r_j\) points of \(D\). Therefore the Skolem hull \(N=\operatorname{Hull}(B)\) cannot contain the \(P\)-element indexed by \(\xi\). Skolem closure makes \(N\) elementary. There are only countably many terms and \(\kappa^{<\omega}=\kappa\), so \(|N|\leq\kappa\), while \(B\subseteq N\) gives \(|N|\geq\kappa\). Hence \(|N|=\kappa\). \(\square\)

5.3 Apply condensation

Theorem 5.3 (b, modulo the Condensation Lemma and Jech's \(0^\sharp\) embedding criterion). If the desired colouring fails for any \(\lambda\), then \(0^\sharp\) exists. Consequently, in every model with no \(0^\sharp\), in particular in \(V=L\), the answer to problem 598 is positive for every \(m\).

Proof. Failure is \(\lambda\rightarrow[\kappa]^\omega_\kappa\). Lemmas 5.1 and 5.2, applied to \((L_\lambda,\in,P=\kappa)\), give an elementary \(N\) of size \(\kappa\) with \(N\cap\kappa\ne\kappa\). By condensation, its transitive collapse is \(L_\alpha\) for an \(\alpha\) with \(|\alpha|=\kappa\). The inverse collapse

is elementary. Its critical point is below \(\kappa\): if it fixed every ordinal below \(\kappa\), then every such ordinal would lie in its range \(N\), contrary to \(N\cap\kappa\ne\kappa\). Since \(|\alpha|=\kappa>\operatorname{crit}(j)\), the standard initial-segment embedding criterion (Jech, Set Theory, third millennium edition, Theorem 18.27, in the numbering cited in the MathOverflow answer) yields \(0^\sharp\). \(\square\)

Thus the positive consistency side needs no large cardinal: if ZFC is consistent, its constructible model satisfies the universal positive answer. The assertion that failure implies \(0^\sharp\) is much stronger than merely saying that the base stationary construction works.

6. The negative side from \(I1\)

Theorem 6.1 (b, modulo Garti--Hayut Claim 1.10(a)). Assuming the consistency of the stated \(I1\) rank-into-rank hypothesis, it is consistent that problem 598 has a negative instance.

Proof. Use Garti--Hayut Claim 1.10(a) with \(\beta=1\) to obtain a forcing extension with a Magidor cardinal \(\lambda\) satisfying

By “Magidor cardinals,” Claim 1.3(d),

Cantor's theorem then forces \(2^{\aleph_0}=\aleph_1\), so the problem's \(\kappa=(2^{\aleph_0})^+\) is exactly \(\aleph_2=\alpha_M(\lambda)\).

Now take any \(c:[\lambda]^\omega\to\kappa\), and restrict it to bounded countable subsets. The definition of \(\alpha_M(\lambda)=\kappa\) gives an \(A\in[\lambda]^\lambda\) and a colour \(\xi<\kappa\) omitted on all bounded countable subsets of \(A\).

A Magidor cardinal has cofinality \(\omega\), while \(\kappa\) is regular. Fix an increasing cofinal sequence \(\langle\lambda_n:n<\omega\rangle\) in \(\lambda\). Some \(A\cap\lambda_n\) has size at least \(\kappa\); otherwise a countable union of sets of size \(<\kappa\) would have size \(<\kappa\), contradicting \(|A|=\lambda>\kappa\). Choose \(X\in[A\cap\lambda_n]^\kappa\). Every countable subset of \(X\) is bounded in \(\lambda\), so \(c''[X]^\omega\) omits \(\xi\). Therefore

which is a negative instance of the Erdős question. \(\square\)

Combining Theorems 5.3 and 6.1 gives the verified consistency-strength bracket

The exact strength between these bounds is not supplied by the sources I found.

7. Exact wall

The remaining obstruction is now precise.

1. A first counterexample cannot be singular: disjoint-sum closure would

assemble colourings below it.

1. It cannot be reached by a countable-power jump from below: it is

\(\aleph_0\)-closed.

1. At a regular \(\lambda_*>\kappa\), every \(\kappa\)-sized subset is

bounded in \(\lambda_*\). Therefore the successful base colouring by stationary pieces of the supremum at the top cardinal sees none of the relevant sets as unbounded.

1. The disjoint-sum construction at \(\lambda_*\) becomes circular: a

decomposition into \(\lambda_*\) small pieces requires a good colouring of the index set \(\lambda_*\), exactly the unknown assertion.

On the positive side, the missing lemma would be a coherent way to combine the good colourings on all proper initial segments of an arbitrary regular \(\aleph_0\)-closed \(\lambda\), without already assuming \(\operatorname{Col}_\omega(\lambda,\kappa)\). Square/quilshon-style coherence is the natural known mechanism, and strong large-cardinal models are precisely where such mechanisms can fail.

On the negative side, one needs to force or derive

from assumptions below \(I1\), or prove that doing so already has higher inner-model strength. The elementary-submodel reduction proves the lower bound \(0^\sharp\), but does not reverse it. This is the exact missing large-cardinal/forcing lemma; no feasible finite computation can decide it.

8. Standalone finite re-verification

File:

runs/erdos598_wavew000_reverify.py

The script defines the finite analogue \(P(n,k,r)\): the maximum number of colours on the \(r\)-subsets of an \(n\)-set such that every \(k\)-subset contains every colour. It exhaustively enumerates every labelled colouring in the decisive cases for \(P(n,3,2)\). This is label (d) and is not used as evidence for an infinite-cardinal theorem.

Run:

python runs/erdos598_wavew000_reverify.py

Verified exact table:

| \(n\) | \(P(n,3,2)\) | |---:|---:| | 3 | 3 | | 4 | 3 | | 5 | 2 | | 6 | 1 |

Decisive labelled-colouring counts:

| \((n,q)\) | valid colourings | |---:|---:| | \((3,3)\) | 6 | | \((4,3)\) | 6 | | \((5,3)\) | 0 | | \((5,2)\) | 12 | | \((6,2)\) | 0 |

The run completed in 0.13 seconds with all assertions passing. SHA-256 of the verifier at the time of this report:

4d0d9e912f46f37442c30bfe494ecbaba4953c425b98bf7dc626b3fba94fb2db

PARTIAL: Relative independence is verified modulo Garti--Hayut and Jech; additionally, any first bad cardinal is proved regular and \(\aleph_0\)-closed, sharpening the linked threshold note, while the exact consistency strength between \(0^\sharp\) and \(I1\) remains open.