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 [math]\displaystyle{ \alpha }[/math] less than the successor [math]\displaystyle{ \kappa^{+} }[/math] of some cardinal number [math]\displaystyle{ \kappa }[/math] can be written as the union of sets [math]\displaystyle{ X_1, X_2,... }[/math] where [math]\displaystyle{ X_n }[/math] is of order type at most κⁿ for n a positive integer.

Proof

The proof is by transfinite induction. Let [math]\displaystyle{ \alpha }[/math] be a limit ordinal (the induction is trivial for successor ordinals), and for each [math]\displaystyle{ \beta\lt \alpha }[/math], let [math]\displaystyle{ \{X^\beta_n\}_n }[/math] be a partition of [math]\displaystyle{ \beta }[/math] satisfying the requirements of the theorem.

Fix an increasing sequence [math]\displaystyle{ \{\beta_\gamma\}_{\gamma\lt \mathrm{cf}\,(\alpha)} }[/math] cofinal in [math]\displaystyle{ \alpha }[/math] with [math]\displaystyle{ \beta_0=0 }[/math].

Note [math]\displaystyle{ \mathrm{cf}\,(\alpha)\le\kappa }[/math].

Define:

[math]\displaystyle{ X^\alpha _0 = \{0\};\ \ X^\alpha_{n+1} = \bigcup_\gamma X^{\beta_{\gamma+1}}_n\setminus \beta_\gamma }[/math]

Observe that:

[math]\displaystyle{ \bigcup_{n\gt 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 }[/math]

and so [math]\displaystyle{ \bigcup_nX^\alpha_n = \alpha }[/math].

Let [math]\displaystyle{ \mathrm{ot}\,(A) }[/math] be the order type of [math]\displaystyle{ A }[/math]. As for the order types, clearly [math]\displaystyle{ \mathrm{ot}(X^\alpha_0) = 1 = \kappa^0 }[/math].

Noting that the sets [math]\displaystyle{ \beta_{\gamma+1}\setminus\beta_\gamma }[/math] form a consecutive sequence of ordinal intervals, and that each [math]\displaystyle{ X^{\beta_{\gamma+1}}_n\setminus\beta_\gamma }[/math] is a tail segment of [math]\displaystyle{ X^{\beta_{\gamma+1}}_n }[/math], then:

[math]\displaystyle{ \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} }[/math]

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 
• How to prove Milner-Rado Paradox? - Mathematics Stack Exchange