10. All countable chains

Mikołaj Bojańczyk

zajęcia / courses

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

zajęcia / courses

10. All countable chains

Leave a Reply