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<y 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<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 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<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 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<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,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<delta, 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<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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: