116c- Homework 6

Homework 6

Due Wednesday, May 21 at 2:30 pm.

Update. Since Wednesday, May 21 is ditch day, the homework is now due Thursday, May 22 at 2:30 pm.

Update. Here is a quick sketch of the solution of exercise 3:

Assume in ${\sf ZF}$ that the power set of any ordinal is well-orderable. We want to conclude that choice holds, i.e., that every set is well-orderable. A natural strategy is to proceed inductively, showing that each $V_\alpha$ is well-orderable: Clearly, if the result is true, each $V_\alpha$ would be well-orderable. But also, given any set $x$, it belongs to some $V_\alpha$ and, since the latter is transitive, in fact $x\subseteq V_\alpha$ and therefore $x$ is well-orderable as well. The strategy is suggested by the fact that for all $\alpha$, $V_{\alpha+1}={\mathcal P}(V_\alpha)$, so a well-ordering of $V_\alpha$ gives us a well-ordering of $V_{\alpha+1}$ thanks to our initial assumption.

We argue by induction: Clearly $V_0$ is well-ordered by the well-ordering $<_0=\emptyset$. Given a well-ordering $<$ of $V_\alpha$, there is a unique ordinal $\beta$ and a unique order isomorphism $\pi : (V_\alpha , <)$ $\to (\beta, \in)$. By assumption, ${\mathcal P}(\beta)$ is well-orderable, and any well-ordering of it induces (via $\pi^{-1}$) a well-ordering of $V_{\alpha+1}$.

We are left with the task of showing that $V_\alpha$ is well-orderable for $\alpha$ limit. The natural approach is to patch together the well-orderings of the previous $V_\beta$ into a well-ordering of $V_\alpha$. This approach meets two obstacles.

The first, and not too serious, one, is that the well-orderings of different $V_\beta$ are not necessarily compatible, so we need to be careful on how we “patch them together. ” The natural solution to this obstacle is to simply order the sets as they appear inside $V_\alpha$. More precisely, define $x for $x,y\in V_\alpha$, iff

• Either ${\rm rk}(x)<{\rm rk}(y)$, or else
• ${\rm rk}(x)={\rm rk}(y)=\beta$, say, and if $<_{\beta+1}$ is the well-ordering of $V_{\beta+1}$, then $x<_{\beta+1}y$.

It is easy to see that this is indeed a well-ordering of $V_\alpha$: Given a non-empty $A\subseteq V_\alpha$,  let $\gamma$ be least so that $A$ has an element of rank $\gamma$. Then the $<_{\gamma+1}$-first among these elements would be the $<$-least element of $A$. Or we could argue that there are no infinite $<$-descending chains: If $(x_n:n<\omega)$ is such a chain then, since $({\rm rk}(x_n):n<\omega)$ is a non-increasing sequence of ordinals, there must be $n_0$ such that all $x_n$ with $n\ge n_0$ have the same rank $\beta$. But then $(x_n:n\ge n_0)$ would be an infinite $<_{\beta+1}$-descending sequence, contradicting that $<_{\beta+1}$ is a well-ordering.

The second obstacle is more serious. Namely, the assumption is simply that there is a well-ordering of each ${\mathcal P}(\delta)$, not that there is any canonical way of choosing one. In order for the argument above to work, we need not just that each $V_\beta$ for $\beta<\alpha$ is well-orderable, but in fact we need to have selected a sequence $(<_{\beta+1}:\beta<\alpha)$ of well-orderings of the $V_{\beta+1}$, with respect to which we proceeded to define the well-ordering $<$ of $V_\alpha$.

The way we began the proof suggests a solution: When we argued that it suffices to well-order each $V_\gamma$, we considered an arbitrary set $x$ and noticed that if $x\subseteq V_\beta$, then a well-ordering of $V_\beta$ gives us a well-ordering of $x$. Similarly, given $\alpha$ limit, if we can find $\delta$ large enough so each $|V_\beta|$ for $\beta<\alpha$ is below $\delta$, then we can use a well-ordering of ${\mathcal P}(\delta)$ to induce the required well-ordering $<_\beta$.

We now proceed to implement this idea: Let $\delta=\sup_{\beta<\alpha}|V_\beta|^+$. (Notice that this makes sense since, inductively, each $V_\beta$ with $\beta<\alpha$ is well-orderable and therefore isomorphic to a unique cardinal.) Let $<^*$ be a well-ordering of ${\mathcal P}(\delta)$. We use $<^*$ to define a sequence $(<_\beta:\beta<\alpha)$ so that $<_\beta$ well-orders $V_\beta$ for all $\beta<\alpha$. We use recursion on $\beta<\alpha$ to define this sequence. Again, $<_0=\emptyset$. At limit stages $\gamma<\alpha$ we copy the strategy with which we tried to well-order $V_\alpha$ to define $<_\gamma$: For $x,y\in V_\gamma$, set $x<_\gamma y$ iff

• Either ${\rm rk}(x)<{\rm rk}(y)$, or else
• ${\rm rk}(x)={\rm rk}(y)=\beta$, say, and $x<_{\beta+1}y$.

Finally, given $<_\beta$, we describe how to define $<_{\beta+1}$: Let $\xi=\xi_\beta$ be the unique ordinal such that there is an order isomorphism

$\pi : (V_\beta,<_\beta)$ $\to (\xi,\in)$.

Since $|\xi|=|V_\beta|$, then $\xi<\delta$, so $\xi\subset\delta$ and the well-ordering $<^*$ of ${\mathcal P}(\delta)$ also well-orders ${\mathcal P}(\xi)$. Via $\pi^{-1}$, this induces the well-ordering $<_{\beta+1}$ of $V_{\beta+1}$ we were looking for.

Equipped with the sequence $(<_\beta:\beta<\alpha)$ we can now proceed to well-order $V_\alpha$ as explained above. This completes the proof. ${\sf QED}$