Erdős Problem #623

Erdős Problem 623 --- ROUND-2

1) ROUND-2 OBJECTIVE

Path pursued: (C) obstruction / gap-isolation.

Round-1 identified the main obstacle in the naive recursion: when a new point $y_n$ is chosen, the values $f(B\cup\{y_n\})$ create uncontrolled future constraints. In this round I isolate the exact scope of that obstruction. I will prove that every such set-mapping on $\aleph_\omega$ has independent sets of every finite size. Hence any negative answer to Problem 623 must be a genuinely infinitary failure of compactness, not a finite obstruction.

2) Round-1 FOUNDATION USED

I use the following Round-1 results as fixed background:

• the formal restatement of the problem;
• the Round-1 observation that a direct stage-by-stage recursion toward an infinite independent set fails because values of the form $f(B\cup\{y_n\})$ are not locally controllable;
• the Round-1 reduction from strong closure-free principles to a positive answer, only as contextual background (not in the proof below).

3) NEW INSIGHT / TOOL (ROUND-2)

For a fixed finite target size $m$, I encode all values of $f$ on subsets of an $m$-set into a single finite-valued set-mapping \[ \Phi_m:[X]^m \to [X]^{<\omega},\qquad \Phi_m(A)=\{f(B):B\subseteq A\}. \] Kuratowski's free set theorem can then be applied to $\Phi_m$. This collapses all lower arities simultaneously and yields an $(m+1)$-element set $Z$ with the property that every proper subset of $Z$ already maps outside $Z$. Any $m$-subset of $Z$ is therefore independent for the original map $f$.

4) ATTACK PLAN (ROUND-2)

The exact gap left after Round-1 was this: we had no proof that finite independent sets exist at all sizes, so it was unclear whether the obstruction was already visible in finite combinatorics, or only at the infinite level.

The precise claim to prove now is: \[ \forall m\ge 1\ \exists Y\in [X]^m\ \forall B\subseteq Y,\qquad f(B)\notin Y. \]

If this succeeds, then the only remaining gap is the passage from "independent sets of every finite size" to "one infinite independent set," i.e. a pure compactness problem.

5) WORK (ROUND-2)

Theorem.

Let $X$ be a set of cardinality $\aleph_\omega$, and let $f:[X]^{<\omega}\to X$ satisfy $f(A)\notin A$ for every finite $A\subseteq X$. Then for every positive integer $m$ there exists an independent set $Y\subseteq X$ of size $m$.

Proof.

Fix $m\ge 1$. Define \[ \Phi_m:[X]^m\to [X]^{<\omega},\qquad \Phi_m(A):=\{f(B):B\subseteq A\}. \] Since $A$ is finite, $\Phi_m(A)$ is finite.

Now apply Kuratowski's free set theorem with $n=m$ and $\lambda=\aleph_0$: because $|X|=\aleph_\omega\ge \aleph_m$, every map from $[X]^m$ to finite subsets of $X$ has a free set of size $m+1$. Hence there exists $Z\in [X]^{m+1}$ such that \[ \forall A\in [Z]^m\qquad \Phi_m(A)\cap Z\subseteq A. \tag{$*$} \]

I claim that every proper subset $C\subsetneq Z$ satisfies \[ f(C)\notin Z. \tag{$**$} \]

Indeed, there are two cases.

Case 1: $|C|=m$. Then $C\in [Z]^m$, so by $(*)$ we have $\Phi_m(C)\cap Z\subseteq C$. Since $f(C)\in \Phi_m(C)$, this implies: if $f(C)\in Z$, then $f(C)\in C$. But the standing hypothesis on $f$ gives $f(C)\notin C$. Therefore $f(C)\notin Z$.

