116c- Lecture 5

April 16, 2008

We defined addition, multiplication, and exponentiation of ordinals, and stated some basic properties of these operations. They extend into the transfinite the usual operations on natural numbers.

I made a mistake when indicating how to define these operations “intrinsically” rather than as a consequence of the transfinite recursion theorem: In the definition of ordinal exponentiation $\alpha^{\cdot\beta}$, we consider the set $\{f\in{}^\beta\alpha:f(\xi)=0\mbox{\ for all but finitely many }\xi<\beta\}$ and order it by setting $f, for $f\ne g$ in this set, iff $f(\xi) as ordinals, where $\xi<\beta$ is the largest ordinal such that $f(\xi)\ne g(\xi)$. In particular, there is such an ordinal $\xi$. In class, I mentioned that $\xi$ was the smallest such ordinal, but this does not work.

Using Hartog’s function and transfinite recursion we defined the long sequence of (well-ordered) cardinals, the alephs.

Remark. It was asked in class whether one can make sense of well-orders longer than ${\sf ORD}$ and if one can extend to them the operations we defined.

Of course, one can define classes that are well-orders of order type longer than ${\sf ORD}$ (for example, one can define the lexicographic ordering on $2\times{\sf ORD}$, which would correpsond to the “long ordinal” ${\sf ORD}+{\sf ORD}$). In ${\sf ZFC}$ this is cumbersome (since classes are formulas) but possible. There is an extension of ${\sf GB}$ that allows these operations to be carried out in a more natural way, Morse-Kelley set theory ${\sf MK}$, briefly discussed here.

However, I do not know of any significant advantages of this approach. But a few general (and unfortunately vague) observations can be made:

• Most likely, any way of extending well-orders beyond ${\sf ORD}$ would also provide a way of extending $V$ to a longer “universe of classes.” The study of these end-extensions (in the context of large cardinals, where it is easier to formalize these ideas) has resulted in an interesting research area originated by Keisler and Silver with recent results by Villaveces and others.
• I also expect that any sytematic way of doing this would translate with minor adjustments into a treatment of indiscernibles and elementary embeddings (which could potentially turn into a motivation for the study of these important topics and would be interesting at least from a pedagogical point of view).
• As I said, however, I do not know of any systematic attempt at doing something with these “long ordinals.” With one exception: the work of Reinhardt, with the caveat that I couldn’t make much sense of it in any productive way years ago. But this is an excuse to recommend a couple of excellent papers by Penelope Maddy, Believing the Axioms I and II, that originally appeared in The Journal of Symbolic Logic in 1988 and can be accessed through JSTOR. These papers discuss the intuitions behind the axioms of set theory and end up discussing more recent developments (like large cardinal axioms and determinacy assumptions), and I believe you will appreciate them. During her discussion of very large cardinals, Maddy mentions Reinhardt ideas, so this can also be a place to start if one is interested in the issue of “long ordinals.”

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 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 in $X$ iff $g(a) 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.

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.

116c- Lecture 2

April 4, 2008

We gave a formal definition of ordered pair, which allows us to discuss relations and functions in set theory. We presented the intuitive picture of the universe of sets in terms of the cumulative hierarchy, that we will be fleshing out in subsequent lectures.

We proved Cantor’s theorem stating that $|X|<|{\mathcal P}(X)|$ for any set $X$ and the Knaster-Tarski theorem stating that any order-preserving function from a complete lattice to itself has a fixed point, as a corollary of which we obtained the Schröder-Bernstein theorem stating that if $|A|\le|B|\le|A|$ then in fact $|A|=|B|$.

We briefly mentioned Cantor’s work on the theory of sets of uniqueness for trigonometric series, that led to his discovery of the ordinal numbers; Kechris’s very nice expository paper on the subject is here, the result that countable closed sets are of uniqueness is discussed in pages 3-13, and I highly recommend it.

Remark: Cantor’s original proof of the Schröder-Bernstein theorem used the axiom of choice and will be discussed in a future lecture, together with a more “combinatorial” proof.

116c- Lecture 1

April 2, 2008

We presented the Zermelo-Fraenkel axioms and derived some immediate consequences. In particular, we discussed Russell’s paradox and how it implies that the universe $V=\{x : x=x\}$ is not a set.

We briefly mentioned some alternatives such as Peter Aczel’s antifoundation axiom or Quine’s New Foundations. Aczel’s book can be found here. A nice short introduction to Quine’s NF can be found here.