Erdoes #501 - working report - Erdős Problem a Day

Erdős problem #501 — wave 9n report

Date of audit: 2026-07-28 UTC.

Claim labels used throughout:

(a) elementary-rigorous — a proof is given here from the definitions.
(b) rigorous-modulo-named-theorem — the exact theorem and a checked source are named.
(c) plausible/structural-unverified — including negative literature-search evidence and unreviewed comments.
(d) computational-only — exactly what was checked by a program, with no promotion to a theorem.

0. Mandatory live-page gate

(b) I fetched the live problem page and its oldest-first discussion thread through the Bright Data browser path on 2026-07-28. This was a live browser fetch, not the stale YAML.

(b) Verbatim live statement:

For every \(x\in\mathbb{R}\) let \(A_x\subset \mathbb{R}\) be a bounded set with outer measure \(<1\). Must there exist an infinite independent set, that is, some infinite \(X\subseteq\mathbb{R}\) such that \(x\not\in A_y\) for all \(x\neq y\in X\)?
If the sets \(A_x\) are closed and have measure \(<1\), then must there exist an independent set of size \(3\)?

(b) The live joint status is OPEN, with the page text “This is open, and cannot be resolved with a finite computation.” The page was last edited 2026-01-25. It says that no partial or complete solution is claimed in the comments. “Interested in collaborating” is None and “Currently working on this problem” is None. The other visible interest/difficulty/formalisation-work markers are also None. Thus the mandatory stop condition was not triggered.

(b) The known-results block on the live page says:

Erdős–Hajnal [ErHa60] proved arbitrarily large finite independent sets under the first hypotheses.
Gładysz [Gl62] proved a two-point independent set under the second hypotheses.
Hechler [He72] gave a negative answer to the first question assuming CH.
Newelski–Pawlikowski–Seredyński [NPS87] proved an infinite independent set when every \(A_x\) is closed of measure \(<1\), strongly answering the second question.

(c) I read all 11 displayed comments. Their assertions are user comments and the page explicitly warns that they are unverified:

| Date | User | Content relevant to the gate/state | |---|---|---| | 2025-08-30 | BorisAlexeev | Initially suggested NPS87 solved the first part and identified the likely Gładysz paper. | | 2025-08-30 | StijnC | Asked for Hechler’s paper and about the apparent conflict. | | 2025-08-31 | BorisAlexeev | Pointed to Komjáth’s Problem 38 and initially suspected a part-(A)/part-(C) mismatch. | | 2025-08-31 | Thomas Bloom | Corrected the record: NPS87 requires closed values, while Hechler does address part (C), the first question here, under CH. | | 2025-12-18 | jaehyeonseo | Reported a typo; the site says it was corrected. | | 2026-01-24 | JakeMallen | Suggested component statuses NOT PROVABLE and PROVED. | | 2026-01-25 | TerenceTao | Explained that the site takes the intersection of component statuses, leaving the joint status OPEN. | | 2026-01-25 | Thomas Bloom | Said the remaining issue is the first question without CH. | | 2026-05-29 | Sungchul Lee | Linked an unrefereed note proving the first part positively under a full extension of Lebesgue measure to all sets. | | 2026-05-29 | Nat Sothanaphan | Reported a nonexpert screening with no issue and described the resulting relative independence. | | 2026-06-01 | Sungchul Lee | Reported a v2 replacing the cited Fremlin/Kunen section inequality by a direct proof. |

1. Primary-source and current-literature audit

(b) The original 1961 source is available as Erdős, Some unsolved problems. On printed p. 243, item 9 states the bounded-outer-measure problem, records all finite \(k\), and asks for an infinite set; it then states the closed-measure question. I downloaded and text-extracted the scan. Its SHA-256 is 6f6dac75cb03edcaf1d7e13509ea9001937248cea1fd5e932b386a6a0a7a1007.

(b) The finite theorem is also the cited Erdős–Hajnal paper, Some remarks on set theory VIII, Michigan Math. J. 7 (1960), 187–191, DOI 10.1307/MMJ/1028998389. The 1961 primary source explicitly restates the theorem, so the claim does not depend only on modern metadata.

