{"id":335,"date":"2015-06-12T16:33:00","date_gmt":"2015-06-12T14:33:00","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=335"},"modified":"2017-10-31T13:02:59","modified_gmt":"2017-10-31T12:02:59","slug":"hausdorffs-theorem","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/10-countable-well-founded-chains\/hausdorffs-theorem","title":{"rendered":"Hausdorff’s Theorem"},"content":{"rendered":"

Suppose that\u00a0\"\alpha\" is an ordinal, and for every \"\beta < \alpha\" we have a\u00a0total order\u00a0\"w_\beta\". Then the concatenation of these total orders is a new total order that\u00a0is obtained in the natural way,\u00a0in 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\u00a0easy to see that if we take a concatenation of scattered\u00a0total orders\u00a0that is indexed by an ordinal (or a reverse ordinal), then the result is also a scattered\u00a0total order. Hausdorff proved that this is the only way to get a scattered\u00a0total order, as stated in the following theorem.<\/p>\n

Hausdorff Scattered Chain Theorem. <\/strong>The set\u00a0of countable scattered total orders\u00a0is the smallest set\u00a0of chains which contains singleton orders, and is closed under concatenation indexed by 2, \"\omega\", or the reverse of \"\omega\".<\/p>\n

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\u00a0talk about ordinals too much, but the same proof is easily adapted to the general case.\u00a0The rest of this page is devoted to proving the theorem.<\/p>\n

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\u00a0here<\/a>. The other notion used is that of a\u00a0cut\u00a0<\/em>in a total order: a\u00a0cut\u00a0<\/em>is in a total order \"w\"\u00a0<\/i>is formally defined to be a downward closed set of positions in \"w\". A cut partitions the order into two connected parts: the cut itself, and its complement. A\u00a0nontrivial cut\u00a0<\/em>is one that is neither empty nor full. Cuts will be used a lot later on.<\/p>\n

Lemma.\u00a0<\/strong>One can assign to each countable\u00a0scattered total order\u00a0an ordinal number, called its rank<\/em>, with the following property. For every scattered total order\u00a0\"w\", and every decomposition \"w = w_1 w_2\", at least one of the parts has strictly smaller rank than \"w\".<\/p>\n

Proof.\u00a0<\/strong>Consider the following safety game. There are two players, called Scattered and Dense, respectively. Positions for the\u00a0Dense\u00a0player are countable\u00a0scattered total orders. Positions for player Scattered are scattered total orders with distinguished nontrivial cuts. In a position\u00a0which is a countable scattered total order \"w\", the\u00a0Dense player chooses a cut \"x\", and the game continues from the position \"(w,x)\", which belongs to the Scattered player. If \"w\" 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 \"(w,x)\", the Scattered player chooses either the part before the cut, or the part after the cut, and the game continues from there. \u00a0This is a safety game for player Dense \u2013 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.<\/p>\n

It is not difficult to see that the Dense\u00a0player 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\u00a0Scattered\u00a0player has a winning strategy from every position. Even more (the proof is essentially the same as\u00a0here<\/a>), as in every safety game where all positions are losing for the Dense (safety)\u00a0player, there is a labelling of the game positions with ordinal numbers such that if a position belongs to the Dense\u00a0player, then all outgoing edges move to smaller ordinals, and if a position belongs to the Scattered\u00a0player, then at least one outgoing edge moves to a smaller ordinal. This labelling by ordinals is the one required by the lemma. \"\Box\"<\/p>\n

Proof of the Hausdorff Theorem.\u00a0<\/strong>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\u00a0\"w\", which has some rank thanks to the above lemma. By the lemma, every cut is either a left cut,\u00a0<\/em>which means that the part to the left of the cut has strictly smaller rank than \"w\", or it is a right cut,\u00a0<\/em>which means that the part to the right of the cut has strictly smaller rank than \"w\". \u00a0Define \"x\" to be the supremum of left cuts, which itself is a left cut. \u00a0Define \"x_0\" to be the trivial cut at the beginning of the entire order, and choose some \"\omega\"-sequence of <\/p>\n

  <\/span>   <\/span>\"\[x_1 \le x_2 \le \cdots\]\"<\/p>\n

of left cuts such that the supremum of this sequence is \"x\". (This sequence might be constant if there is a greatest left cut.) Define \"w_n\" to be the part of \"w\" between \"x_{n-1}\" and \"x_n\", and define \"v_n\" to be the part of \"w\" to the left of \"x_n\". Because \"x_n\" is a left cut, \"v_n\" has strictly smaller rank, and therefore the induction assumption can be applied to it to show that it belongs to the set\u00a0in the statement of the theorem. The order \"w_n\" is a suffix of \"v_n\", 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 \"x\" can be decomposed as a concatenation, indexed by \"\omega\", of orders for which the theorem is true. The right part of \"x\" is treated in an symmetric, but\u00a0slightly\u00a0simpler way \u2013 because \"x\" was chosen as a supremum of left cuts, every cut to the right of \"x\" is a right cut, and therefore can be seen as an infimum of a sequence of right cuts. \"\Box\"<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Suppose that\u00a0 is an ordinal, and for every we have a\u00a0total order\u00a0. Then the concatenation of these total orders is a new total order that\u00a0is obtained in the natural way,\u00a0in 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":327,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-335","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/335"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=335"}],"version-history":[{"count":5,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/335\/revisions"}],"predecessor-version":[{"id":1407,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/335\/revisions\/1407"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/327"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}