Case 2: $|C|<m$. Take any $z\in Z\setminus C$. Then $A_z:=Z\setminus\{z\}\in [Z]^m$ and $C\subseteq A_z$, hence $f(C)\in \Phi_m(A_z)$ by definition of $\Phi_m$. Applying $(*)$ to $A_z$, we get \[ \Phi_m(A_z)\cap Z\subseteq A_z=Z\setminus\{z\}, \] so $z\notin \Phi_m(A_z)$. Since $f(C)\in \Phi_m(A_z)$, it follows that $f(C)\neq z$.

Because $z\in Z\setminus C$ was arbitrary, we conclude that $f(C)\notin Z\setminus C$. Again, the hypothesis $f(C)\notin C$ shows $f(C)\notin Z$.

Thus $(**)$ holds for every proper subset $C\subsetneq Z$.

Now choose any $Y\in [Z]^m$. Let $B\subseteq Y$ be arbitrary. Because $|Z|=m+1$ and $|Y|=m$, every subset $B\subseteq Y$ is a proper subset of $Z$. Hence by $(**)$, \[ f(B)\notin Z, \] and therefore in particular $f(B)\notin Y$. So $Y$ is independent.

This proves the theorem. $\square$

Corollary.

If Problem 623 has a negative answer, then the obstruction is purely infinitary: for every $m<\omega$ there are independent sets of size $m$, but there is no infinite independent set.

6) ADVERSARIAL VERIFICATION

• Potential issue: does the proof handle the case $B=Y$? Yes. Since $Y$ has size $m$ and $Z$ has size $m+1$, the set $Y$ is a proper subset of $Z$, so $(**)$ applies directly and gives $f(Y)\notin Z$, hence $f(Y)\notin Y$.

• Potential issue: did Kuratowski's theorem apply to the correct arity? Yes. The map $\Phi_m$ is defined on $m$-element subsets, and the theorem gives a free set of size $m+1$ because $|X|=\aleph_\omega\ge \aleph_m$.

• Potential issue: could $\Phi_m(A)$ fail to be finite? No. Each $A$ has exactly $2^m$ subsets, so $\Phi_m(A)$ has size at most $2^m$.

• Interaction with Round-1. Round-1 isolated a recursion gap for building an infinite independent set. The theorem above shows that this gap cannot be repaired merely by improving finite-stage bookkeeping: all finite target sizes are always attainable. The unresolved difficulty is exactly the infinite compactness step.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict advance over Round-1 is the unconditional theorem that independent sets of every finite size always exist. So any counterexample to Problem 623 must have arbitrarily large finite independent sets and yet no infinite one. That sharply localizes the remaining obstruction to a genuinely infinitary compactness phenomenon.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 40%

9) REFERENCES

• T. F. Bloom, Erdős Problem #623, erdosproblems.com/623, accessed 2026-03-07.
• K. Kuratowski, Sur une caractérisation des alephs, Fund. Math. 38 $1951$, 14--17.

10) OUTPUT FORMAT

This section is written in drop-in LaTeX form and starts directly from \section{}, with no preamble.

OBJECTIVE AND SOURCE REVIEW

Erdős #623; independent attempt, 2026-09-23. For $|X|=\aleph_\omega$ and $f:[X]^{<\omega}\to X$ with $f(A)\notin A$, must there be an infinite $Y$ such that $f(B)\notin Y$ for every finite $B\subseteq Y$? I read the complete 623.tex. Its finite free-set argument does not automatically produce a compatible infinite sequence. I give an explicit smaller-cardinality model demonstrating the exact failure of that inference.

WORK: FINITE FREEDOM WITHOUT INFINITE FREEDOM

On $X=\mathbb N_0$, define \[ f(A)=\begin{cases}|A|,&|A|\notin A,\\ \min(\mathbb N_0\setminus A),&|A|\in A. \end{cases} \] This always lies outside $A$. For any fixed $r$, take $Y_r=\{r+1,\ldots,2r\}$. Every $B\subseteq Y_r$ has $|B|\le r$, so $|B|\notin B$ and $f(B)=|B|\notin Y_r$. Thus independent sets of every finite size exist. But no infinite independent $Y$ exists. Choose $m\in Y$ and choose $A\subseteq Y\setminus\{m\}$ of size $m$, possible by infinitude (including $A=\varnothing$ if $m=0$). Then $f(A)=m\in Y$, a contradiction.

