Todd Trimble remark on Cantor-Schroeder-Bernstein

Theorem

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.

Proposition

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

Proof

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:

Proof

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:

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 19:41:20 by Todd Trimble