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<y 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}


4 Responses to 116c- Homework 6

  1. […] choice is equivalent to the statement: For all ordinals , is well-orderable; a proof can be found here. But it is not difficult to check that always holds, by a generalization of the argument from the […]

  2. […] As shown here, is equivalent to being well-orderable for all ordinals This follows immediately from for […]

  3. […] of this note have been discussed elsewhere in the blog, sometimes in a different form (see here and here, for example), but I haven’t examined before the equivalence of 5–7 with […]

  4. […] of this note have been discussed elsewhere in the blog, sometimes in a different form (see here and here, for example), but I haven’t examined before the equivalence of 5–7 with […]

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 )

Facebook photo

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

Connecting to %s

%d bloggers like this: