Thursday, February 7, 2019

The Milner-Rado paradox from walks on ordinals

Let $\kappa$ be a cardinal. The Milner-Rado paradox states:

Every ordinal $\beta<\kappa^+$ can be written as $\bigcup_{n<\omega} X_n$, where $X_n$ is of order-type at most $\kappa^n$.

It's surprising because it goes against our intuition of the pigeonhole principle: the ordinals $\kappa^n$ don't go very far up to $\kappa^+$.


There are some nice short proofs on mathstackexchange. But the one I find easiest to remember uses the method of walks on ordinals. For each $\alpha<\kappa^+$, fix an unbounded set $C_\alpha\subseteq \alpha$ of order-type at most $\kappa$ (and for successor ordinals $\alpha$ this just means that the predecessor must be in $C_\alpha$). Now suppose $\alpha\le\beta$. The walk from $\beta$ to $\alpha$ is a finite sequence decreasing of ordinals $\alpha_0>\alpha_1>\cdots>\alpha_n$ so that $\alpha_0=\beta$, $\alpha_{i+1}=\min(C_{\alpha_i}\setminus \alpha)$, and the walk ends at $\alpha_n=\alpha$. In words, we start from $\beta$ and follow $C_\beta$ down as close to $\alpha$ we can get without overshooting it, then jump to the set indexed by that ordinal and repeat the process. We must eventually get to $\alpha$ by the well-ordering principle, and call $n$ the length of the walk.

Now suppose $\beta<\kappa^+$. Let $X_n$ be the set of $\alpha$ so that the walk from $\beta$ to $\alpha$ has length $n$. A moment's thought shows that $X_n$ has order-type at most $\kappa^n$. So we have proved the Milner-Rado paradox!