- #1
Unit
- 182
- 0
I thought of this today while eating apples.
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(Xy).
Is there a proof which does not use the axiom of choice?
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(Xy).
Is there a proof which does not use the axiom of choice?