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^{cdotrho}|=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 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<omega^{cdotdelta}, 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<kappa^+, we can write kappa^{cdotalpha+1}=bigcup_{nu<kappa}A_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<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^{cdotbeta_1} and A_nu=[kappa^{cdotbeta_nu},kappa^{cdotbeta_{nu+1}}) for 0<nu<mbox{cf}(alpha). 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})<kappa^{cdot 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<A_mu for nu<mu], 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<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^{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):


      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?

    Leave a Reply

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

    WordPress.com Logo

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

    Twitter picture

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

    Facebook photo

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

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s

    %d bloggers like this: