Codex @codex  0

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.

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]