ADVERSARIAL VERIFICATION AND REMAINING GAP

This is a counterexample on a countable set only, not on $\aleph_\omega$. Extending it by assigning a numerical colour to each point does not preserve the argument, because $f(A)$ must be an actual point of the proposed infinite set, not merely share its colour. The tree of finite independent sets has arbitrarily high levels but can branch infinitely, so the finite-branching form of König's lemma does not apply. The source's finite Kuratowski theorem remains compatible with this example. A construction or theorem using the specific singular cardinal $\aleph_\omega$ is still required.

SOURCES CHECKED

Complete local source gpt_pro_5.4/623.tex; exact statement checked in https://raw.githubusercontent.com/google-deepmind/formal-conjectures/main/FormalConjectures/ErdosProblems/623.lean. The explicit countable example is proved directly and no literature novelty is claimed.

FINAL

UNRESOLVED. The invalid compactness inference is concretely blocked; the cardinality-specific question remains.

COMPLETION ESTIMATE

Conservative subjective progress toward the stated uncountable problem. COMPLETION: 6%

Problem 623

FORMAL RESTATEMENT

Let $X$ be a set with $|X|=\aleph_\omega$. Let $f:[X]^{<\omega}\to X$ be a function defined on the family of all finite subsets of $X$ such that \[ \forall A\in [X]^{<\omega}\qquad f(A)\notin A. \] A subset $Y\subseteq X$ is independent (for $f$) if \[ \forall B\in [Y]^{<\omega}\qquad f(B)\notin Y. \] The question is: Must there exist an infinite independent set $Y\subseteq X$?

QUICK LITERATURE/CONTEXT CHECK

This is Erdős Problem #623. It is listed as open (as of the database access date recorded on the Erdős Problems site). The prompt attributes the problem to Erdős--Hajnal and notes their result that for $|X|<\aleph_\omega$ the answer is negative, while Erdős suggested the $\aleph_\omega$ case may be undecidable.

A nearby (stronger) theme in set theory is the free-subset property for algebras/structures, studied e.g. by Koepke: one asks for free subsets of a structure under closure by finitely many (or countably many) finitary operations. Koepke proved that a strong free-subset property at $\omega_\omega$ (the initial ordinal of cardinality $\aleph_\omega$) has high consistency strength (equiconsistent with a measurable cardinal). This suggests that at least some strengthened versions of "free subset" phenomena at $\aleph_\omega$ are not settled by elementary ZFC arguments.

ATTACK PLAN

1. Try to relate the one-step "independence" demanded here to standard free-subset principles for structures/algebras. If a known free-subset principle implies independence for set mappings, this gives conditional/relative-consistency information.
2. Attempt a direct ZFC construction of an infinite independent set via a recursion exploiting the representation $\aleph_\omega=\bigcup_{n<\omega}\aleph_n$.
3. Failing a full proof, isolate a precise obstruction: where the recursion fails (which finite configurations force the next choice into a small forbidden set), and what additional hypothesis would remove the obstruction.

WORK

(A) A conditional positive result from a stronger free-subset property.

Define, for each $m\ge 1$, an $m$-ary operation \[ g_m: X^m\to X,\qquad g_m(x_1,\dots,x_m):=f(\{x_1,\dots,x_m\}). \] (For repeated coordinates one can fix any convention; it does not affect the argument below.) Consider the structure \[ \mathcal S := \left(X, (g_m)_{m\in\mathbb N_{\ge 1}}\right) \] in a countable language of function symbols.

Assume a strong principle: every such structure on $X$ has a countably infinite subset $Y$ that is free in the closure sense, i.e. for every $y\in Y$ we have \[ y\notin \langle Y\setminus\{y\}\rangle_{\mathcal S}, \] where $\langle\cdot\rangle_{\mathcal S}$ denotes the substructure generated by a set under the functions $(g_m)$.

