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.)
This entry was posted on Friday, April 18th, 2008 at 12:14 am and is filed under 116c: Set theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
![\pi(X)=A\setminus g[B\setminus f[X]]](https://s0.wp.com/latex.php?latex=%5Cpi%28X%29%3DA%5Csetminus+g%5BB%5Csetminus+f%5BX%5D%5D&bg=ffffff&fg=333333&s=0&c=20201002)
![A\setminus X=g[B\setminus f[X]]](https://s0.wp.com/latex.php?latex=A%5Csetminus+X%3Dg%5BB%5Csetminus+f%5BX%5D%5D&bg=ffffff&fg=333333&s=0&c=20201002)
).
for any set
and
, one of them injects into the other. (Called trichotomy as it gives that either
,
or
.)
-trichotomy (for a fixed
): Given any
A kind of library 
Lecture notes updated! 🙂