Basics on maps

Recently I was trying to prove the following statement found as an exercise in a topology book by Arkhangel’skii (I forget the title):

Let $X$ be a set and let $A, B$ be subsets such that there are bijections $\varphi_A: A \to (X \setminus A)$ and $\varphi_B: B \to (X \setminus B)$. Show without using the Axiom of Choice that there is a bijection from $A$ to $B$.

It turns out that you can construct an injection from $A$ into $B$ (and, by symmetry, an injection from $B$ into $A$). So the theorem of Cantor-Schroeder-Bernstein (CSB) comes in usefully (which can be proved without AC): It says that whenever you have injective maps between two sets, then there is a bijection between them.

There are several proofs to CSB, none of which was simple or elegant enough that it would stick to my memory. So, with the aid of Google and Wikipedia, I tried to find a proof that I would remember. On the German-speaking wiki page of CSB I was pointed to an astonishing generalisation of CSB, called Banach’s mapping theorem, which is purely set-theoretical and has nothing to do with contractions, Banach spaces, or whatever you would associate with Stefan Banach. Here is the statement of that theorem.

Banach’s mapping theorem: If $X, Y$ are sets and $f: X \to Y$ and $g: Y \to X$ are maps, then there are subsets $A \subseteq X$ and $B \subseteq Y$ such that

(1) $f(A) = B$, and
(2) $g(Y\setminus B) = X \setminus A$.

That struck me as a truly remarkable statement: You can dissect $X$ and $Y$ so that you get two “matching pairs” of subsets so that $f,g$ “respect” the pairings. No restrictions are made on the nature of the maps $f, g$! If we take $f, g$ to be injections, it is clear how CSB can be proved from this: just define $\varphi : X \to Y$ to be $f$ on $A$ and $g^{-1}$ on $X \setminus A$, and so $\varphi$ is our bijection.

How would we go to prove Banach’s little gem? It turns out that it is a consequence from the Knaster-Tarski fixed point theorem:

Knaster-Tarski fixed point theorem: If $(P, \leq)$ is a complete lattice and $f:L \to L$ is an order-preserving function, then $f$ has a fixed point. — The proof of this fixed point theorem is remarkably straightforward: Just consider the supremum $s^*$ of the set $M = \{l \in L : l \leq f(l)\}$ and verify that $f(s^*) = s^*$.

As to why Knaster-Tarski is helpful for proving Banach’s theorem, let $P(X)$ be the powerset of $X$ and note that $P(X)$ is a complete lattice, ordered by set inclusion $\subseteq$. Consider

$\Phi: P(X) \to P(X)$ defined by $S \mapsto X \setminus (g(Y\setminus f(S))$.

We verify that $\Phi$ is order-preserving, therefore it has a fixed point $A \in P(X)$. Set $B:= f(A)$. So we get item (1) of Banach’s theorem for free, and item (2) is easy too, because $A = X \setminus (g(Y\setminus B)$ since $A$ is a fixed point of $\Phi$, and therefore $X\setminus A = g(Y \setminus B)$.

For me, seeing how you get Banach’s theorem out of Knaster’s and Tarski’s well-known fixed-point theorem was a real wow moment!