Mikołaj Bojańczyk

## 10. All countable chains

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 for the set of all countable chains labelled by alphabet , modulo isomorphism. This forms a monad, with the flattening operation inherited from the monad of all chains.

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

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 -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 and its reverse), as well as a new operation, called the shuffle, defined below.

Shuffles. For a set of letters , define a shuffle of to be a countable chain labelled by which has no endpoints (i.e. has neither least nor greatest positions) and where labels from are dense in the sense that for every positions and every letter , there is some position with label that is between and . Using the back and forth method one can easily show that every two shuffles of the same set are isomorphic. Since chains are considered up to isomorphism, the above lemma justifies talking about the shuffle of , an element of , which is unique up to isomorphism, and which is denoted by .

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

Theorem. Let be a -algebra, and let be a subset of its universe. The subalgebra generated by is equal to the smallest subset of the universe which contains the and is closed under  the operations

Let the universe of be  , and let be some subset. Let be the smallest subset in the statement of the theorem. We need to show that

Define to be those chains such that every infix of has value in . Using this terminology, we need to show that .

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

Proof. For binary concatenation, this is an immediate application of associativity. For concatenation indexed by or its reverse, we use the Ramsey theorem in the same way as in the Wilke lemma or in the proof for scattered chains.

Let then .  To prove the Theorem, we will show that . Define to be the set of those equivalence relations on positions in such that every equivalence class is an interval (i.e. if it contains then it contains all positions between and ), and furthermore the infix given by that interval belongs to . We will show that contains the trivial equivalence relation where all positions are equivalent.

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

Proof. We claim that satisfies the assumptions of the Kuratowski-Zorn Lemma, i.e. every chain of elements in 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 . We claim that the union of all these equivalence relations in the chain (seen as a union of binary relations) also belongs to . Because the  has countably many positions, we can find equivalence relations

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 be an equivalence class of the union, and let be the infix of induced by the equivalence class . Define to be some equivalence class of that is contained in , and define to be the unique equivalence class of which contains . Consider a decomposition

such that is the infix of  induced by , while is the left part induced by and  is the right part. For every , the infix   is contained in an equivalence class of , and therefore belongs to . Using Lemma 1, we conclude that .

To finish the proof of the theorem, we will show that every maximal element of is the trivial equivalence relation with one equivalence class only. Indeed, suppose that has at least two equivalence classes, and is maximal with respect to inclusion. We will talk about the equivalence classes of as a totally ordered set, with the order inherited from the chain . 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 for a dense countable order.

Lemma 3. Let have dense set of positions. Then on some interval, is equal to a shuffle of some subset .

Proof. Take some and some interval in . Either is dense in this interval, or we can find a subinterval where does not appear at all. Iterating this observation through all elements of , we get the lemma.

Define to be the chain whose positions are equivalence classes of , and where the coloring is given by . By assumption that , the coloring only uses colors from . Applying Lemma 3 to , we find an interval which is shuffle of some subset of . That interval can be joined into a single equivalence class, contradicting maximality of .