## 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<\omega_1$ as a countable union of singletons. So we may assume that $\kappa$ is uncountable.

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

Notice that the function $\alpha\mapsto\omega^{\cdot \alpha}$ is normal. By the above, it follows that $\omega^{\cdot\lambda}=\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^{\cdot\rho}=\omega^{\cdot\kappa\cdot\rho}$ for any $\rho$. It is easy to see that for any $\delta$, if $\alpha<\omega^{\cdot\delta}$, then the interval $\null[\alpha,\omega^{\cdot\delta})$ is order isomorphic to $\omega^{\cdot\delta}$; this can be proved by a straightforward induction on $\delta$.

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

Also, if $\alpha$ is a limit ordinal below $\kappa^+$, then we can write $\alpha=\sup_{\nu<\mbox{\small cf}(\alpha)}\beta_\nu$ for some strictly increasing continuous sequence $(\beta_\nu:\nu<\mbox{cf}(\alpha))$ cofinal in $\alpha$. Let $A_0=\kappa^{\cdot\beta_1}$ and $A_\nu=[\kappa^{\cdot\beta_\nu},\kappa^{\cdot\beta_{\nu+1}})$ for $0<\nu<\mbox{cf}(\alpha)$. Then $\kappa^{\cdot\alpha}=\bigcup_\nu A_nu$ and each $A_\nu$ has order type $\kappa^{\cdot\beta_{\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^{\cdot\rho}$ 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^{\cdot\rho}$ can be written as claimed in the paradox. In particular, each $A_\nu$, having order type an ordinal smaller than $\kappa^{\cdot\rho}$, can be written that way, say $A_\nu=\bigcup_n A_{\nu,n}$ where $\mbox{ot}(A_{\nu,n})<\kappa^{\cdot n}$. If $\sigma=\omega$, this immediately gives the result for $\kappa^{\cdot\rho}$: Take $X_0=\emptyset$ and $X_{2^m(2n+1)}=A_{m,n}$. Clearly their union is $\kappa^{\cdot\rho}$ 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^{\cdot\rho}$, 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<\mu$], so $\mbox{ot}(X_{n+2})\le\kappa^{\cdot n+1}$.

Advertisement

### 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<\kappa^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<\kappa^+$ 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^{\cdot\delta+1},0)=\omega^{\cdot\delta} \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?