{"id":1062,"date":"2016-05-18T17:11:47","date_gmt":"2016-05-18T15:11:47","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1062"},"modified":"2017-10-31T13:05:09","modified_gmt":"2017-10-31T12:05:09","slug":"all-countable-chains-a-new-proof","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/all-countable-chains-a-new-proof","title":{"rendered":"10. All countable chains"},"content":{"rendered":"

In the previous lecture<\/a>, we talked about scattered countable chains. The benefit of scattered chains is that one can use the Hausdorff theorem<\/a>, which decomposes every scattered chain into simpler blocks in a well-founded way, enabling induction. In this lecture, we study arbitrary countable chains, where we cannot apply the Hausdorff theorem. Let us write \"\cchain \Sigma\" for the set of all countable chains labelled by alphabet \"\Sigma\", modulo isomorphism. This forms a monad, with the flattening operation inherited from the monad of all chains.<\/p>\n

In particular, we can talk of \"\cchain\"-algebras. Such an algebra consists of a universe \"A\", as well \u00a0as a multiplication operation <\/p>\n

  <\/span>   <\/span>\"\[\mult : \cchain A \to A\]\"<\/p>\n

which is associative in the sense of Eilenberg-Moore algebras. The question we ask in this lecture is:\u00a0how one can represent such an algebra? It turns out that, like for the previous kinds of algebras, a \"\cchain\"-algebra is uniquely determined by a small subset of operations. These are the same operations as used for scattered chains (binary concatenation, and powers indexed by \"\omega\" and its reverse), as well as a new operation, called the shuffle, defined below.<\/p>\n

Shuffles.\u00a0<\/b>For a set of letters \"\Sigma\", define a\u00a0shuffle\u00a0<\/em>of \"\Sigma\" to be a countable chain labelled by \"\Sigma\" which has no endpoints (i.e. has neither least nor greatest positions) and where labels from \"\Sigma\" are\u00a0dense in the sense that for every positions \"x < y\" and every letter \"a \in \Sigma\", there is some position with label \"a\" that is between \"x\" and \"y\".\u00a0Using the back and forth method<\/a>\u00a0one can easily show that every two shuffles of the same set \"\Sigma\" are isomorphic.\u00a0Since chains are considered up to isomorphism, the above lemma justifies talking about\u00a0the shuffle\u00a0<\/em>of \"\Sigma\", an element of \"\cchain \Sigma\", which is unique up to isomorphism, and which is denoted by \"\shuffle \Sigma\".<\/p>\n

We are now ready to state the representation theorem for \"\cchain\"-algebras.<\/p>\n

 <\/p>\n

Theorem. <\/strong>Let \"\alg\" be a\u00a0\"\cchain\"-algebra, and let \"A_0\" be a subset of its universe. The subalgebra generated by \"A_0\" is equal to the smallest subset of the universe which contains the \"A_0\" and is closed under \u00a0the operations\u00a0<\/p>\n

  <\/span>   <\/span>\"\[ab, a^\omega, a^{-\omega}, \shuffle \set{a_1,\ldots,a_n}\]\"<\/p>\n

Let the universe of \"\alg\" be \u00a0\"A\", and let \"A_0\" be some subset. Let \"\subalg{A_0}\" be the smallest subset in the statement of the theorem. We need to show that<\/p>\n

  <\/span>   <\/span>\"\[\mult w \in \subalg{A_0} \qquad \mbox{for every }w \in \cchain A_0\]\"<\/p>\n

Define \"X\" to be those chains \"w \cchain A_0\" such that every infix of \"w\" has value in \"\subalg{A_0}\". Using this terminology, we need to show that \"X = \cchain A_0\".<\/p>\n

Lemma 1.\u00a0<\/strong>Chains in \"X\" are closed under binary concatenation, and concatenation indexed by \"\omega\" or reverse \"\omega\".<\/p>\n

Proof. <\/strong>For binary concatenation, this is an immediate application of associativity. For concatenation indexed by \"\omega\" or its reverse, we use the Ramsey theorem in the same way as in the Wilke lemma<\/a> or in the proof for scattered chains<\/a>. \"\Box\"<\/p>\n

Let then \"w \in \cchain A_0\". \u00a0To prove the Theorem, we will show that \"w \in X\". Define \"E\" to be the set of those equivalence relations on positions in \"w\" such that every equivalence class is an interval (i.e. if it contains \"x<y\" then it contains all positions between \"x\" and \"y\"), and furthermore the infix given by that interval belongs to \"X\". We will show that \"E\" contains the trivial equivalence relation where all positions are equivalent.\u00a0<\/span><\/p>\n

Lemma 2.\u00a0<\/strong>The set \"E\" has a maximal element with respect to inclusion (i.e. a maximally coarse equivalence relation).<\/p>\n

Proof.\u00a0<\/strong>We claim that \"E\" satisfies the assumptions of the Kuratowski-Zorn Lemma, i.e. every chain of elements in \"E\" has an upper bound. (In this proof, and this proof only, we use the word chain<\/em> for a family of equivalence relations totally ordered by inclusion.)\u00a0Consider\u00a0a chain of equivalence relations in \"E\". We claim that the union of all these equivalence relations in the chain (seen as a union of binary relations) also belongs to \"E\". Because the \"w\"\u00a0has countably many positions, we can find equivalence relations <\/p>\n

  <\/span>   <\/span>\"\[\sim_0 \subseteq \sim_1 \subseteq \cdots\]\"<\/p>\n

in the chain of equivalence relations which have the same union as the entire chain. \u00a0Clearly the union of a chain of equivalence relations is itself an equivalence relation. Also, its equivalence classes are intervals. Let then \"C\" be an equivalence class of the union, and let \"v\" be the infix of \"w\" induced by the equivalence class \"C\". Define \"C_0\" to be some equivalence class of \"\sim_0\" that is contained in \"C\", and define \"C_{i+1}\" to be the unique equivalence class of \"\sim_{i+1}\" which contains \"C_i\". Consider a decomposition\u00a0<\/p>\n

  <\/span>   <\/span>\"\[v = \cdots v_{-2} v_{-1} v_0 v_1 v_2 \cdots\]\"<\/p>\n

such that \"v_0\" is the\u00a0infix of \"w\"\u00a0induced by \"C_0\", while \"v_{-i}\" is the left part induced by \"C_i-C_{i-1}\" and\u00a0\"v_{i}\" is the right part. For every \"i \in \mathbb Z\", the infix\u00a0\u00a0\"v_i\" is contained in an\u00a0equivalence class of \"\sim_{|i|}\", and therefore belongs to \"X\". Using Lemma 1, we conclude that \"v \in X\". \"\Box\"<\/p>\n

To finish the proof of the theorem, we will show that every maximal element of \"E\" is the trivial equivalence relation with one equivalence class only. Indeed, suppose that \"\sim \in E\" has at least two equivalence classes, and is maximal with respect to inclusion. We will talk about the equivalence classes of \"\sim\" as a totally ordered set, with the order inherited from the chain \"w\". There cannot be two consecutive equivalence classes, because otherwise we could join them using Lemma 1 and thus contradict maximality. Therefore the equivalence classes of \"\sim\" for a dense countable order.<\/p>\n

Lemma 3.\u00a0<\/strong>Let \"u \in \cchain A\" have dense set of positions. Then on some interval, \"u\" is equal to a shuffle of some subset \"B \subseteq A\".<\/p>\n

Proof.\u00a0<\/strong>Take some \"a \in A\" and some interval in \"u\". Either \"a\" is dense in this interval, or we can find a subinterval where \"a\" does not appear at all. Iterating this observation through all elements of \"A\", we get the lemma. \"\Box\"<\/p>\n

Define \"u\" to be the chain whose positions are equivalence classes of \"\sim\", and where the coloring is given by \"\mult \alg\". By assumption that \"\sim \in E\", the coloring only uses colors from \"\subalg {A_0}\". Applying Lemma 3 to \"u\", we find an interval which is shuffle of some subset of \"A_0\". That interval can be joined into a single equivalence class, contradicting maximality of \"E\".<\/p>\n","protected":false},"excerpt":{"rendered":"

In the previous lecture, we talked about scattered countable chains. The benefit of scattered chains is that one can use the Hausdorff theorem, which decomposes every scattered chain into simpler blocks in a well-founded way, enabling induction. In this lecture, we study arbitrary countable chains, where we cannot apply the Hausdorff theorem. Let us write […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":42,"menu_order":2,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1062","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1062"}],"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=1062"}],"version-history":[{"count":20,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1062\/revisions"}],"predecessor-version":[{"id":1409,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1062\/revisions\/1409"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/42"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1062"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}