Homework 3.

**Update.** Now due Wednesday, April 30 at 2:30 pm.

**Corrections**. (Thanks to Fedor Manin for noticing these.)

- On Exercise 2.(c), assume in addition that satisfies the conditions of in item 2.(a); this should really be all that is needed of 2.(c) for later parts of the exercise.
- On Exercise 2.(f), we also need .

**Update**. Here is a quick sketch of the proof of the Milner-Rado paradox.

First notice that the result is clear if , since we can write any as a countable union of singletons. So we may assume that is uncountable.

Notice that . This can be checked either by induction on , or by using the characterization of ordinal exponentiation in terms of functions of finite support.

Notice that the function is normal. By the above, it follows that for all uncountable cardinals . In particular, it suffices to prove the result for ordinals that are an ordinal power of , since these ordinals are cofinal in , and a representation as desired for an ordinal gives (by restriction) such a representation for any smaller ordinal.

By the above, for any . It is easy to see that for any , if , then the interval is order isomorphic to ; this can be proved by a straightforward induction on .

For any , we can write , where so it has order type .

Also, if is a limit ordinal below , then we can write for some strictly increasing continuous sequence cofinal in . Let and for . Then and each has order type .

[That the sequence is continuous (at limits) ensures that the cover . That they have the claimed order type follows from the “straightforward inductive argument” three paragraphs above.]

So we have written each as an increasing union of many intervals whose order types are ordinal powers of , and is either or . Now proceed by induction. We may assume that each ordinal below can be written as claimed in the paradox. In particular, each , having order type an ordinal smaller than , can be written that way, say where . If , this immediately gives the result for : Take and . Clearly their union is and they have small order type as required. If , take and . Again, their union is , and is at most the order type of concatenating many copies of [it is here that we use that for ], so .