4
$\begingroup$

Exercise 3.17 on page 136 asks to prove the Milner-Rado paradox. Levy gives hints for two different proofs. I have no problem with the first one but I do not understand the ordering he mentions in the second one.

Let $\alpha$ be an infinite cardinal. Let $X$ be the set of all finite sequences of elements of $\alpha$. Define an order $<_l$ on $X$ by setting, for $p,q \in X$:

$p <_l q$ if $p\subset q$ or neither of $p$ and $q$ is included in the other and $p$ precedes $q$ lexicographically.

(Note that in the errata given in the Dover edition, '$\subseteq$' is changed to '$\subset$' as I have written above.)

Is it not true that

$$01,002,0003,00004, \ldots $$

is an infinite strictly decreasing sequence w.r.t. $<_l$ ? For example, $002$ is bigger than $0003$ because at the first position they differ, $002$ has $2 $ and $0003$ has $0$. So $002$ is bigger than $0003$.

If the sequence given above is an infinite strictly decreasing sequence w.r.t. $<_l$, then $<_l$ is not a well-order on $X$. But Levy talks about the order type of $(X,<_l)$ as if it is a well-order.

What am I missing here?

Added Dec 5

Here are the related parts from Levy's book.

(p. 136) Exercise 3.17. (Milner and Rado 1965) Let $\alpha$ be an aleph. For every ordinal $\beta$ such that $\beta<\alpha^{+}$ there are subsets, $A_n\subseteq \beta$, for $n<\omega$, such that $\mbox{Ord}(A_n)\leq \alpha^{\cdot n}$ and $\beta = \bigcup_{n < \omega} A_n$.

(p. 137) Hint. ... An alternative proof which sheds some more light on the matter can be obtained as follows. If $\sigma$ and $\tau$ are order types we say that $\sigma \leq \tau$ if there is an ordered set $\langle t, <\rangle$ and a subset $s$ of $t$ such that $\mbox{Ord}(\langle t, <\rangle) = \tau$ and $\mbox{Ord}(\langle s, <\rangle) = \sigma$. Define an order $<_l$ on $\mbox{}^{<\omega}\alpha$ by setting, for $p,q\in \mbox{}^{<\omega}\alpha$, $p<_l q$ if $p\subset q$ or if neither of $p$ and $q$ is included in the other and $p$ precedes $q$ lexicographically. Let $\lambda = \mbox{Ord}(\langle \mbox{}^{<\omega}\alpha , <_l \rangle)$, then we have $\lambda \cdot \alpha \leq \lambda$. Use this to prove by induction on $\beta<\alpha^{+}$ that $\beta\leq \lambda$.

(p. 108) Definition 4.20. For a class $A$ and an ordinal $\alpha$, $\mbox{}^{<\alpha}A$ is the set of all functions on ordinals $\beta<\alpha$ into $A$, that is, $$\mbox{}^{<\alpha}A = \{ f | (\exists \beta < \alpha) f: \beta\longrightarrow A\}.$$

  • 1
    You probably meant to write $00004$ (that is **four** zeros), but you wrote $0004$ instead.2012-11-28
  • 0
    Fixed it. Thanks.2012-11-28
  • 0
    A dumb question, why is this called a paradox?2012-12-01
  • 0
    Mathematicians use paradox for surprising and unexpected results (for example Banach–Tarski paradox, Skolem's paradox). Milner-Rado paradox fails for finite unions. I guess that is why the infinite case is unexpected.2012-12-05

1 Answers 1