remark on Cantor-Schroeder-Bernstein

Given injective functions $f: A \to B$ and $g: B \to A$, there is a bijection $h: A \to B$.

There are two familiar proofs of the CSB theorem, with somewhat different flavors. One is a kind of back-and-forth argument, attributed to Julius König, involving chains of applications of $f$ and $g$ that extend forwards and backwards. The other is a more abstract-looking proof where the CSB theorem is neatly derived as a corollary of the Knaster-Tarski fixed-point theorem. In this short note I would like to “beta-reduce” the abstract proof, indicating that the result is the exact same as the back-and-forth proof.

Let us first recall the Knaster-Tarski theorem.

Let $L$ be a sup-lattice and $\phi: L \to L$ an order-preserving function. Then $\phi$ has a fixed point.

In fact we construct the greatest fixed point of $\phi$ as

$a = \sup \{x \in L: x \leq \phi(x)\}.$

For every $x \in L$ satisfying $x \leq \phi(x)$, we have $x \leq a$ and therefore $x \leq \phi(x) \leq \phi(a)$ since $\phi$ is order-preserving, and therefore $\phi(a)$ is an upper bound of $\{x \in L: x \leq \phi(x)\}$. Hence $a \leq \phi(a)$ as $a$ is the least upper bound. But then it follows that $\phi(a) \leq \phi(\phi(a))$ by order-preservation, so $\phi(a) \in \{x \in L: x \leq \phi(x)\}$, whence $\phi(a) \leq a$ by definition of $a$. Hence $a = \phi(a)$.

The abstract proof of CSB is as follows:

Given injective functions $f: A \to B$ and $g: B \to A$, let $L = P(A)$, and define an order-preserving map $\phi: P(A) \to P(A)$ by $\phi(S) = \neg g(\neg f(S))$ where $\neg$ denotes complement and $f(S)$ and $g(T)$ denote direct images of $S \in P(A)$, $T \in P(B)$. The map $\phi$ is order-preserving; it has a fixed point $H \subseteq A$ by Knaster-Tarski. Now define

$\array{
A & \stackrel{h}{\to} & B & \\
a & \mapsto & f(a) & \; if \; a \in H \\
& \mapsto & g^{-1}(a) & \; if \; a \in \neg H
}$

From $H = \neg g(\neg f(H))$ we have $\neg H = g(\neg f(H))$, so the last line of the multiline definition makes sense. Putting $J = f(H)$, we have

$\neg J = \neg f(H) = g^{-1} g (\neg f(H)) = g^{-1}(\neg H)$

and so $f: H \to J$ is a bijection, and $g^{-1}: \neg H \to \neg J$ is a bijection, and therefore $h = f \sqcup g^{-1}: H \sqcup \neg H \to J \sqcup \neg J$ is also a bijection.

The proof, although “abstract”, can be converted into an explicit construction. In particular, the greatest fixed point (or terminal coalgebra) of $\phi = \neg \exists_g \neg \exists_f$ can be calculated by an application of Adamek’s theorem:

Suppose $C$ is a category with a terminal object $1$ and (projective) limits of chains $\omega \to C$, and $\phi: C \to C$ is a functor that preserves limits of $\omega$-chains. Then the terminal coalgebra of $\phi$ is given as the limit of

$\ldots \to \phi^{n+1}(1) \stackrel{\phi^n(!)}{\to} \phi^n(1) \to \ldots \to \phi(1) \stackrel{!}{\to} 1.$

To be continued…

(One year later…) Heh, seems I’ve now written up details at the nLab.

Revised on February 16, 2016 at 14:41:20
by
Todd Trimble