---
tag: 96YGM41V3B
kind: proof
name: Proof that a function is bijective iff it has a two-sided inverse
msc: ["03E20"]
proves: 01VG2A0BHW
uses: [0SNQEF7Z53, 0PVG1CRAJN, 0XKH881BZ7, 0XHDTE5YMZ, 07HF9YCWPP, 0FSNQ0GNCC]
sources:
  - url: https://proofwiki.org/wiki/Bijection_iff_Left_and_Right_Inverse
---

## Proof

We prove the two directions separately, and we use no choice.

1. Let $f \colon A \to B$ be a [[function|0XHDTE5YMZ]]. Here $\circ$ is [[composition|07HF9YCWPP]] and $\mathrm{id}$ is the [[identity function|0FSNQ0GNCC]].
2. First suppose $f$ is [[bijective|0SNQEF7Z53]], that is, [[injective|0PVG1CRAJN]] and [[surjective|0XKH881BZ7]].
3. Let $b \in B$. Since $f$ is surjective, some $a \in A$ has $f(a) = b$. If also $f(a') = b$, then $f(a) = f(a')$, so $a = a'$ by injectivity. So exactly one $a \in A$ has $f(a) = b$.
4. Define $g \colon B \to A$ by letting $g(b)$ be the unique $a$ of step 3. Then $g$ is a function, and $f(g(b)) = b$ for each $b \in B$. So $f \circ g = \mathrm{id}_B$.
5. Let $a \in A$. By step 4, $f(g(f(a))) = f(a)$. Since $f$ is injective, $g(f(a)) = a$. So $g \circ f = \mathrm{id}_A$.
6. Now suppose that $g \colon B \to A$ satisfies $g \circ f = \mathrm{id}_A$ and $f \circ g = \mathrm{id}_B$.
7. Let $a, a' \in A$ with $f(a) = f(a')$. Applying $g$ gives $g(f(a)) = g(f(a'))$. Since $g \circ f = \mathrm{id}_A$, this says $a = a'$. So $f$ is injective.
8. Let $b \in B$ and put $a = g(b)$. Since $f \circ g = \mathrm{id}_B$, we get $f(a) = f(g(b)) = b$. So $f$ is surjective.
9. By steps 7 and 8, $f$ is bijective.
10. By steps 4, 5 and 9, $f$ is bijective if and only if there is a function $g \colon B \to A$ with $g \circ f = \mathrm{id}_A$ and $f \circ g = \mathrm{id}_B$.

## Idea

For a bijection, each $b$ has exactly one preimage, and sending $b$ to it undoes $f$ on both sides. Conversely, $g \circ f = \mathrm{id}_A$ forces $f$ to be injective, and $f \circ g = \mathrm{id}_B$ forces $f$ to be surjective.