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 be a set and let be subsets such that there are bijections and . Show without using the Axiom of Choice that there is a bijection from to .
It turns out that you can construct an injection from into (and, by symmetry, an injection from into ). 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 are sets and and are maps, then there are subsets and such that
(1) , and
That struck me as a truly remarkable statement: You can dissect and so that you get two “matching pairs” of subsets so that “respect” the pairings. No restrictions are made on the nature of the maps ! If we take to be injections, it is clear how CSB can be proved from this: just define to be on and on , and so 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 is a complete lattice and is an order-preserving function, then has a fixed point. — The proof of this fixed point theorem is remarkably straightforward: Just consider the supremum of the set and verify that .
As to why Knaster-Tarski is helpful for proving Banach’s theorem, let be the powerset of and note that is a complete lattice, ordered by set inclusion . Consider
defined by .
We verify that is order-preserving, therefore it has a fixed point . Set . So we get item (1) of Banach’s theorem for free, and item (2) is easy too, because since is a fixed point of , and therefore .
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!