---
tag: A2A69H6MM4
kind: proof
name: Proof that a function is surjective iff it has a right inverse
msc: ["03E20"]
proves: 0TYQNHVB4C
uses: [0XKH881BZ7, 0DDPZAG5ER, 0HTGB13FE2, 0YXEQWRGP0, 0FGCFY1AZX, 0XHDTE5YMZ, 07HF9YCWPP, 0FSNQ0GNCC]
sources:
  - url: https://proofwiki.org/wiki/Surjection_iff_Right_Inverse
    locator: Proof 1
---

## Proof

We prove the two directions separately. Only the second direction uses the axiom of choice.

1. Let $f \colon A \to B$ be a [[function|0XHDTE5YMZ]].
2. First suppose that $f$ has a [[right inverse|0DDPZAG5ER]] $h \colon B \to A$. So $f(h(b)) = b$ for each $b \in B$.
3. Let $b \in B$ and put $a = h(b) \in A$. By step 2, $f(a) = b$. So $f$ is [[surjective|0XKH881BZ7]].
4. Now suppose that $f$ is surjective. For $b \in B$, let $F_b = f^{-1}(\set{b}) = \set{a \in A \mid f(a) = b}$ be the [[preimage|0FGCFY1AZX]] of $\set{b}$.
5. Since $f$ is surjective, each $F_b$ is nonempty. Let $X = \set{F_b \mid b \in B}$. Then $X$ is a set of nonempty sets.
6. By the [[axiom of choice|0HTGB13FE2]], there is a [[choice function|0YXEQWRGP0]] $c \colon X \to \bigcup X$ with $c(S) \in S$ for each $S \in X$.
7. Each $F_b$ is a subset of $A$, so $\bigcup X \subseteq A$. Define $h \colon B \to A$ by $h(b) = c(F_b)$.
8. Let $b \in B$. By step 6, $h(b) = c(F_b) \in F_b$. By the definition of $F_b$, this says $f(h(b)) = b$.
9. By step 8, $f \circ h = \mathrm{id}_B$, where $\mathrm{id}_B$ is the [[identity function|0FSNQ0GNCC]] and $\circ$ is [[composition|07HF9YCWPP]]. So $h$ is a right inverse of $f$.
10. By steps 3 and 9, $f$ is surjective if and only if $f$ has a right inverse.

## Idea

A right inverse must pick, for each $b$, one point of $A$ that $f$ sends to $b$. Surjectivity says such points exist, and the axiom of choice lets us pick one for every $b$ at once. Conversely, the picked point $h(b)$ shows that $b$ is hit.