(b) Springer verifies S. Gładysz, Bemerkungen über die Unabhängigkeit der Punkte in Bezug auf mengenwertige Funktionen, Acta Math. Acad. Sci. Hungar. 13 (1962), 199–201, DOI 10.1007/BF02033638. The full text was paywalled in this audit. The two-point result is independently attributed to it in the introduction of NPS87, so I use the result only modulo that published attribution.

(b) The bibliographic record for S. H. Hechler, On two problems in combinatorial set theory, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 20 (1972), 429–431, MR0314628, exists. I did not locate an accessible primary scan. I therefore do not infer any finer theorem from its unavailable text. The CH counterexample needed here is reconstructed from scratch in §2, so its correctness does not rest on this access failure.

(b) I downloaded and read the official AMS PDF of Newelski–Pawlikowski–Seredyński, Infinite free set for small measure set mappings, Proc. AMS 100 (1987), 335–339, DOI 10.1090/S0002-9939-1987-0884475-3. Its Corollary 1 says exactly that a real-line map into closed sets of measure \(<1\) has an infinite free set. The PDF SHA-256 is 5315e3dff48957c7883fc788fc30c6d6f4e73138c82ba5e2999a0647be172aea.

(b) Péter Komjáth’s 2025 update The Erdős–Hajnal problem list exists in Bull. Symbolic Logic 31 (2025), 418–461 and its bibliography contains Hechler and NPS87. The publisher redirected full-PDF attempts to the abstract page, so I did not independently inspect its Problem 38 text. This is an explicit source miss, not a reconstructed summary.

(b) The May/June 2026 note linked in the live comments is Sungchul Lee’s GitHub preprint, audited at commit 9147918d42c905d9a8888fef746a13dde67f90e1. It is labelled “Preprint draft”, not a refereed publication. I read the June 1 TeX source; its SHA-256 is d26f033d6216475bf42fd4e65a4b11f849ac34f293a545600acb382a1d99264b. Its conditional proof is independently reconstructed in §3.

(b) For the null-initial-order ingredient below, Elekes–Steprāns, Set-theoretical problems concerning Hausdorff measures, Proc. AMS 147 (2019), 1709–1717, Definition 1.10 and Claim 1.12, explicitly record

\operatorname{add}(\mathcal I)=\operatorname{cov}(\mathcal I) \ \Longrightarrow\ (\ast)_{\mathcal I} \ \Longrightarrow\ \operatorname{cov}(\mathcal I)\leq\operatorname{non}(\mathcal I),

where \((\ast)_{\mathcal I}\) is an ordering of \(\mathbb R\) whose proper initial segments lie in \(\mathcal I\). I nevertheless prove the special well-ordered null-ideal instances needed here directly.

(c) Searches by the exact problem wording, Problem 38, all named authors, the cited titles, and the current comment’s full-measure-extension terminology found no refereed post-NPS87 resolution of the remaining ZFC component. This is only a documented search miss, not evidence that no such paper exists and not a novelty claim for §2.

2. Explicit counterexamples from null-initial well-orders

Let \(\mathcal N\) be the Lebesgue-null ideal and \(\mathfrak c=|\mathbb R|\). Define:

\begin{aligned} \operatorname{add}(\mathcal N) &=\min\{|\mathcal F|:\mathcal F\subseteq\mathcal N,\ \bigcup\mathcal F\notin\mathcal N\},\\ \operatorname{cov}(\mathcal N) &=\min\{|\mathcal F|:\mathcal F\subseteq\mathcal N,\ \bigcup\mathcal F=\mathbb R\},\\ \operatorname{non}(\mathcal N) &=\min\{|S|:S\subseteq\mathbb R,\ S\notin\mathcal N\}. \end{aligned}

Call NWO the assertion that there is a well-order \(\prec\) of \(\mathbb R\) for which every proper initial segment

I_y=\{x\in\mathbb R:x\prec y\}

is Lebesgue null.

The null-initial-order criterion

(a) Theorem. NWO gives an explicit negative answer to the first question. More precisely, for a witnessing well-order define

\boxed{\quad A_y=\{x\in\mathbb R:x\prec y\text{ and }|x|\leq |y|+1\}. \quad}

Then every \(A_y\) is bounded and has outer measure \(0<1\), but the family has no infinite independent set.

