116c- Homework 1

April 9, 2008

Homework 1.

Due Tuesday,  April 15 at 2:30 pm.

116c- Lecture 3

April 9, 2008

We verified the “surjective” version of Cantor’s theorem: If f:{\mathcal P}(X)\to X then f is not injective. A curious weakness of the standard diagonal proof is that the argument is not entirely constructive: We considered the set A=\{a\in X:\exists Z\,(a=f(Z)\notin Z)\} and showed that there is some set Z\ne A such that f(Z)=f(A).

Question. Can one define such a set Z?

As a consequence of the results we will prove on well-orderings, we will be able to provide a different proof where the pair of distinct sets verifying that f is not injective is definable. (Definability is an issue we will revisit a few times.)

We proved the trichotomy theorem for well-orderings, defined ordinals, and showed that {\sf ORD}=\{ x : x \mbox{ is an ordinal}\} is not a set (the Burali-Forti paradox).