View source for Milner–Rado paradox

In [[set theory]], a branch of mathematics, the '''Milner &ndash; Rado paradox''', found by {{harvs|txt|first1=Eric Charles|last1=Milner|author1-link=Eric Charles Milner|first2=Richard|last2=Rado|author2-link=Richard Rado|year=1965}}, states that every [[ordinal number]] <math>\alpha</math> less than the [[Successor cardinal|successor]] <math>\kappa^{+}</math> of some [[cardinal number]] <math>\kappa</math> can be written as the union of sets <math>X_1, X_2,...</math> where <math>X_n</math> is of [[order type]] at most ''&kappa;''<sup>''n''</sup> for ''n'' a positive integer.

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

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

Note <math>\mathrm{cf}\,(\alpha)\le\kappa</math>.

Define:

:<math>X^\alpha _0 = \{0\};\ \ X^\alpha_{n+1} = \bigcup_\gamma X^{\beta_{\gamma+1}}_n\setminus \beta_\gamma</math>

Observe that:

:<math>\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</math>

and so  ''<math>\bigcup_nX^\alpha_n = \alpha</math>''.

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

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

:<math>\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==
*{{Citation | last1=Milner | first1=E. C. | last2=Rado | first2=R. | title=The pigeon-hole principle for ordinal numbers | doi=10.1112/plms/s3-15.1.750 | mr=0190003 | year=1965 | journal= Proceedings of the London Mathematical Society |series=Series 3 | volume=15 | pages=750–768}}
*[https://math.stackexchange.com/q/440184 How to prove Milner-Rado Paradox? - Mathematics Stack Exchange]

{{DEFAULTSORT:Milner-Rado paradox}}
[[Category:Set theory]]
[[Category:Paradoxes]]


{{mathlogic-stub}}