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.)