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

  • $\begingroup$ Thank you very much for the clarification about the order. Unfortunately, I am still unable to complete the proof. But still working on it. $\endgroup$ – Ali Kare Dec 5 '12 at 10:07
  • $\begingroup$ @Ali: If you can post his statement of the M-R theorem and his hints for this proof, I’ll take a look. $\endgroup$ – Brian M. Scott Dec 5 '12 at 10:24
  • $\begingroup$ I added his statement to my original post. $\endgroup$ – Ali Kare Dec 5 '12 at 11:59
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Dec 10 '12 at 9:40
  • $\begingroup$ 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.$$ $\endgroup$ – Ali Kare Dec 13 '12 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.