Proof that a function is bijective iff it has a two-sided inverse

Proof

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

1. Let $f \colon A \to B$ be a function. Here $\circ$ is composition and $\mathrm{id}$ is the identity function.
2. First suppose $f$ is bijective, that is, injective and surjective.
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$.