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 α {\displaystyle \alpha } less than the successor κ + {\displaystyle \kappa ^{+}} of some cardinal number κ {\displaystyle \kappa } can be written as the union of sets X 1 , X 2 , . . . {\displaystyle X_{1},X_{2},...} where X n {\displaystyle X_{n}} is of order type at most κn for n a positive integer.

Proof

The proof is by transfinite induction. Let α {\displaystyle \alpha } be a limit ordinal (the induction is trivial for successor ordinals), and for each β < α {\displaystyle \beta <\alpha } , let { X n β } n {\displaystyle \{X_{n}^{\beta }\}_{n}} be a partition of β {\displaystyle \beta } satisfying the requirements of the theorem.

Fix an increasing sequence { β γ } γ < c f ( α ) {\displaystyle \{\beta _{\gamma }\}_{\gamma <\mathrm {cf} \,(\alpha )}} cofinal in α {\displaystyle \alpha } with β 0 = 0 {\displaystyle \beta _{0}=0} .

Note c f ( α ) ≤ κ {\displaystyle \mathrm {cf} \,(\alpha )\leq \kappa } .

Define:

X 0 α = { 0 } ;     X n + 1 α = ⋃ γ X n β γ + 1 ∖ β γ {\displaystyle X_{0}^{\alpha }=\{0\};\ \ X_{n+1}^{\alpha }=\bigcup _{\gamma }X_{n}^{\beta _{\gamma +1}}\setminus \beta _{\gamma }}

Observe that:

⋃ n > 0 X n α = ⋃ n ⋃ γ X n β γ + 1 ∖ β γ = ⋃ γ ⋃ n X n β γ + 1 ∖ β γ = ⋃ γ β γ + 1 ∖ β γ = α ∖ β 0 {\displaystyle \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 ⋃ n X n α = α {\displaystyle \bigcup _{n}X_{n}^{\alpha }=\alpha } .

Let o t ( A ) {\displaystyle \mathrm {ot} \,(A)} be the order type of A {\displaystyle A} . As for the order types, clearly o t ( X 0 α ) = 1 = κ 0 {\displaystyle \mathrm {ot} (X_{0}^{\alpha })=1=\kappa ^{0}} .

Noting that the sets β γ + 1 ∖ β γ {\displaystyle \beta _{\gamma +1}\setminus \beta _{\gamma }} form a consecutive sequence of ordinal intervals, and that each X n β γ + 1 ∖ β γ {\displaystyle X_{n}^{\beta _{\gamma +1}}\setminus \beta _{\gamma }} is a tail segment of X n β γ + 1 {\displaystyle X_{n}^{\beta _{\gamma +1}}} , then:

o t ( X n + 1 α ) = ∑ γ o t ( X n β γ + 1 ∖ β γ ) ≤ ∑ γ κ n = κ n ⋅ c f ( α ) ≤ κ n ⋅ κ = κ n + 1 {\displaystyle \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
  • How to prove Milner-Rado Paradox? - Mathematics Stack Exchange


  • v
  • t
  • e