Mikołaj Bojańczyk

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 \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.

In particular, we can talk of \cchain-algebras. Such an algebra consists of a universe A, as well  as a multiplication operation

    \[\mult : \cchain A \to A\]

which is associative in the sense of Eilenberg-Moore algebras. The question we ask in this lecture is: how 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.

Shuffles. For a set of letters \Sigma, define a shuffle 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 dense 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. Using the back and forth method one can easily show that every two shuffles of the same set \Sigma are isomorphic. Since chains are considered up to isomorphism, the above lemma justifies talking about the shuffle of \Sigma, an element of \cchain \Sigma, which is unique up to isomorphism, and which is denoted by \shuffle \Sigma.

We are now ready to state the representation theorem for \cchain-algebras.


Theorem. Let \alg be a \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  the operations 

    \[ab,  a^\omega, a^{-\omega}, \shuffle \set{a_1,\ldots,a_n}\]

Let the universe of \alg be  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

    \[\mult w \in  \subalg{A_0} \qquad \mbox{for every }w \in \cchain A_0\]

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.

Lemma 1. Chains in X are closed under binary concatenation, and concatenation indexed by \omega or reverse \omega.

Proof. 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 or in the proof for scattered chains. \Box

Let then w \in \cchain A_0.  To 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. 

Lemma 2. The set E has a maximal element with respect to inclusion (i.e. a maximally coarse equivalence relation).

Proof. 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 for a family of equivalence relations totally ordered by inclusion.) Consider a 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 has countably many positions, we can find equivalence relations

    \[\sim_0 \subseteq \sim_1 \subseteq \cdots\]

in the chain of equivalence relations which have the same union as the entire chain.  Clearly 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 

    \[v = \cdots v_{-2} v_{-1} v_0 v_1 v_2 \cdots\]

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

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.

Lemma 3. 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.

Proof. 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

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.


Leave a Reply

Your email address will not be published.