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 {cf} \,(\alpha )}$ cofinal in $\alpha$ with $\beta _{0}=0$.

Note $\mathrm {cf} \,(\alpha )\leq \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 {ot} \,(A)$ be the order type of $A$. As for the order types, clearly $\mathrm {ot} (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 {ot} (X_{n+1}^{\alpha })=\sum _{\gamma }\mathrm {ot} (X_{n}^{\beta _{\gamma +1}}\setminus \beta _{\gamma })\leq \sum _{\gamma }\kappa ^{n}=\kappa ^{n}\cdot \mathrm {cf} (\alpha )\leq \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, MR 0190003
• Hajnal, A.; Larson, J.A. (2010), "Partition Relations", in Foreman, M.; Kanamori, A. (eds.), Handbook of Set Theory, vol. 1, Springer, pp. 129–214
• How to prove Milner-Rado Paradox? - Mathematics Stack Exchange