I thought of this today while eating apples.(adsbygoogle = window.adsbygoogle || []).push({});

Suppose we have two arbitrary sets X and Y and a surjection g:X→Y. We seek an injection f:Y→X. Each element of Y has at least one pre-image in X, but there might be more than one; the nonempty sets [itex]X_y = \{ x\in X : g(x) = y \}[/itex] are subsets of X, indexed by Y. In fact, they partition X, for if we had [itex]x\in X_a\cap X_b[/itex] then, by definition, a = g(x) = b. Thus these sets are pairwise disjoint; by the axiom of choice, there exists a function h such that [itex]h(X_y) \in X_y[/itex] for all [itex]y \in Y[/itex]. From here, we can define the injection f(y) = h(X_{y}).

Is there a proof which does not use the axiom of choice?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Given g from X onto Y, can we find some f from Y into X without the axiom of choice?

**Physics Forums | Science Articles, Homework Help, Discussion**