116c- Lecture 2

April 4, 2008

We gave a formal definition of ordered pair, which allows us to discuss relations and functions in set theory. We presented the intuitive picture of the universe of sets in terms of the cumulative hierarchy, that we will be fleshing out in subsequent lectures.

We proved Cantor’s theorem stating that |X|<|{\mathcal P}(X)| for any set X and the Knaster-Tarski theorem stating that any order-preserving function from a complete lattice to itself has a fixed point, as a corollary of which we obtained the Schröder-Bernstein theorem stating that if |A|\le|B|\le|A| then in fact |A|=|B|.

We briefly mentioned Cantor’s work on the theory of sets of uniqueness for trigonometric series, that led to his discovery of the ordinal numbers; Kechris’s very nice expository paper on the subject is here, the result that countable closed sets are of uniqueness is discussed in pages 3-13, and I highly recommend it.

Remark: Cantor’s original proof of the Schröder-Bernstein theorem used the axiom of choice and will be discussed in a future lecture, together with a more “combinatorial” proof.