Cantor-Schröder-Bernstein theorem ($|X|\le |Y|,|Y|\le |X|\Rightarrow |X|=|Y|$)

If there are injections $X\to Y$ and $Y\to X$, then there is a bijection $X\cong Y$.

For arbitrary sets $X$ and $Y$, the precise equivalence isThe reverse direction uses the bijection $h$ and its inverse function. Neither set is assumed to be a subset of the other: the hypothesis concerns functions, rather than containments. The forward direction holds in ZF without the axiom of choice.^[ref]

This makes cardinality comparison an antisymmetric relation: if each set is no larger than the other in the sense of an injection, they have equal cardinality. It also gives a practical strategy: build two convenient injections and let the theorem supply the bijection. The Injection-chain proof of the Cantor-Schröder-Bernstein theorem explains how to combine them without losing an output or pairing two inputs with the same output.

Take $X=\{0,1,2,\dots \}$, the nonnegative integers, and $Y=\{1,2,3,\dots \}$, the positive integers. Choose the injectionsHere $g$ is an inclusion map, while $f$ reaches only the positive even integers. In particular, $f$ is not a bijection: it misses every positive odd integer. Simply using the inverse function of $g$ on its image misses input zero.

The remedy is to follow the alternating injections starting at the missing input zero:The subscripts distinguish an input in $X$ from an output in $Y$, even when their numerical values agree. The resulting subset of $X$ is $A=\{0,2,6,14,30,\dots \}$. Its sequence of members satisfies $a_0=0$ and $a_{k+1}=2a_k+2$, giving $a_k=2^{k+1}-2$ by mathematical induction. Define the function

The image $h(A)=\{2,6,14,30,\dots \}=A\setminus \{0\}$ covers all the positive members of $A$ exactly once. The other inputs cover $Y\setminus A$ exactly once by staying fixed. These output sets are disjoint and their union is $Y$, proving that $h$ is a bijection. In particular, $h(0)=2$, $h(2)=6$, $h(6)=14$, while $h(1)=1$ and $h(4)=4$.

For completeness, its inverse function isThe familiar bijection $n\mapsto n+1$ also works, but this example shows something more specific: the two chosen injections can repair the missing zero by moving only a sparse sequence of inputs. The repair never has to shift the entire set.

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 defineThus $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.

Define a function on all of $X$ byHere $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 isThe last equality holds because every $A_k$ with $k\ge 1$ lies in $g(Y)$, whereas $A_0$ is disjoint from $g(Y)$. Consequently, for any $y\in Y$,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.^[ref]