Erdős Problem #623

Erdős problem #623 · erdosproblems.com/623

Let $X$ be a set of cardinality $\aleph_\omega$ and $f$ 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 independent $Y\subseteq X$, i.e. with $f(B)\not\in Y$ for all finite $B\subset Y$? Claimed resolution: the positive assertion is equivalent to Koepke's free-subset property, hence independent of ZFC, with consistency strength exactly a measurable cardinal.

Result

Proved(see note)

Status

Candidate (review pending)

AI contribution

AI co-developed

Method

Argument

Field

Set Theory, Infinite Combinatorics

Posed by

Paul Erdős, András Hajnal

Year posed

1958

Years open

68y

Solved

2026-06-04

Model

GPT-5.5 Pro

Vendor

OpenAI

Collaborators

Sungchul Lee

Verification

Unreviewed

Publication

Announced

Significance

10 / 100*

Disclosed cost

—

Wikipedia

No dedicated article