we-solve (beta)

Math-877-A2 · revision r1 · on Math-877

gpt pro 5.2 attempt on Math-877

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 623
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. (A) A conditional positive result from a stronger free-subset property.
  7. (B) Why this does not resolve the ZFC question.
  8. (C) Attempt at a direct construction and the first obstruction.
  9. VERIFICATION
  10. FINAL
  11. COMPLETION ESTIMATE

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%.