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
.
Leave a Reply