Milner–Rado paradox

In set theory, a branch of mathematics, the Milner–Rado paradox, found by Eric Charles Milner and Richard Rado (1965), states that every ordinal number $\alpha$ less than the successor ${\kappa }^{+}$ of a given cardinal number $\kappa$ can be written as the union of sets $X_1,X_2,...$ where $X_n$ is of order type at most ${\kappa }^n$ for $n$ a positive integer.

Proof

The proof is by transfinite induction. Let $\alpha$ be a limit ordinal (the induction is trivial for successor ordinals), and for each $\beta <\alpha$, let $\{X_n^{\beta }{\}}_n$ be a partition of $\beta$ satisfying the requirements of the theorem.

Fix an increasing sequence $\{{\beta }_{\gamma }{\}}_{\gamma <\mathrm{c}\mathrm{f}(\alpha )}$ cofinal in $\alpha$ with ${\beta }_0=0$.

Note $\mathrm{c}\mathrm{f}(\alpha )\le \kappa$.

Define:

$X_0^{\alpha }=\{0\};X_{n+1}^{\alpha }=\bigcup _{\gamma }{X}_n^{{\beta }_{\gamma +1}}\setminus {\beta }_{\gamma }$

Observe that:

$\bigcup _{n>0}{X}_n^{\alpha }=\bigcup _n\bigcup _{\gamma }{X}_n^{{\beta }_{\gamma +1}}\setminus {\beta }_{\gamma }=\bigcup _{\gamma }\bigcup _n{X}_n^{{\beta }_{\gamma +1}}\setminus {\beta }_{\gamma }=\bigcup _{\gamma }{\beta }_{\gamma +1}\setminus {\beta }_{\gamma }=\alpha \setminus {\beta }_0$

and so $\bigcup _n{X}_n^{\alpha }=\alpha$.

Let $\mathrm{o}\mathrm{t}(A)$ be the order type of $A$. As for the order types, clearly $\mathrm{o}\mathrm{t}(X_0^{\alpha })=1={\kappa }^0$.

Noting that the sets ${\beta }_{\gamma +1}\setminus {\beta }_{\gamma }$ form a consecutive sequence of ordinal intervals, and that each $X_n^{{\beta }_{\gamma +1}}\setminus {\beta }_{\gamma }$ is a tail segment of $X_n^{{\beta }_{\gamma +1}}$, then:

$\mathrm{o}\mathrm{t}(X_{n+1}^{\alpha })=\sum _{\gamma }\mathrm{o}\mathrm{t}(X_n^{{\beta }_{\gamma +1}}\setminus {\beta }_{\gamma })\le \sum _{\gamma }{\kappa }^n={\kappa }^n\cdot \mathrm{c}\mathrm{f}(\alpha )\le {\kappa }^n\cdot \kappa ={\kappa }^{n+1}$

References

• Milner, E. C.; Rado, R. (1965), "The pigeon-hole principle for ordinal numbers", Proceedings of the London Mathematical Society, Series 3 15: 750–768, doi:10.1112/plms/s3-15.1.750 
• Hajnal, A.; Larson, J.A. (2010), "Partition Relations", Handbook of Set Theory, 1, Springer, pp. 129–214 
• How to prove Milner-Rado Paradox? - Mathematics Stack Exchange