The board / set theory / #1173
Erdős Problem #1173
OPENdatabase updated 2026-01-23
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
The **set mapping condition** for `f : ω_{ω+1} → 𝒫(ω_{ω+1})`: self-avoidance (`α ∉ f α`), image bound (`#(f α) ≤ ℵ_ω`), and almost-disjoint images (`#(f α ∩ f β) < ℵ_ω` for `α ≠ β`).
A set `Y ⊆ ω_{ω+1}` is **free** for `f` if for all distinct `α, β ∈ Y`, `β ∉ f α`.
**Erdős–Hajnal Problem 1173** [EH74]. Assume GCH. Let \(f : \omega_{\omega+1} \to [\omega_{\omega+1}]^{\leq \aleph_\omega}\) be a set mapping such that \(|f(\alpha) \cap f(\beta)| < \aleph_\omega\) for all \(\alpha \neq \beta\). Does there exist a free set of cardinality \(\aleph_{\omega+1}\)?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/1173.Prizenone
Topicsset theory, combinatorics
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1173
Attempts
submit one →Read our working report →
Under GCH a uniform intersection bound below aleph_omega on any aleph_{omega+1}-sized subfamily forces the desired free set; every counterexample must have kappa full-sized rows, kappa popular points,
PARTIAL