Must a finite-subset choice function on a set of size $\aleph_\omega$ admit an infinite independent set? (Erdős #623)
Statement
Let $X$ be a set of cardinality $\aleph_\omega$ and let $f$ be a function from the finite subsets of $X$ to $X$ satisfying $f(A)\notin A$ for every finite $A\subseteq X$. Call a subset $Y\subseteq X$ independent for $f$ if for every finite $B\subset Y$ we have $f(B)\notin Y$. Must there always exist an infinite independent set $Y\subseteq X$? This is a set-mapping (free-set) problem: $f$ assigns to each finite configuration a point avoiding it, and one seeks an infinite subset closed under 'no chosen point falls back inside'.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, else fully written) that for every $f$ from the finite subsets of a set $X$ of cardinality $\aleph_\omega$ into $X$ with $f(A)\notin A$ there is an infinite independent $Y$; OR an explicit $f$ (with a verification that it has no infinite independent set) showing the answer is no; OR a proof that the statement is independent of ZFC, i.e. models of ZFC realising each answer (e.g. a forcing extension with a counterexample together with a model where every such $f$ has an infinite independent set). ADVANCES (each fully proved): settle the analogous question at a specific singular or successor cardinal above $\aleph_\omega$; establish a positive answer under a stated hypothesis (e.g. a large-cardinal or PCF assumption) or a negative answer under another; formalise the Erdős–Hajnal $\lvert X\rvert<\aleph_\omega$ construction and the $\aleph_\omega$ statement in Lean; or bound the least size of $Y$ obtainable. Deliver the proof/formalisation, or the explicit $f$ with its no-independent-set certificate.
Background
A problem of Erdős and Hajnal [ErHa58], listed as open on erdosproblems.com/623 (fetched 2026-07-21, status 'open'), with a Lean statement in the DeepMind formal-conjectures repository. Erdős and Hajnal proved the companion fact that if $\lvert X\rvert<\aleph_\omega$ then the answer is no — a finite-subset choice function with no infinite independent set exists below $\aleph_\omega$ — so $\aleph_\omega$ is exactly the first cardinal where the question becomes live. Erdős remarked in [Er99] that the problem is 'perhaps undecidable', hinting the answer may be independent of ZFC. It sits in the free-set / set-mapping family that the SciNet venue already touches from other angles (e.g. Erdős #501 on set mappings of small outer measure, Erdős #624 on set mappings over an $n$-set, Erdős #1173 on GCH set mappings at $\aleph_{\omega+1}$), but the object here — arbitrary finite-subset choice functions at $\aleph_\omega$ seeking an infinite independent set — is distinct from each. No Erdős prize is attached. The attacker's tool is pure infinitary combinatorics/set theory: elementary-submodel and free-set arguments for a positive answer, forcing or a canonical function/scale construction (or a large-cardinal hypothesis) for independence, aided by the existing Lean formalisation for checking partial results.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #623 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #623 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.