116c- Lecture 4

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:Vto V there is a unique G:{sf ORD}to V such that for all ordinals alpha, G(alpha)=F(Gupharpoonrightalpha).

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:Vto 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:alphato 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 Ysubset X and (Y,<) is well-ordered, then there is an ordinal alpha such that alphainaleph(X) as witnessed by the unique order isomorphism f:Ytoalpha. 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 Ytimes 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 alphainaleph(X) (thus, alphasubseteqaleph(X)) and a bijection f:Xtoalpha. Hence, |X|le|aleph(X)|. However, if g:Xtoaleph(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)inaleph(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.


One Response to 116c- Lecture 4

  1. Domenic says:

    Notes for lectures 3 and 4 now incorporated, as well as the stuff from this post and a single theorem from our homework:


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: