Due Tuesday, April 15 at 2:30 pm.

## 116c- Homework 1

April 9, 2008## 116c- Lecture 3

April 9, 2008We verified the “surjective” version of Cantor’s theorem: If then is not injective. A curious weakness of the standard diagonal proof is that the argument is not entirely constructive: We considered the set and showed that there is some set such that .

**Question.** Can one define such a set ?

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 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 is not a set.