Mikołaj Bojańczyk

## Hausdorff’s Theorem

Suppose that is an ordinal, and for every we have a total order . Then the concatenation of these total orders is a new total order that is obtained in the natural way, in the same way as flattening for the chain monad. Likewise, we can do concatenation indexed by a reverse ordinal (i.e. the a total order obtained by reversing the order in some ordinal). It is easy to see that if we take a concatenation of scattered total orders that is indexed by an ordinal (or a reverse ordinal), then the result is also a scattered total order. Hausdorff proved that this is the only way to get a scattered total order, as stated in the following theorem.

Hausdorff Scattered Chain Theorem. The set of countable scattered total orders is the smallest set of chains which contains singleton orders, and is closed under concatenation indexed by 2, , or the reverse of .

Actually, Hausdorff proved the result for all scattered total orders, not only countable ones, in which case the statement needs to talk about arbitrary ordinals. We do the countable case just so that we do not need to talk about ordinals too much, but the same proof is easily adapted to the general case. The rest of this page is devoted to proving the theorem.

We only prove the more difficult left-to-right inclusion in the statement of the theorem. We use the following lemma, which uses safety games, as described here. The other notion used is that of a cut in a total order: a cut is in a total order is formally defined to be a downward closed set of positions in . A cut partitions the order into two connected parts: the cut itself, and its complement. A nontrivial cut is one that is neither empty nor full. Cuts will be used a lot later on.

Lemma. One can assign to each countable scattered total order an ordinal number, called its rank, with the following property. For every scattered total order , and every decomposition , at least one of the parts has strictly smaller rank than .

Proof. Consider the following safety game. There are two players, called Scattered and Dense, respectively. Positions for the Dense player are countable scattered total orders. Positions for player Scattered are scattered total orders with distinguished nontrivial cuts. In a position which is a countable scattered total order , the Dense player chooses a cut , and the game continues from the position , which belongs to the Scattered player. If has at most one position, then it has no nontrivial cuts, and therefore the Dense player loses immediately for the lack of a possible move. In a position , the Scattered player chooses either the part before the cut, or the part after the cut, and the game continues from there.  This is a safety game for player Dense – if a play continues forever, then player Dense wins; the only way for player Scattered to win is for the play to reach a total order of size at most one.

It is not difficult to see that the Dense player cannot have a winning strategy from any position, since such a winning strategy would demonstrate an embedding of the rational numbers into that position. Therefore by determinacy of safety games, the Scattered player has a winning strategy from every position. Even more (the proof is essentially the same as here), as in every safety game where all positions are losing for the Dense (safety) player, there is a labelling of the game positions with ordinal numbers such that if a position belongs to the Dense player, then all outgoing edges move to smaller ordinals, and if a position belongs to the Scattered player, then at least one outgoing edge moves to a smaller ordinal. This labelling by ordinals is the one required by the lemma. Proof of the Hausdorff Theorem. Given the above lemma, we prove the non-obvious left-to-right inclusion in the Hausdorff Theorem by induction on these ranks. Consider a countable scattered total order , which has some rank thanks to the above lemma. By the lemma, every cut is either a left cut, which means that the part to the left of the cut has strictly smaller rank than , or it is a right cut, which means that the part to the right of the cut has strictly smaller rank than .  Define to be the supremum of left cuts, which itself is a left cut.  Define to be the trivial cut at the beginning of the entire order, and choose some -sequence of of left cuts such that the supremum of this sequence is . (This sequence might be constant if there is a greatest left cut.) Define to be the part of between and , and define to be the part of to the left of . Because is a left cut, has strictly smaller rank, and therefore the induction assumption can be applied to it to show that it belongs to the set in the statement of the theorem. The order is a suffix of , and therefore it must also belong to the set of in the statement of the lemma, because that set is closed under removing positions. This shows that the part to the left of can be decomposed as a concatenation, indexed by , of orders for which the theorem is true. The right part of is treated in an symmetric, but slightly simpler way – because was chosen as a supremum of left cuts, every cut to the right of is a right cut, and therefore can be seen as an infimum of a sequence of right cuts. 