From Wikipedia, the free encyclopedia
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.
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}}