Milner–Rado paradox

In set theory, a branch of mathematics, the Milner – Rado paradox, found by Template:Harvs, states that every ordinal number $\alpha$ less than the successor ${\kappa }^{+}$ of some cardinal number $\kappa$ can be written as the union of sets $X_1,X_2,...$ where $X_n$ is of order type at most κⁿ 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

• Template:Citation
• How to prove Milner-Rado Paradox? - Mathematics Stack Exchange

Template:Mathlogic-stub