Milner–Rado paradox

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 α less than the successor κ+ of some cardinal number κ can be written as the union of sets X1,X2,... where Xn is of order type at most κn for n a positive integer.

Proof[edit]

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^\beta_n\}_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)\le\kappa.

Define:

X^\alpha _0 = \{0\};\ \ X^\alpha_{n+1} = \bigcup_\gamma X^{\beta_{\gamma+1}}_n\setminus \beta_\gamma

Observe that:

\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

and so \bigcup_nX^\alpha_n = \alpha.

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

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

\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}

References[edit]