GCH set mappings on $\aleph_{\omega+1}$ with small intersections: is there a full-size free set? (Erdős #1173)
Statement
Assume the generalised continuum hypothesis (GCH). Let$$f: \omega_{\omega+1}\to [\omega_{\omega+1}]^{\leq \aleph_\omega}$$be a set mapping (so each $f(\alpha)$ is a subset of $\omega_{\omega+1}$ of cardinality at most $\aleph_\omega$) such that$$\lvert f(\alpha)\cap f(\beta)\rvert <\aleph_\omega$$for all $\alpha\neq \beta$. Must there exist a free set of cardinality $\aleph_{\omega+1}$ — a set $X\subseteq \omega_{\omega+1}$ with $\lvert X\rvert = \aleph_{\omega+1}$ such that $\alpha\notin f(\beta)$ for all distinct $\alpha,\beta\in X$?
Acceptance. FULLY RESOLVES: assuming GCH, either (a) prove that every set mapping $f:\omega_{\omega+1}\to[\omega_{\omega+1}]^{\leq\aleph_\omega}$ with pairwise intersections of size $<\aleph_\omega$ admits a free set of cardinality $\aleph_{\omega+1}$, or (b) construct (under GCH, or show consistent with ZFC+GCH via forcing/inner models, with the metatheory explicit) such a set mapping with no free set of cardinality $\aleph_{\omega+1}$. An independence proof — models of ZFC+GCH deciding it each way — also fully resolves. Machine-checkable (Lean/Coq) proof preferred, else a complete written proof; a computation cannot contribute to closure. ADVANCES: prove the existence of free sets of intermediate cardinality (e.g. $\aleph_\omega$ or every $\aleph_n$) under the stated hypotheses; settle the analogous question at a smaller successor-of-singular test case or under stronger hypotheses (e.g. intersections uniformly bounded below $\aleph_\omega$, or $\square_{\aleph_\omega}$-type principles); or prove the question equivalent to a known PCF or square-principle statement. Deliver the proof file or Lean sources, with all set-theoretic assumptions explicit.
Background
A problem of Erdős and Hajnal, catalogued as Problem 7.88 in [Va99] and as Problem 35 in Komjáth's 2025 problem collection [Ko25b]; listed as open on erdosproblems.com/1173 (fetched 2026-07-13, status 'open'), with no partial progress recorded there. It probes the boundary case of the Erdős–Hajnal theory of set mappings and free sets. Hajnal's classical free-set theorem gives a free set of full cardinality $\kappa$ whenever $f:\kappa\to[\kappa]^{<\lambda}$ with $\lambda<\kappa$; here $\kappa=\aleph_{\omega+1}=\aleph_\omega^+$ while the images may have size $\aleph_\omega$, so the theorem does not apply — and without an extra hypothesis the answer is simply no: since every ordinal below $\omega_{\omega+1}$ has cardinality at most $\aleph_\omega$, the predecessor map $f(\alpha)=\{\beta:\beta<\alpha\}$ is a legal set mapping with no free pair at all. That example has pairwise intersections of size $\aleph_\omega$, which is exactly what the added condition $\lvert f(\alpha)\cap f(\beta)\rvert<\aleph_\omega$ forbids; the problem asks whether this small-intersection hypothesis, together with GCH, restores a free set of full size $\aleph_{\omega+1}$. The successor-of-a-singular cardinal $\aleph_{\omega+1}$ is the canonically hard case in this theory (PCF-adjacent territory), which is why it is singled out. The attacker's tool: pure infinitary combinatorics — elementary submodels, Fodor/pressing-down arguments, PCF-style scales for the positive direction, or a GCH-consistent (or ZFC+GCH) construction of a counterexample set mapping; there is no computational purchase.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1173 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.