> [!NOTE] Theorem (Surjective iff right-invertible) > Suppose $X$ and $Y$ are non-empty. Then $f:X\to Y$ is [[Surjection|surjective]] iff $f$ has a *[[Function Inverse|right inverse]]*. *Proof*. For each $y\in Y$ there is some $x\in X$ so that $f(x)=y.$ For each $y$ choose one such $x$ and denote it $g(y)$ (note that when $Y$ is infinite, picking the elements $g(y)$ requires the [[Zermelo Frankel set theory (ZFC)|axiom of choice]]). Thus $g:X\to Y$ is a function. We can check that indeed $(f\circ g) (y)=\text{Id}_{Y}(y).$ This holds for all $y\in Y$ so $f\circ g= \text{Id}_{Y}.$ Conversely, suppose that $g$ is a right inverse for $f.$ Take $y\in Y$ and let $x=g(y).$ We compute as follows: $ \begin{aligned} y & =\operatorname{Id}_Y(y) & & \text { definition of } \operatorname{Id}_Y \\ & =(f \circ g)(y) & & g \text { is a right inverse for } f \\ & =f(g(y)) & & \text { definition of composition } \\ & =f(x) & & \text { definition of } x \end{aligned} $Hence $f$ is surjective.