How to prove the Milner-Rado Paradox?

For every ordinal $\alpha<\kappa^+$ there are sets $X_n\subset\alpha$ $(n\in\Bbb{N})$ such that $\alpha=\bigcup_n X_n$ and for each $n$ the order-type of $X_n$ is $\le\kappa^n$.

[By induction on $\alpha$, choosing a sequence cofinal in $\alpha$.]

I tried to prove this problem by using transfinite induction.

For $\alpha=0$, this statement is trivial.

If $\alpha$ has sets $X_n\subset \alpha$ satisfies $\alpha=\bigcup_n X_n$, $\text{order-type of }X_n\le\kappa^n$, we define $X'_0=\{\alpha\}$, $X_{n+1}'=X_n$. Then $\{X_n'\}$ satisfies $\bigcup_n X_n'=\alpha+1$, $\text{order-type of }X'_n \le \kappa^n$.

But I don't know how to proceed the proof. Thanks for any help.

Solution 1:

The Milner-Rado paradox is only a paradox in the traditional sense of the word: there are no inconsistencies here, but rather the result is (perhaps naively) seen as counter-intuitive. There are two reasons here: First, if $\alpha=\bigcup_{n<\omega}A_n$, and the $A_n$ are intervals, $A_n=[\alpha_n,\alpha_{n+1})$, where the $\alpha_i$ are increasing, and the order type of $A_n$ is at most $\kappa^n$ for all $n$, then $\alpha\le\kappa^\omega$. This means the obvious attempt to decompose an ordinal as requested has to fail as soon as the ordinal is sufficiently large.

It follows that the decomposition ought to be somewhat messy, for example, we may see $i< j$, such that the ordinals in $A_j$ are smaller than the ordinals in $A_i$, or we may see $i\ne j$ such that there are points in $A_i$ between points in $A_j$, and vice versa. But then we reach the second reason why the result may seem counter-intuitive: In

G.H. Toulmin. Shuffling ordinals and transfinite dimension, Proc. London Math. Soc. (3), 4, (1954), 177–195. MR0065907 (16,502a),

it is shown that if $A,B$ are sets of ordinals of order types $\alpha$ and $\beta$, then there is an upper bound on the order type of $A\cup B$ that depends only on $\alpha,\beta$.

(Namely, write $\alpha$ and $\beta$ as a decreasing sum of indecomposable ordinals, $\alpha=\sum_{i<k} \gamma_i n_i$ and $\beta=\sum_{i<k} \gamma_i m_i$, where the $\gamma_i$ are indecomposable, $\gamma_0>\dots>\gamma_{k-1}$, and the $n_i,m_i$ are natural numbers. Then $A\cup B$ has type at most $\sum_{i<k}\gamma_i(n_i+m_i)$, the natural or Hessenberg sum of $\alpha$ and $\beta$. In fact, Toulmin proved that there are only finitely many possible order types for $A\cup B$, all expressible in terms of the $\gamma_i,n_i,m_i$.)

This means that the fact that we may write ordinals much larger than $\kappa^\omega$ as the union of sets $A_n$ ($n<\omega$) with each $A_n$ of type at most $\kappa^n$, cannot be "seen" or anticipated by considering only finitely many of the $A_n$ and thus may appear surprising. (Of course, this is but one example of the many ways in which our intuitions about the finite prove insufficient when dealing with the infinite.)

Now we proceed to the proof.

This comes from a set of notes I'm working on. A draft version of the argument below can be found here. A proof close to this one can be found in the paper by Hajnal and Larson in the Handbook of set theory. The result itself comes from

Eric C. Milner, and Richard Rado. The pigeon-hole principle for ordinal numbers, Proceedings of the London Mathematical Society (3), 15, (1968), 750–768, 1965.

First notice that the result is clear if $\kappa=\omega$, since we can write any $\alpha<\omega_1$ as a countable union of singletons (and an empty set). So we may assume that $\kappa$ is uncountable. All powers in what follows are in the sense of ordinal exponentiation.

Notice that $|\kappa^{\rho}|=\kappa$ for any $\rho<\kappa^+$, as one can easily check by induction.

Notice also that the function $\alpha\mapsto\omega^{ \alpha}$ is normal (i.e., strictly increasing and continuous). By the above, it follows that $\omega^{\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^{\rho}=\omega^{\kappa\cdot\rho}$ for any $\rho$. Since $\omega^\delta$ is indecomposable, if $\alpha<\omega^{\delta}$, then the interval $[\alpha,\omega^{\delta})$ is order isomorphic to $\omega^{\delta}.$

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

Also, if $\alpha$ is a limit ordinal below $\kappa^+$, then we can write $\alpha=\sup_{\nu<\mathrm{cf}(\alpha)}\beta_\nu$ for some strictly increasing continuous sequence $(\beta_\nu\mid\nu<\mbox{cf} (\alpha))$ cofinal in $\alpha$. Let $A_0=\kappa^{\beta_1}$ and $A_\nu=[\kappa^{\beta_\nu}, \kappa^{\beta_{\nu+1}})$ for $0<\nu<\mbox{cf}(\alpha)$. Then $\kappa^{\alpha}=\bigcup_\nu A_\nu$ and each $A_\nu$ has order type $\kappa^{\beta_{\nu+1}}$.

That the sequence $\beta_\nu$ is continuous (at limits) ensures that the $A_\nu$ cover $\kappa^{ \alpha}$. That they have the claimed order type follows from indecomposability.

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

If $\sigma=\omega$, this immediately gives the result for $\kappa^{\rho}$: Take $X_0=\emptyset$ and $X_{2^m(2n+1)}=A_{m,n}$. Clearly their union is $\kappa^{\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^{\rho}$, and $\mbox{ot}(X_{n+2})$ is at most the order type of concatenating $\kappa$ many copies of $\kappa^{ n}$ (it is here that we use that $A_\nu<A_\mu$ for $\nu<\mu$), so $\mbox{ot} (X_{n+2})\le\kappa^{ n+1}$.

Edit, November 1, 2016: Toulmin's result actually appeared significantly earlier, and Toulmin rediscovered it independently. See

MR0005878 (3,225a). Philip W. Carruth. Arithmetic of ordinals with applications to the theory of ordered Abelian groups. Bull. Amer. Math. Soc. 48, (1942). 262–271.

Solution 2:

Let $\alpha$ be a limit ordinal, and for each $\beta < \alpha$, let $(X^\beta _n)_n$ be the obvious thing. Fix an increasing sequence $(\beta_\gamma)_{\gamma < \mathrm{cf}(\alpha)}$ cofinal in $\alpha$ with $\beta_0 = 1$. Note $\mathrm{cf}(\alpha) \leq \kappa$. Define:

$$X^\alpha _0 = \{0\};\ \ X^\alpha_{n+1} = \bigcup_\gamma X^{\beta_{\gamma+1}}_n\setminus \beta_\gamma$$

and that's it!

To see that it works, observe that:

$$\bigcup_{n>0}X^\alpha_n = \bigcup _n \bigcup _\gamma X^{\beta_{\gamma+1}}_n\setminus \beta_\gamma = \bigcup_\gamma \bigcup_n X^{\beta_{\gamma+1}}_n\setminus \beta_\gamma = \bigcup_\gamma \beta_{\gamma+1}\setminus \beta_\gamma = \alpha \setminus \beta_0$$

and so $\bigcup_nX^\alpha_n = \alpha$.

As for the order types, clearly $\mathrm{ot}(X^\alpha_0) = 1 = \kappa^0$. Noting that the sets $\beta_{\gamma+1}\setminus\beta_\gamma$ form a consecutive sequence of ordinal intervals, and that each $X^{\beta_{\gamma+1}}_n\setminus\beta_\gamma$ is a tail segment of $X^{\beta_{\gamma+1}}_n$ we get that:

$$\mathrm{ot}(X^\alpha_{n+1}) = \sum_\gamma \mathrm{ot}(X^{\beta_{\gamma+1}}_n\setminus\beta_\gamma) \leq \sum_\gamma \kappa^n = \kappa^n \cdot \mathrm{cf}(\alpha) \leq \kappa^n\cdot\kappa = \kappa^{n+1}$$

Solution 3:

$\newcommand{\cf}{\operatorname{cf}}$There’s no problem if $\alpha\le\kappa$, so suppose that $\alpha$ is a limit ordinal such that $\kappa<\alpha<\kappa^+$. Let $\lambda=\cf\alpha$, and let $\langle\alpha_\xi:\xi<\lambda\rangle$ be an increasing sequence cofinal in $\alpha$. For each $\xi<\lambda$ let $\{X_n^\xi:n\in\omega\}$ be a Milnor-Rado decomposition of $\alpha_\xi$, and let $\{X_n^\lambda:n\in\omega\}$ be a decomposition of $\lambda$.

For $n\in\omega$ let

$$X_{2n}=\bigcup_{\eta\in X_n^\lambda}\left(X_n^\eta\cap\alpha_\eta\setminus\bigcup_{\xi<\eta}\alpha_\xi\right)\;;$$

the order type of each set

$$X_n^\eta\cap\alpha_\eta\setminus\bigcup_{\xi<\eta}\alpha_\xi$$

is clearly at most that of $X_n^\eta$, which by hypothesis is at most $\kappa^n$. Moreover, if $\eta<\theta$,

$$\beta\in X_n^\eta\cap\alpha_\eta\setminus\bigcup_{\xi<\eta}\alpha_\xi\;,\quad\text{and}\quad\gamma\in X_n^\theta\cap\alpha_\eta\setminus\bigcup_{\xi<\theta}\alpha_\xi\;,$$

then $\beta<\delta$. Or in brief,

$$X_n^\eta\cap\alpha_\eta\setminus\bigcup_{\xi<\eta}\alpha_\xi<X_n^\theta\cap\alpha_\eta\setminus\bigcup_{\xi<\theta}\alpha_\xi\;.$$

Since the order type of $X_n^\lambda$ is at most $\kappa^n$, that of $X_{2n}$ is at most $\kappa^n\cdot\kappa^n=\kappa^{2n}$. Let $X_{2n+1}=\varnothing$, whose order type is certainly no more than $\kappa^{2n+1}$. It only remains to show that $\alpha=\bigcup_{n\in\omega}X_n$.

If $\beta<\alpha$, let $\eta<\lambda$ be minimal such that $\beta<\alpha_\eta$. Then $\beta\in\alpha_\eta\setminus\bigcup_{\xi<\eta}\alpha_xi$, and $\alpha_\eta=\bigcup_{n\in\omega}X_n^\eta$, so

$$\beta\in X_n^\eta\cap\alpha_\eta\setminus\bigcup_{\xi<\eta}\alpha_\xi\subseteq X_{2n}$$

for some $n\in\omega$.