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 $xsubseteq 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,yin 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 $Asubseteq 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 is such a chain then, since $({rm rk}(x_n):n is a non-increasing sequence of ordinals, there must be $n_0$ such that all $x_n$ with $nge n_0$ have the same rank $beta$. But then $(x_n:nge 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 is well-orderable, but in fact we need to have selected a sequence $(<_{beta+1}:beta 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 $xsubseteq 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 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. (Notice that this makes sense since, inductively, each $V_beta$ with $beta 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 so that $<_beta$ well-orders $V_beta$ for all $beta. We use recursion on $beta to define this sequence. Again, $<_0=emptyset$. At limit stages $gamma we copy the strategy with which we tried to well-order $V_alpha$ to define $<_gamma$: For $x,yin 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, so $xisubsetdelta$ 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 we can now proceed to well-order $V_alpha$ as explained above. This completes the proof. ${sf QED}$