(a) Proof. The set \(A_y\) is contained both in \(I_y\) and in \([-(|y|+1),|y|+1]\). Thus it is bounded and, as a subset of a null set, has outer measure zero.

Suppose \(X\) were infinite and independent. Because \(\prec\) is a well-order, recursively taking the least remaining member of \(X\) produces

x_0\prec x_1\prec x_2\prec\cdots .

For \(i<j\), independence says \(x_i\notin A_{x_j}\). Since \(x_i\prec x_j\), the only possible reason is

\[ |x_i|>|x_j|+1. \]

In particular, \(|x_n|<|x_0|-n\). Choosing an integer \(n>|x_0|\) contradicts \(|x_n|\geq0\). \(\square\)

Two from-scratch sufficient hypotheses

(a) Corollary 1. If \(\operatorname{add}(\mathcal N)=\operatorname{cov}(\mathcal N)\), then NWO holds and the displayed family is a counterexample.

(a) Proof. Put

\(\kappa=\operatorname{add}(\mathcal N)=\operatorname{cov}(\mathcal N)\)

and choose a null cover \(\mathbb R=\bigcup_{\alpha<\kappa}N_\alpha\). Form disjoint layers

D_\alpha=N_\alpha\setminus\bigcup_{\beta<\alpha}N_\beta,

well-order each layer, and order all points lexicographically by layer and then by the layer order. A proper initial segment ending in \(D_\alpha\) is contained in \(\bigcup_{\beta\leq\alpha}N_\beta\). Since \(\alpha<\kappa\), this is a union of fewer than \(\operatorname{add}(\mathcal N)\) null sets and is null. \(\square\)

(a) Corollary 2. If \(\operatorname{non}(\mathcal N)=\mathfrak c\), then NWO holds and the displayed family is a counterexample.

(a) Proof. Well-order \(\mathbb R\) in order type the initial ordinal of cardinality \(\mathfrak c\). Every proper initial segment has cardinality \(<\mathfrak c=\operatorname{non}(\mathcal N)\), so it is null. \(\square\)

(a) CH is recovered as a special case of Corollary 2: under CH every proper initial segment of an \(\omega_1\)-enumeration is countable and hence null. Thus the construction also independently verifies the page’s stated CH counterexample.

A necessary condition for this method

(a) Proposition. NWO implies

\operatorname{cov}(\mathcal N)\leq\operatorname{non}(\mathcal N).

(a) Proof. Let \(S\subseteq\mathbb R\) be nonnull with \(|S|=\operatorname{non}(\mathcal N)\). It must be cofinal in \(\prec\); otherwise it is contained in one null proper initial segment. The null sets \(\{I_s\cup\{s\}:s\in S\}\) cover \(\mathbb R\), so their number bounds \(\operatorname{cov}(\mathcal N)\). \(\square\)

(a) Exact reduction obtained. The counterexample problem is therefore reduced to a familiar set-theoretic object:

\boxed{ \text{null proper initial segments} \quad\Longrightarrow\quad \text{an explicit bounded outer-null family with no infinite free set}. }

The implication is available at least under either \(\operatorname{add}(\mathcal N)=\operatorname{cov}(\mathcal N)\) or \(\operatorname{non}(\mathcal N)=\mathfrak c\), while \(\operatorname{non}(\mathcal N)<\operatorname{cov}(\mathcal N)\) rules this method out.

(c) I did not find this explicit application of a null-initial order to problem #501 in the searched sources. Elekes–Steprāns supply the general ideal-order fact, and Lee’s appendix contains the CH specialization, so no claim of novelty is made.

3. Audit of the positive full-measure-extension direction

Let FMEA assert that Lebesgue measure \(m\) extends to a countably additive measure \(\nu:\mathcal P(\mathbb R)\to[0,\infty]\).

(a) Conditional theorem. Under FMEA, every family \((A_y)_{y\in\mathbb R}\) satisfying \(m^*(A_y)<1\) has an infinite independent set. Boundedness is not needed.

Here is a self-contained reconstruction of the preprint’s argument.

(a) Domination. For every \(S\subseteq\mathbb R\), \(\nu(S)\leq m^*(S)\): cover \(S\) by open intervals, use countable additivity and agreement with Lebesgue measure, then take the infimum.

