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 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 is well-orderable: Clearly, if the result is true, each would be well-orderable. But also, given any set , it belongs to some and, since the latter is transitive, in fact and therefore is well-orderable as well. The strategy is suggested by the fact that for all , , so a well-ordering of gives us a well-ordering of thanks to our initial assumption.

We argue by induction: Clearly is well-ordered by the well-ordering . Given a well-ordering of , there is a unique ordinal and a unique order isomorphism . By assumption,  is well-orderable, and any well-ordering of it induces (via ) a well-ordering of .

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

The first, and not too serious, one, is that the well-orderings of different 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 . More precisely, define for , iff

• Either , or else
• , say, and if is the well-ordering of , then .

It is easy to see that this is indeed a well-ordering of : Given a non-empty ,  let be least so that has an element of rank Then the -first among these elements would be the -least element of . Or we could argue that there are no infinite -descending chains: If is such a chain then, since is a non-increasing sequence of ordinals, there must be such that all with have the same rank . But then would be an infinite -descending sequence, contradicting that is a well-ordering.

The second obstacle is more serious. Namely, the assumption is simply that there is a well-ordering of each , not that there is any canonical way of choosing one. In order for the argument above to work, we need not just that each for is well-orderable, but in fact we need to have selected a sequence of well-orderings of the , with respect to which we proceeded to define the well-ordering of .

The way we began the proof suggests a solution: When we argued that it suffices to well-order each , we considered an arbitrary set and noticed that if , then a well-ordering of gives us a well-ordering of . Similarly, given limit, if we can find large enough so each  for is below , then we can use a well-ordering of  to induce the required well-ordering .

We now proceed to implement this idea: Let . (Notice that this makes sense since, inductively, each with is well-orderable and therefore isomorphic to a unique cardinal.) Let be a well-ordering of . We use to define a sequence so that well-orders for all . We use recursion on to define this sequence. Again, . At limit stages we copy the strategy with which we tried to well-order to define : For , set  iff

• Either , or else
• , say, and .

Finally, given , we describe how to define : Let be the unique ordinal such that there is an order isomorphism

.

Since , then , so and the well-ordering of also well-orders . Via , this induces the well-ordering of we were looking for.

Equipped with the sequence we can now proceed to well-order as explained above. This completes the proof.

Advertisement