116c- Lecture 4

April 11, 2008

We showed that every well-ordered set is isomorphic to a unique ordinal. The proof uses replacement in an essential way.

Example. (V_{\omega+\omega},\in)\models{\sf ZFC}-\mbox{\sf Replacement} and in this model there are well-ordered sets not isomorphic to any ordinal. We will return to this example in the future.

We defined natural numbers in the context of set theory and showed that \omega, the first limit ordinal, is the set of natural numbers.

We explained how we understand (proper) classes within {\sf ZFC}. Other formalizations of set theory allow one to handle classes as actual objects, for example Gödel-Bernays-von Neumann set theory, {\sf GB}, the system in which Gödel originally presented his proof of the consistency of the axiom of choice and the generalized continuum hypothesis. See here for a brief description of {\sf GB}. One can show that {\sf GB} is conservative over {\sf ZF}.

Finally, we stated versions of the theorem of transfinite induction and proved a version of the theorem of transfinite recursion: Given any F:V\to V there is a unique G:{\sf ORD}\to V such that for all ordinals \alpha, G(\alpha)=F(G\upharpoonright\alpha).

This result is very useful. It allows us, for example, to define operations on the ordinals by recursion. The easiest example is perhaps the definition of addition of ordinals: Let \beta+1=S(\beta) be the successor of \beta.

  • \alpha+0=\alpha.
  • \alpha+(\beta+1)=(\alpha+\beta)+1.
  • \alpha+\lambda=\sup\{\alpha+\beta:\beta<\lambda\} for \lambda limit.

To see that there is a unique function satisfying these conditions, one can show that this is a particular case of the theorem. For this, define F_\alpha:V\to V as follows: F_\alpha(x)=0 unless x is a sequence. If \mbox{dom}(x)=0, let F_\alpha(x)=\alpha. If \mbox{dom}(x)=\beta+1 for some \beta, let F_\alpha(x)=S(x(\beta)). If \mbox{dom}(x)=\lambda is a limit ordinal, let F_\alpha(x)=\bigcup x. The function G_\alpha whose existence is granted by the theorem is precisely G_\alpha(\beta)=\alpha+\beta.

We also stated (without proof) Hartog’s theorem. The following definition will be useful.

Definition. A set X is finite iff there is a natural number n such that |X|=|n|. Otherwise, it is infinite.

(This is our official defintion. There are several possible ways of defining infinite sets, and they are not necessarily equivalent without choice. One such alternative, Dedekind infinite, is presented in Exercise 2 of the Homework.)

For completeness, I include a proof of Hartog’s theorem. Recall:

Theorem (Hartog). ({\sf ZF}) For any set X, let \aleph(X)=\{\alpha: there is an injection of \alpha into X\}. Then \aleph(X) is an ordinal.

Proof. Clearly the class \aleph(X)\subset{\sf ORD} is transitive (which for ordinals simply means, closed under initial segments). So it suffices to see that it is a set. This uses replacement.

Notice that if f:\alpha\to Y is a bijection, then there is a well-ordering of Y in order type \alpha: Simply set a<b in Y iff there are \beta<\gamma in \alpha such that f(\beta)=a and f(\gamma)=b.

By von Neumann’s theorem, conversely, if Y\subset X and (Y,<) is well-ordered, then there is an ordinal \alpha such that \alpha\in\aleph(X) as witnessed by the unique order isomorphism f:Y\to\alpha. Hence, \aleph(X) coincides with the class of ordinals \alpha such that there is a subset Y of X and a well-ordering of Y isomorphic to \alpha

Since a well-ordering of Y is just a subset of Y\times Y, it follows that \aleph(X) is a set, by replacement. {\sf QED}

The following (important) observation is needed in the homework, I will return to it in Tuesday’s lecture: Suppose now that X itself is well-orderable. Then |X|<|\aleph(X)|. Because since X is well-orderable, there is an ordinal \alpha\in\aleph(X) (thus, \alpha\subseteq\aleph(X)) and a bijection f:X\to\alpha. Hence, |X|\le|\aleph(X)|. However, if g:X\to\aleph(X) is a bijection, we can well-order X isomorphically to \aleph(X) by setting a<b in X iff g(a)<g(b) as ordinals. But this would imply that \aleph(X)\in\aleph(X), a contradiction.

Remark. In the statement of Exercise 1 in the Homework, \aleph(X) is defined as the union of the set we are calling \aleph(X) here. This makes no difference whenever X is infinite (as one can easily check), so feel free to use either version, we will discuss this issue in lecture.