For \(x\in\mathbb R\), put

B_x=\{y:x\in A_y\}.

(a) Section inequality. If \((Y,\mathcal P(Y),\nu)\) is \(\sigma\)-finite and \(H\subseteq\mathbb R\times Y\), then

\overline{\int_{\mathbb R}}\nu(H_x)\,dm(x) \leq \int_Ym^*(H^y)\,d\nu(y). \tag{1}

To prove this, choose a positive measurable \(\eta\) with \(\int\eta\,d\nu\leq1\). Given \(\varepsilon>0\), for each \(y\) choose an open \(U_y\supseteq H^y\) with

m(U_y)\leq m^*(H^y)+\varepsilon\eta(y).

For a countable rational-interval base \((J_n)\), let \(Y_n=\{y:J_n\subseteq U_y\}\) and \(E=\bigcup_n(J_n\times Y_n)\). Every \(Y_n\) is measurable because the \(\sigma\)-algebra is \(\mathcal P(Y)\); \(E\) is product-measurable, \(H\subseteq E\), and \(E^y=U_y\). Tonelli gives

\int_{\mathbb R}\nu(E_x)\,dm(x) =\int_Ym(U_y)\,d\nu(y) \leq\int_Ym^*(H^y)\,d\nu(y)+\varepsilon.

The measurable function \(x\mapsto\nu(E_x)\) majorizes \(x\mapsto\nu(H_x)\), so the definition of upper integral and \(\varepsilon\downarrow0\) give (1).

(a) Selection lemma. If \(\nu(C)=\infty\), then some \(x\in C\) satisfies

\nu(C\setminus B_x)=\infty. \tag{2}

Suppose instead that this measure is finite for every \(x\in C\). Choose a bounded \(D=C\cap[-N,N]\) with \(\nu(D)>1\), then choose \(k\) for which

D_k=\{x\in D:\nu(C\setminus B_x)\leq k\} \quad\text{satisfies}\quad \nu(D_k)>1.

Domination gives \(1<m^*(D_k)<\infty\). For \(C_M=C\cap[-M,M]\), choose \(M\) so large that, writing \(V=\nu(C_M)\),

V>\frac{k\,m^*(D_k)}{m^*(D_k)-1}. \tag{3}

Apply (1) to

H=\{(x,y)\in D_k\times C_M:x\in A_y\}.

For \(x\in D_k\), its horizontal section has measure

\nu(H_x)=\nu(B_x\cap C_M)\geq V-k,

so the left side of (1) is at least \((V-k)m^*(D_k)\). For \(y\in C_M\), \(H^y\subseteq A_y\), while outside \(C_M\) the section is empty; hence the right side is at most \(V\). Thus \((V-k)m^*(D_k)\leq V\), contradicting (3). This proves (2).

(a) Recursion. Starting with \(C_\varnothing=\mathbb R\), after choosing \(x_0,\ldots,x_{n-1}\), let

C_n=\mathbb R\setminus \bigcup_{i<n}\bigl(A_{x_i}\cup B_{x_i}\cup\{x_i\}\bigr).

Inductively \(\nu(C_n)=\infty\). Choose \(x_n\in C_n\) using (2) so that \(\nu(C_n\setminus B_{x_n})=\infty\); deleting \(A_{x_n}\) and the singleton \(\{x_n\}\), whose total measure is finite, leaves \(\nu(C_{n+1})=\infty\). The simultaneous deletion of \(A_{x_i}\) and \(B_{x_i}\) makes \(\{x_n:n<\omega\}\) independent.

(d) Formalisation check. In the pinned Lee repository I ran:

lake exe cache get
lake build

The build completed successfully with 8260 jobs and checked:

Erdos501.fmea_implies_StrongP : FMEA → StrongP
Erdos501.fmea_implies_P       : FMEA → P
Erdos501.ch_implies_not_P     : CH → ¬P

This verifies elaboration of the formalised definitions and theorems at that commit; it is not peer review and does not verify bibliographic or metamathematical claims.

