We revisited the proof of the Schröder-Bernstein theorem and showed how arguments using recursion can provide explicit fixed points for the required map. Recall that if and are injective, we consider the monotone map given by , since if is a fixed point of , then , and we obtain a bijection by setting if and if .
We also presented a combinatorial proof considering “paths” along the graphs of and (surely folklore, but apparently first recorded by Paul Cohen) and Cantor’s original argument (using choice).
We then started the proof of the equivalence (in ) of several versions of choice:
- The well-ordering principle (our official version of ).
- The existence of choice functions for any set .
- Zorn’s lemma.
- Trichotomy: Given any sets and , one of them injects into the other. (Called trichotomy as it gives that either , or .)
- -trichotomy (for a fixed ): Given any sets, at least one of them injects into another.
(The proof that (5) implies (1) will be given in Tuesday.)