## 116c- 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 $(lambda,alpha)$ satisfies the conditions of $(alpha,beta)$ 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 $n>0$.
• Update. Here is a quick sketch of the proof of the Milner-Rado paradox.

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

Notice that $|kappa^{cdotrho}|=kappa$. This can be checked either by induction on $rho, or by using the characterization of ordinal exponentiation in terms of functions of finite support.

Notice that the function $alphamapstoomega^{cdot alpha}$ is normal. By the above, it follows that $omega^{cdotlambda}=lambda$ for all uncountable cardinals $lambda$. In particular, it suffices to prove the result for ordinals $alpha$ that are an ordinal power of $kappa$, since these ordinals are cofinal in $kappa^+$, and a representation as desired for an ordinal gives (by restriction) such a representation for any smaller ordinal.

By the above, $kappa^{cdotrho}=omega^{cdotkappacdotrho}$ for any $rho$. It is easy to see that for any $delta$, if $alpha, then the interval $null[alpha,omega^{cdotdelta})$ is order isomorphic to $omega^{cdotdelta}$; this can be proved by a straightforward induction on $delta$.

For any $alpha, we can write $kappa^{cdotalpha+1}=bigcup_{nu, where $A_nu=[kappa^{cdot alpha}cdotnu,kappa^{cdotalpha}cdot(nu+1))$ so it has order type $kappa^{cdotalpha}$.

Also, if $alpha$ is a limit ordinal below $kappa^+$, then we can write $alpha=sup_{nu for some strictly increasing continuous sequence $(beta_nu:nu cofinal in $alpha$. Let $A_0=kappa^{cdotbeta_1}$ and $A_nu=[kappa^{cdotbeta_nu},kappa^{cdotbeta_{nu+1}})$ for $0. Then $kappa^{cdotalpha}=bigcup_nu A_nu$ and each $A_nu$ has order type $kappa^{cdotbeta_{nu+1}}$.

[That the sequence $beta_nu$ is continuous (at limits) ensures that the $A_nu$ cover $kappa^{cdot alpha}$. That they have the claimed order type follows from the “straightforward inductive argument” three paragraphs above.]

So we have written each $kappa^{cdotrho}$ as an increasing union of $sigma$ many intervals whose order types are ordinal powers of $kappa$, and $sigma$ is either $kappa$ or $mbox{cf}(rho)$. Now proceed by induction. We may assume that each ordinal below $kappa^{cdotrho}$ can be written as claimed in the paradox. In particular, each $A_nu$, having order type an ordinal smaller than $kappa^{cdotrho}$, can be written that way, say $A_nu=bigcup_n A_{nu,n}$ where $mbox{ot}(A_{nu,n}).

If $sigma=omega$, this immediately gives the result for $kappa^{cdotrho}$: Take $X_0=emptyset$ and $X_{2^m(2n+1)}=A_{m,n}$. Clearly their union is $kappa^{cdotrho}$ and they have small order type as required.

If $sigma>omega$, take $X_0=X_1=emptyset$ and $X_{n+2}=bigcup_nu A_{nu,n}$. Again, their union is $kappa^{cdotrho}$, and $mbox{ot}(X_{n+2})$ is at most the order type of concatenating $kappa$ many copies of $kappa^{cdot n}$ [it is here that we use that $A_nu for $nu], so $mbox{ot}(X_{n+2})lekappa^{cdot n+1}$.

### 7 Responses to 116c- Homework 3

1. Fedor Manin says:

It seems that the Milner-Rado paradox, as stated, is false, because if $alpha$ is successor, the sequence of $X_n$ has to be eventually constant, so $alpha=X_n for some $n$; but this is not the case for $kappa=omega, alpha=omega^omega+1$.

Is there a typo in the problem?

2. Fedor, the exercise is not requiring that the sets $X_n$ are intervals or that they appear one after another in order type $omega$. For $alpha=omega^omega+1$, for example, you can even let each $X_n$ (for $n>0$) be a singleton. For $kappa=2^{aleph_0}$, the sets $X_n$ corresponding to some $alpha cannot be intervals.

3. Fedor Manin says:

This time, something I’m pretty sure is a trivial error: in 2(f), we have to take $n>0$, since $d(omega^{cdotdelta+1},0)=omega^{cdotdelta} cdot 0=0$.

4. Yes, you are right. Thanks for spotting this!

5. Fedor Manin says:

Uh… I think we found a counterexample for 2(c):

$n=1$
$lambda=omega$
$alpha=omega^2$
$beta=omega$

Then we have $lambda+alpha=alpha$ and $d(alpha,1)=omega$, but $lambda+beta=omega cdot 2 > d(lambda+alpha,1)$.

If the condition in part (a) holds for $lambda$ and $alpha$, this problem is simple. I think this would be sufficient to do the later parts of 2.

6. 8) You are right, I was a bit suspicious of the general statement. Yes, if $(lambda,alpha)$ is like $(alpha,beta)$ in 2.(a), the result holds, and this should be all that is needed for later items.

7. That set was pretty fun. I don’t feel like I really understood what was going on in 1(d) and 1(e), however. (And maybe that means I only tricked myself into thinking that I understood parts (a)–(c).) Would you be willing to post a solution or something for problem 1?