Proof of the Schröder–Bernstein theorem

Proof

We build the bijection piece by piece: it follows $f$ on one part of $A$ and $g^{-1}$ on the rest.

1. Let $f \colon A \to B$ and $g \colon B \to A$ be injective functions.
2. By definition by recursion, define subsets $C_n \subseteq A$ by $C_0 = A \setminus g(B)$ and $C_{n+1} = g(f(C_n))$. Here $g(f(C_n))$ is the image of $C_n$ under $g \circ f$.
3. Let $C = \bigcup_{n \in \N} C_n$ be their union.
4. Let $x \in A \setminus C$. Then $x \notin C_0$, so $x \in g(B)$. Since $g$ is injective, exactly one $y \in B$ has $g(y) = x$. Write $g^{-1}(x) = y$.
5. Define $h \colon A \to B$ by $h(x) = f(x)$ if $x \in C$, and $h(x) = g^{-1}(x)$ if $x \notin C$.
6. We show that $h$ is injective. Let $x, x' \in A$ with $h(x) = h(x')$.
7. If $x, x' \in C$, then $f(x) = f(x')$, so $x = x'$ because $f$ is injective.
8. If $x, x' \notin C$, then $g^{-1}(x) = g^{-1}(x')$. Applying $g$ gives $x = x'$.
9. Suppose $x \in C$ and $x' \notin C$. Then $f(x) = g^{-1}(x')$, so $x' = g(f(x))$.
10. In step 9, $x \in C_n$ for some $n$, so $x' \in g(f(C_n)) = C_{n+1} \subseteq C$. This contradicts $x' \notin C$. The case $x \notin C$, $x' \in C$ is the same with the roles exchanged.
11. So $h$ is injective. We show that $h$ is surjective. Let $y \in B$ and put $x = g(y)$.
12. If $x \notin C$, then $g^{-1}(x) = y$ by step 4, so $h(x) = y$.
13. If $x \in C$, then $x \in C_n$ for some $n$. Since $x \in g(B)$, $x \notin C_0$, so $n \ge 1$.
14. So $x \in C_n = g(f(C_{n-1}))$, and $x = g(f(z))$ for some $z \in C_{n-1} \subseteq C$.
15. Then $g(y) = g(f(z))$, so $y = f(z)$ because $g$ is injective. Since $z \in C$, $h(z) = f(z) = y$.
16. Thus $h$ is injective and surjective, so $h \colon A \to B$ is a bijective function.