# An exercise from Levy's Basic Set Theory (Exercise 3.17)

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?

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

-
You probably meant to write $00004$ (that is four zeros), but you wrote $0004$ instead. –  Asaf Karagila Nov 28 '12 at 20:28
Fixed it. Thanks. –  Ali Kare Nov 28 '12 at 20:31
A dumb question, why is this called a paradox? –  Metta World Peace Dec 1 '12 at 12:30
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. –  Ali Kare Dec 5 '12 at 11:58

I strongly suspect that reverse lexicographic order is intended here. Let $\mathscr{F}$ be the set of functions from $\omega$ to $\alpha$ having finite support, and let $\preceq$ be the reverse lexicographic order on $\mathscr{F}$, so that $f\prec g$ iff $f(n)<g(n)$ for the largest $n$ at which $f$ and $g$ differ. Then the order type of $\langle\mathscr{F},\preceq\rangle$ is the ordinal exponential $\alpha^\omega$. (See here, for instance.)

If the lexicographic component of $<_l$ is reverse lexicographic order, the set of finite sequences of elements of $\alpha$ ordered by $<_l$ is just $\langle\mathscr{F},\preceq\rangle$ with each point replaced by a copy of $\omega$: the finite sequences $\langle 1\rangle,\langle 1,0\rangle,\langle 1,0,0\rangle,\dots$ all correspond to the function $f:\omega\to\alpha$ such that $f(0)=1$ and $f(n)=0$ for $n>0$.

Added: As suggested above, I take $<_l$ to be reverse lexicographic order, so that setting $\lambda=\operatorname{Ord}\big(\langle{^{<\omega}\alpha},\le_l\rangle\big)$ makes sense. Notationally I’ll treat elements of ${^{<\omega}\alpha}$ as finite sequences. Let $$\varphi:{^{<\omega}\alpha}\times\alpha\to{^{<\omega}\alpha}:\langle\sigma,\xi\rangle\mapsto\sigma^\frown\xi\;,$$ where $\sigma^\frown\xi$ is the concatenation of $\sigma$ with $\langle\xi\rangle$. It’s straightforward to check that $\sigma^\frown\xi<_l\tau^\frown\eta$ iff $\xi<\eta$, or $\xi=\eta$ and $\sigma<_l\tau$, so $\varphi$ is strictly order-preserving, ${^{<\omega}\alpha}\times\alpha\preceq{^{<\omega}\alpha}$, where I write $\sigma\preceq\tau$ to mean that the order type $\sigma$ embeds in the order type $\tau$, and hence $\lambda\cdot\alpha\preceq\lambda$.

If there is some ordinal less than $\alpha^+$ that does not embed in $\lambda$, let $\beta$ be the least such ordinal. If $\beta=\gamma+1$, then $\gamma\preceq\lambda$, so $\beta\preceq\gamma\cdot2\preceq\lambda\cdot\alpha\preceq\lambda$, contradicting the choice of $\beta$. Otherwise, let $\kappa=\operatorname{cf}\beta$, and let $\langle\gamma_\xi:\xi<\kappa\rangle$ be a cofinal sequence in $\beta$. Then $\gamma_\xi\preceq\lambda$ for each $\xi<\kappa$, and $\kappa\le\alpha$, so $\beta\preceq\lambda\cdot\kappa\preceq\lambda\cdot\alpha\preceq\lambda$, again contradicting the choice of $\beta$. Thus, $\beta\preceq\lambda$ for all $\beta<\alpha^+$.

Finally, $\operatorname{Ord}\left(\left\langle{^{\le n}\alpha},<_l\right\rangle\right)=\alpha^n$ for each $n\in\omega$, and ${^{<\omega}\alpha}=\bigcup_{n\in\omega}\left({^{\le n}\alpha}\right)$. Thus, if $\varphi$ is an embedding of $\beta<\alpha^+$ into ${^{<\omega}\alpha}$, the sets $A_n=\varphi^{-1}\left[{^{\le n}\alpha}\right]$ are as desired.

-
Thank you very much for the clarification about the order. Unfortunately, I am still unable to complete the proof. But still working on it. –  Ali Kare Dec 5 '12 at 10:07
@Ali: If you can post his statement of the M-R theorem and his hints for this proof, I’ll take a look. –  Brian M. Scott Dec 5 '12 at 10:24
I added his statement to my original post. –  Ali Kare Dec 5 '12 at 11:59
@Ali: I apologize for having taken so long to get to this, but I’ve now added the argument that I think Levy had in mind. –  Brian M. Scott Dec 10 '12 at 9:40
Thank you for your help. Unfortunately, I fail to see why $\varphi$ is order-preserving. Let $\sigma = (5,5,5,5)$, $\tau = (1,1)$, $\xi = 1$, $\eta = 3$. Now $\xi < \eta$ but $\sigma^\frown \xi <_l \tau^\frown \eta$ fails to hold. Indeed, $$\tau^\frown \eta = (1,1,3) <_l (5,5,5,5,1) = \sigma^\frown \xi.$$ –  Ali Kare Dec 13 '12 at 14:39