116c- Lecture 6

April 18, 2008

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 $f:A\to B$ and $g:B\to A$ are injective, we consider the monotone map $\pi:{\mathcal P}(A)\to{\mathcal P}(A)$ given by $\pi(X)=A\setminus g[B\setminus f[X]]$, since if $X$ is a  fixed point of $\pi$, then $A\setminus X=g[B\setminus f[X]]$, and we obtain a bijection $h:A\to B$ by setting $h(x)=f(x)$ if $x\in X$ and $h(x)=g^{-1}(x)$ if $x\in A\setminus X$.

We also presented a combinatorial proof considering “paths” along the graphs of $f$ and $g$ (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 ${\sf ZF}$) of several versions of choice:

1. The well-ordering principle (our official version of ${\sf AC}$).
2. The existence of choice functions $f:{\mathcal P}(X)\setminus\{\emptyset\}\to X$ for any set $X$.
3. Zorn’s lemma.
4. Trichotomy: Given any sets $A$ and $B$, one of them injects into the other. (Called trichotomy as it gives that either $|A|=|B|$, $|A|<|B|$ or $|B|<|A|$.)
5. $k$-trichotomy (for a fixed $2\le k\in\omega$): Given any $k$ sets, at least one of them injects into another.

(The proof that (5) implies (1) will be given in Tuesday.)