Todd Trimble
remark on Cantor-Schroeder-Bernstein

Theorem

Given injective functions f:ABf: A \to B and g:BAg: B \to A, there is a bijection h:ABh: 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 ff and gg 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 LL be a sup-lattice and ϕ:LL\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{xL:xϕ(x)}.a = \sup \{x \in L: x \leq \phi(x)\}.

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

The abstract proof of CSB is as follows:

Proof

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

A h B a f(a) ifaH g 1(a) ifa¬H\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=¬g(¬f(H))H = \neg g(\neg f(H)) we have ¬H=g(¬f(H))\neg H = g(\neg f(H)), so the last line of the multiline definition makes sense. Putting J=f(H)J = f(H), we have

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

and so f:HJf: H \to J is a bijection, and g 1:¬H¬Jg^{-1}: \neg H \to \neg J is a bijection, and therefore h=fg 1:H¬HJ¬Jh = 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 ϕ=¬ g¬ f\phi = \neg \exists_g \neg \exists_f can be calculated by an application of Adamek’s theorem:

Theorem

Suppose CC is a category with a terminal object 11 and (projective) limits of chains ωC\omega \to C, and ϕ:CC\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

ϕ n+1(1)ϕ n(!)ϕ n(1)ϕ(1)!1.\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