(b) Consistency calibration. Fremlin’s Real-valued-measurable cardinals, 1D(e), proves that a countably additive extension of Lebesgue measure to all subsets of \(\mathbb R\) exists iff there is an atomlessly measurable cardinal. Its 2E gives the equiconsistency of atomlessly measurable, real-valued-measurable, and two-valued measurable cardinals. Carlson’s 1984 paper Extending Lebesgue measure by infinitely many sets also explicitly records Solovay’s equiconsistency statement. Consequently, modulo Solovay’s named consistency theorem, a measurable cardinal’s consistency gives models of the positive FMEA direction.

(b) Combining that positive model with the CH counterexample gives relative independence of the first assertion from ZFC, conditional on the consistency of a measurable cardinal: FMEA supplies the positive model, while Gödel’s constructible-universe relative-consistency theorem supplies a CH model in which the explicit counterexample gives the negative assertion. This does not authorize marking the live problem solved: the only current proof located is an unrefereed draft, and the authoritative page remains OPEN with zero claimed solutions.

(a) New compatibility consequence. The proved implications in §2 and the conditional FMEA theorem force, in every FMEA model,

\operatorname{add}(\mathcal N)<\operatorname{cov}(\mathcal N) \quad\text{and}\quad \operatorname{non}(\mathcal N)<\mathfrak c.

Indeed, equality in the first pair or in the second pair would produce the explicit counterexample of §2, contradicting the FMEA construction of an infinite independent set.

4. Standalone finite re-verification

The checker is erdos501_wave9n_verify.py. It uses only the Python standard library.

(d) For a finite ordered set with integer “heights” \(h_i\), it constructs

A_j=\{i<j:h_i\leq h_j+1\}.

It then computes the largest free set in two independent ways:

explicit construction of every \(A_j\) as a bit mask followed by enumeration of every subset;
a dynamic program for the longest subsequence satisfying \(h_i>h_j+1\) at each later selected index.

It also checks every ordered pair of the returned witness and the rigorous finite height bound

|X|\leq\left\lfloor\frac{\max_i h_i}{2}\right\rfloor+1.

Running

python3 runs/erdos501_wave9n_verify.py

took about 5.1 seconds and produced:

gap=1; heights=0..4; exhaustive words
n | words | distribution of maximum free-set size
1 | 5 | 1:5
2 | 25 | 1:19, 2:6
3 | 125 | 1:63, 2:61, 3:1
4 | 625 | 1:192, 2:416, 3:17
5 | 3125 | 1:552, 2:2392, 3:181
6 | 15625 | 1:1520, 2:12560, 3:1545
7 | 78125 | 1:4048, 2:62512, 3:11565
total words checked: 97655
ALL CHECKS PASSED

(d) This checks the descent mechanism and its sharp three-level example \((4,2,0)\); it does not test nullity, FMEA, a forcing model, or the infinite conclusion.

5. Exact remaining wall

(b) The second displayed question is already stronger-than-affirmatively answered by NPS87, as the live page and the paper’s Corollary 1 say.

(a) For the first question, §2 supplies an explicit counterexample from NWO and constructs NWO under two concrete cardinal-invariant regimes. It also identifies a hard obstruction to that method: when \(\operatorname{non}(\mathcal N)<\operatorname{cov}(\mathcal N)\), no null-initial well-order can exist.

(c) In the intermediate regimes

\operatorname{cov}(\mathcal N)\leq\operatorname{non}(\mathcal N),\qquad \operatorname{add}(\mathcal N)<\operatorname{cov}(\mathcal N),\qquad \operatorname{non}(\mathcal N)<\mathfrak c,

the arguments here neither construct NWO nor prove it impossible. The exact missing lemma for extending this attack is a weaker hypothesis sufficient to build a well-order whose relevant bounded initial pieces have outer measure \(<1\), or a different potential forcing every free sequence to descend.

(c) No larger finite search can settle that missing lemma: its content is the existence of a well-order of all reals with a null-ideal property, and the relevant cardinal invariants vary between set-theoretic models without changing the finite descent calculation. Thus heavier enumeration is the wrong resource rather than merely an expensive one. The meaningful next work is forcing/model analysis of the null-initial-order property, not core-hours of enumeration.

PARTIAL: A null-initial well-order gives an explicit counterexample, so the first question is negative under add(N)=cov(N) or non(N)=c; the live joint problem remains OPEN.

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