To each injective function there exists a surjective such that $f \circ g =\operatorname{Id}_X$

Question

So I learned that to each surjective function exists an injective function. I wanted to prove the other direction since it sounded reasonable.

Then there should exist a surjective function f such that $fog = \operatorname{Id}_X$ For each injective function $g: X \to Y$, there exists a surjective function $f: Y\to X$ such that $f∘g = \operatorname{Id}_X$ applies.

Proof (Axiom of choice)

Consider for each $y∈g(X)$ the set $X_y := \{x∈X: g(x) = y\} $

Since $g$ is a function, there follows that $X_y , g(X) ≠ ∅$. For all $y: X_y≠∅$ since g is a function.

The axiom of choice says there exists a function $f : g(X) \to \bigcup\limits_{y∈g(x)} (X_y), =X,\;g(x) ⊂ Y$, thus it follows that $f: Y \to X$ with $f(y) ∈ X_y\; ∀y$ *since $g$ is injective.

So is this a correct proof and a correct claim? I just went with my gut intuition

Answer 1

You're using the Axiom of Choice for the wrong direction.

If we have an injective $g:X\to Y$, then assuming $X$ is non-empty we can construct a surjective $f:Y\to X$ without Choice the following way:

Pick a distinguished element $x_0\in X$. Now take an arbitrary $y\in Y$. If there is an $x\in X$ such that $g(x) = y$, then $f(y) = x$ (this $x$ is unique by injectivity, so this is well-defined). If there is no such $x$, then $f(y) = x_0$.

On the other hand, if we have a surjective $f:Y\to X$, then we need Choice. We can construct an injective $g:X\to Y$ the following way:

Take an arbitrary $x\in X$, and look at the set $f^{-1}(\{x\})$. This set is non-empty, so we can pick a $y$ in it. Set $g(x) = y$. This can be done for any $x\in X$, and two distinct $x$ will necessarily result in two distinct $y$, so our $g$ is injective. However, we need the Axiom of Choice in order to guarantee that we can do this for all $x\in X$ simultaneously, and stitch together the results into an actual function $g$.