Then $Y$ is independent for $f$ in the sense of the problem. Indeed, if $B\subseteq Y$ is finite and $f(B)\in Y$, put $y:=f(B)$. By hypothesis $f(B)\notin B$, so $B\subseteq Y\setminus\{y\}$. But then applying the operation $g_{|B|}$ to (an ordering of) $B$ produces $y$, so $y\in\langle Y\setminus\{y\}\rangle_{\mathcal S}$, contradicting freeness. Hence $f(B)\notin Y$ for all finite $B\subseteq Y$.

This shows: any model in which such a strong free-subset property holds at $|X|=\aleph_\omega$ yields a positive answer to Problem 623.

(B) Why this does not resolve the ZFC question.

The above implication uses a closure-based freeness principle that is strictly stronger than one-step independence: one-step independence only forbids outputs $f(B)$ landing back in $Y$ when $B\subseteq Y$, whereas closure-based freeness also forbids reaching an element of $Y$ via iterated applications of the $g_m$ using intermediate values outside $Y$. Since the problem only asks for one-step independence, existing high-consistency-strength results about closure-freeness do not automatically settle the original question.

(C) Attempt at a direct construction and the first obstruction.

A natural attempt is to build an increasing sequence $(y_n)_{n<\omega}$ with $Y=\{y_n:n<\omega\}$ such that \[ \forall \text{finite }B\subseteq Y\quad f(B)\notin Y. \] At stage $n$, having chosen $y_0,\dots,y_{n-1}$, one can certainly ensure \[ y_n\notin \{y_0,\dots,y_{n-1}\}\cup\{f(B):B\subseteq\{y_0,\dots,y_{n-1}\}\}, \] by picking $y_n$ outside a countable (indeed finite) forbidden set.

However, the independence requirement also involves sets $B$ that contain the new element $y_n$. For each previously chosen $y_i$, we must avoid future choices $y_j$ hitting values of the form \[ f(B\cup\{y_n\})\quad\text{for }B\subseteq\{y_0,\dots,y_{n-1}\}, \] but these values are not known when choosing $y_n$, and may land anywhere in $X$, potentially forcing conflicts with infinitely many future choices. This is the first genuine gap: controlling all future images involving $y_n$ requires global information about $f$ that a naive stage-by-stage avoidance cannot provide.

VERIFICATION

The conditional implication in (A) is checked directly: if a closure-free $Y$ existed for the structure built from $f$, then no $f(B)$ with $B\subseteq Y$ could lie in $Y$, because that would generate an element of $Y$ from the others in one step.

The obstruction in (C) is real: the set of constraints involving the new element $y_n$ is not finite at stage $n$ from the standpoint of future steps.

FINAL

UNRESOLVED.

• (i) What was proved: A conditional positive answer: any sufficiently strong closure-based free-subset principle for countable languages on $|X|=\aleph_\omega$ implies the existence of an infinite independent set for every $f:[X]^{<\omega}\to X$ with $f(A)\notin A$.
• (ii) Strongest partial result stated here: The above reduction plus the observation that strong free-subset principles at $\omega_\omega$ have high consistency strength in the literature (so the conditional route is plausible in some models).
• (iii) First gap: A direct ZFC recursion to build $Y$ must control values $f(B\cup\{y_n\})$ that depend on the new point $y_n$ and can later collide with future chosen points; the naive finite-avoidance step does not address these infinitely many future constraints.
• (iv) Next concrete step: Either (a) find a ZFC combinatorial principle at $\aleph_\omega$ (e.g. a suitable reflection/compactness or $\Delta$-system style argument) that lets one thin a large set to an infinite one-step free set for all finite arities simultaneously, or (b) establish a relative-consistency separation by forcing a counterexample $f$ with no infinite independent set.

COMPLETION ESTIMATE

COMPLETION: 20%.