Axiomatic Set Theory 6: Gluing
Posted by Tom Leinster
Previously: Part 5. Next: Part 7.
A category theorist might imagine that a chapter with this title would be about constructing colimits, and they’d be half right.
We did indeed construct the quotient of a set by an equivalence relation, and prove its universal property and the first isomorphism theorem for sets (which is the core of its more famous algebraic cousins). And we did indeed construct coproducts, using a technique that looks much more like the ZFC trick of “” than it looks like Paré’s sublime construction of colimits in a topos.
But that’s not all! We also did an isomorphism-invariant version of “there is no set of all sets”, proving that for any set-indexed family of sets , there is some set not isomorphic to any of its members . And, most excitingly, we used coproducts to prove the Cantor–Bernstein theorem: if you’ve got sets and and know that there exist injections , then and must, in fact, be isomorphic.
Re: Axiomatic Set Theory 6: Gluing
Incidentally, at some point I spent a while reading about the history of the Cantor–Bernstein theorem. It has often been called the “Schröder–Bernstein theorem” (at least in English language sources). But, as I observe in the notes, Schröder’s only contribution was a proof attempt which he himself conceded was wrong.
If I understand and remember correctly, the contributions of the various players were something like this.
Cantor proved the result, but used the axiom of choice to do it. He set it as a challenge to prove it without the axiom of choice.
Schröder thought he’d proved it without choice, and published the purported proof. The mistake was eventually spotted, and Schröder agreed that his proof was wrong.
Dedekind proved it without choice in a letter to Cantor, but didn’t publish it. I think I remember reading that there’s no evidence that Cantor read or understood Dedekind’s proof, and that the relationship between the two of them was sometimes strained.
Bernstein was the first to publish a correct proof without choice.
There’s more on the Wikipedia page, which I’m too lazy to read again now.
The notes use my preferred proof, which is probably the less well known of the two I’m aware of. It depends on the Knaster–Tarski fixed point theorem, which states that every order endomorphism of a complete lattice has a fixed point. In the notes, I only state and prove this for the case we need, where the lattice is a power set. This saves me from having to define “complete lattice” (or indeed “lattice”).
The other proof I have in mind is where you trace each element back along the given injections for as long as you can, and split into cases according to whether/how that process terminates. I think that’s the best known proof, but for some reason I find it less appealing.
Although the two proofs feel quite different, if you work through them, you discover that both actually give the same algorithm. What I mean is that given sets and injections and , both proofs not only prove the existence of a bijection between and , but construct a bijection—and it turns out that they construct the same bijection.