= Injection-chain proof of the Cantor-Schröder-Bernstein theorem
{c}
{title2=$A_0=X\setminus g(Y),\quad A_{k+1}=g(f(A_k))$}
Given <injections> $f:X\to Y$ and $g:Y\to X$, start with the <set difference> $A_0=X\setminus g(Y)$: these are exactly the inputs for which $g^{-1}$ is unavailable. Follow both <functions> repeatedly, using the <natural-number recursion theorem> to define
$$
A_{k+1}=g(f(A_k)),\qquad
A=\bigcup_{k=0}^{\infty}A_k.
$$
Thus $A$ contains all the $X$ members reachable from any starting point in $A_0$. The notation $f(A_k)$ and $g(f(A_k))$ denotes <images of a function>. If $A_0$ is the <empty set>, then every $A_k$ is empty and $g^{-1}$ alone gives the desired <bijection>.
\Image[/cantor-schroder-bernstein-injection-chain-partition.png]
{title=The <Injection-chain proof of the Cantor-Schröder-Bernstein theorem> partitions the inputs into two matching rules}
{description=The upper row shows a chain seeded in $A_0$, where the <bijection> follows $f$. The lower row shows a chain beginning in $Y$, where the <bijection> reverses $g$. The same rule $g^{-1}$ also handles chains with no starting point and closed loops. Separate $X$ and $Y$ copies are used even if the original <sets> overlap.}
Define a <function> on all of $X$ by
$$
h(x)=\begin{cases}
f(x),&x\in A,\\
g^{-1}(x),&x\in X\setminus A.
\end{cases}
$$
Here $g^{-1}$ is the <inverse function> from $g(Y)$ to $Y$, obtained by restricting the <codomain> of $g$ to its <image>. It is well defined because $g$ is <injective>. Every $x\notin A$ belongs to $g(Y)$, since $A_0\subseteq A$, so the second rule is always available where it is used.
The decisive <set> identity is
$$
g(f(A))=\bigcup_{k=0}^{\infty}g(f(A_k))
=\bigcup_{k=1}^{\infty}A_k
=A\setminus A_0.
$$
The last equality holds because every $A_k$ with $k\geq1$ lies in $g(Y)$, whereas $A_0$ is disjoint from $g(Y)$. Consequently, for any $y\in Y$,
$$
g(y)\in A\quad\Longleftrightarrow\quad y\in f(A).
$$
Indeed, $g(y)$ cannot belong to $A_0$; if it lies in $A$, the identity gives $g(y)=g(f(a))$ for some $a\in A$, and <injectivity> gives $y=f(a)$. The converse follows directly by applying $g$.
Now $f$ restricts to a <bijection> from $A$ onto $f(A)$. The displayed equivalence says that $g$ restricts to a <bijection> from $Y\setminus f(A)$ onto $X\setminus A$, so its <inverse function> bijects the remaining inputs with the remaining outputs. The two input <sets> partition $X$ and the two output <sets> partition $Y$. Their combined <function> $h$ is therefore both <injective> and <surjective>.
No <choice function> is needed: $A$ is fixed by the given <injections>, and each required $g^{-1}(x)$ is unique. We neither choose a representative from each chain nor enumerate $X$. This is a proof in ordinary classical <ZF>, even when no <well-ordering> of the <sets> exists there.<Cantor-Schroeder-Bernstein Theorem by Paul Garrett>[Paul Garrett, Cantor-Schroeder-Bernstein Theorem, pp. 1–2, chain construction and pairings; p. 1, no invocation of the axiom of choice]{ref}
Back to article page
