## 116c- Homework 1

April 9, 2008

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