Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 623

claims/: The 2 claim pages of Problem 623, one per claimant's result; the problem's standing derives from them.

Statement. Let $X$ be a set of cardinality $\aleph_\omega$ and $f$ be a function from the finite subsets of $X$ to $X$ such that $f(A)\not\in A$ for all $A$ . Must there exist an infinite $Y\subseteq X$ that is independent - that is, for all finite $B\subset Y$ we have $f(B)\not\in Y$ ?

Status. Open. The site's label is OPEN; the results claimed against the problem are recorded on the claim pages, and the standing in the frontmatter is derived from them.

Source. erdosproblems.com/623, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #623, https://www.erdosproblems.com/623.

References.

[Er99] Erdős, Paul, A selection of problems and results in combinatorics. Combin. Probab. Comput. (1999), 1-6.
[ErHa58] Erdős, P. and Hajnal, A., On the structure of set mappings. Acta Math. Acad. Sci. Hungar. 9 (1958), 111-131.

Formalization. Statement only. The file ErdosProblems/623.lean of formal-conjectures, at the commit linked, declares erdos_623 under category research open with answer(sorry) and no formal_proof attribute; a statement file is not a formalization link, and nothing was built here.

Current assessment

Scope. This assessment rests on the site's problem page, proof-claims tab and discussion thread, the statement file of formal-conjectures at the commit linked above, the library cards of Koepke's 1984 paper and Lee's manuscript, and the proof-claims tab's summary of Crawford's note, whose text is not covered. No literature search beyond the site was made, and the proof coverage of neither claimed argument was assessed.

Claims. Two results are claimed from outside the project, neither accepted by the site, which keeps the label OPEN. Lee's independence result (manuscript dated 2026-06-04, found with GPT-5.5 Pro) asserts that the positive answer is equiconsistent with a measurable cardinal and the negative answer with ZFC, through the equivalence of the problem with Koepke's free-subset property $\mathrm{Fr}_\omega(\aleph_\omega,\omega)$ ; three commenters in the site's thread endorsed it, which is not an acceptance, and the claim stays claimed, so the problem's standing is claimed with the claim independent. Crawford's consistency proof (2026-08-21) is a partial claim covering the measurable-cardinal half, that a positive answer cannot be refuted in ZFC, assuming ZFC plus a measurable cardinal is consistent. A thread comment of 2026-04-25 by Ritvik Nayak reports a partial reduction, that a counterexample must have a fiber of size $\aleph_\omega$ ; it is a thread post without a manuscript and has no claim page.

Known Results

Erdős and Hajnal [ErHa58] proved that the answer is no when $|X|<\aleph_\omega$ , and Erdős [Er99] suggested that the $\aleph_\omega$ case might be undecidable, as the site's commentary records. Koepke's 1984 theorem, on the Koepke card, makes the free-subset property $\mathrm{Fr}_\omega(\aleph_\omega,\omega)$ equiconsistent with a measurable cardinal. The claimed results are on the claim pages: Lee's independence result, which reduces the problem to that property and so claims exactly the undecidability Erdős suggested, and Crawford's partial claim, a consistency proof of the positive answer from a measurable cardinal that its author describes as similar to Lee's but found independently. Neither is accepted by the site.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (16)

Lee's independence through the free-subset property Crawford's consistency of a positive answer from a measurable problems/set_theory/E0623/claims Set Theory and Infinite Combinatorics set_theory/erdos_1958_structure_set_mappings Problem 1: an infinite free set at aleph_omega Theorem 2: no infinite free set below aleph_omega set_theory/koepke_1984_consistency_strength_free_subset_property_omega Theorem 2.2: the free-subset property for ω_ω gives an inner model with a measurable cardinal Theorem 4.4: from a measurable cardinal, a forcing extension satisfies the free-subset property for ω_ω Lee: Erdős Problem 623 and the free-subset property Corollary 5.1: Problem 623 is equivalent in ZFC to Koepke's free-subset property Proposition 2.2: Problem 623 restated as the free-set property FS_1 Proposition 3.1: singleton forbidden sets give countable ones Proposition 4.3: free-set property equals Koepke's free-subset property Theorem 1.1: both answers to Problem 623 are consistent, at different strengths

Graph