116c- Homework 3

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<A_\mu for \nu<\mu], so \mbox{ot}(X_{n+2})\le\kappa^{\cdot n+1}.

Advertisement

This entry was posted on Tuesday, April 22nd, 2008 at 2:56 am and is filed under 116c: Set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

7 Responses to 116c- Homework 3

  1. Fedor Manin says:
    April 28, 2008 at 2:03 am

    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?

    Reply
  2. andrescaicedo says:
    April 28, 2008 at 6:48 am

    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.

    Reply
  3. Fedor Manin says:
    April 29, 2008 at 5:34 am

    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.

    Reply
  4. andrescaicedo says:
    April 29, 2008 at 7:07 am

    Yes, you are right. Thanks for spotting this!

    Reply
  5. Fedor Manin says:
    April 29, 2008 at 8:23 pm

    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.

    Reply
  6. andrescaicedo says:
    April 29, 2008 at 9:17 pm

    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.

    Reply
  7. Domenic Denicola says:
    April 30, 2008 at 9:25 pm

    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?

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

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

Cancel

Connecting to %s

%d bloggers like this: