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 .

Advertisements

Like this:

LikeLoading...

Related

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.

It seems that the Milner-Rado paradox, as stated, is false, because if is successor, the sequence of has to be eventually constant, so for some ; but this is not the case for .

Fedor, the exercise is not requiring that the sets are intervals or that they appear one after another in order type . For , for example, you can even let each (for ) be a singleton. For , the sets corresponding to some cannot be intervals.

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

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?

I thought about this question a while ago, while teaching a topics course. Since one can easily check that $${}|{\mathbb R}|=|{\mathcal P}({\mathbb N})|$$ by a direct construction that does not involve diagonalization, the question can be restated as: Is there a proof of Cantor's theorem that ${}|X|

First of all, note (as Monroe does in his question) that if $\mathbb P,\mathbb Q$ are ccc, then $\mathbb P\times\mathbb Q$ is $\mathfrak c^+$-cc, as an immediate consequence of the Erdős-Rado theorem $(2^{\aleph_0})^+\to(\aleph_1)^2_2$. (This is to say, if $\mathbb P$ and $\mathbb Q$ do not admit uncountable antichains, then any antichain in their product ha […]

The technique of almost disjoint forcing was introduced in MR0289291 (44 #6482). Jensen, R. B.; Solovay, R. M. Some applications of almost disjoint sets. In Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968), pp. 84–104, North-Holland, Amsterdam, 1970. Fix an almost disjoint family $X=(x_\alpha:\alpha

At the moment most of those decisions come from me, at least for computer science papers (those with a 68 class as primary). The practice of having proceedings and final versions of papers is not exclusive to computer science, but this is where it is most common. I've found more often than not that the journal version is significantly different from the […]

The answer is no in general. For instance, by what is essentially an argument of Sierpiński, if $(X,\Sigma,\nu)$ is a $\sigma$-finite continuous measure space, then no non-null subset of $X$ admits a $\nu\times\nu$-measurable well-ordering. The proof is almost verbatim the one here. It is consistent (assuming large cardinals) that there is an extension of Le […]

A notion now considered standard of primitive recursive set function is introduced in MR0281602 (43 #7317). Jensen, Ronald B.; Karp, Carol. Primitive recursive set functions. In 1971 Axiomatic Set Thoory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) pp. 143–176 Amer. Math. Soc., Providence, R.I. The concept is use […]

The power of a set is its cardinality. (As opposed to its power set, which is something else.) As you noticed in the comments, Kurepa trees are supposed to have countable levels, although just saying that a tree has size and height $\omega_1$ is not enough to conclude this, so the definition you quoted is incomplete as stated. Usually the convention is that […]

The key problem in the absence of the axiom of replacement is that there may be well-ordered sets $S$ that are too large in the sense that they are longer than any ordinal. In that case, the collection of ordinals isomorphic to an initial segment of $S$ would be the class of all ordinals, which is not a set. For example, with $\omega$ denoting as usual the f […]

R. Solovay proved that the provably $\mathbf\Delta^1_2$ sets are Lebesgue measurable (and have the property of Baire). A set $A$ is provably $\mathbf\Delta^1_2$ iff there is a real $a$, a $\Sigma^1_2$ formula $\phi(x,y)$ and a $\Pi^1_2$ formula $\psi(x,y)$ such that $A=\{t\mid \phi(t,a)\}=\{t\mid\psi(t,a)\}$, and $\mathsf{ZFC}$ proves that $\phi$ and $\psi$ […]

It seems that the Milner-Rado paradox, as stated, is false, because if is successor, the sequence of has to be eventually constant, so for some ; but this is not the case for .

Is there a typo in the problem?

Fedor, the exercise is not requiring that the sets are intervals or that they appear one after another in order type . For , for example, you can even let each (for ) be a singleton. For , the sets corresponding to some cannot be intervals.

This time, something I’m pretty sure is a trivial error: in 2(f), we have to take , since .

Yes, you are right. Thanks for spotting this!

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

Then we have and , but .

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

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

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?