9. Countable scattered chains

Mikołaj Bojańczyk

zajęcia / courses

Chains and total orders. A total order is a set $X$ together with an ordering $\le$ which is total (also known as linear) in the sense that every two elements are comparable. Define a chain over an alphabet $\Sigma$ to be a nonempty totally ordered set with a labelling of its elements by $\Sigma$ . We consider chains up to isomorphism, i.e. we identify two chains if there is a bijection between their positions that preserves the order and labelling. We write $\cmonad \Sigma$ for the (class) of all chains over the alphabet $\Sigma$ .

There is a natural monad structure on chains. If $f : \Sigma \to \Gamma$ is a function on alphabets, then its lifting to chains

$\cmonad f : \cmonad \Sigma \to \cmonad \Gamma$

is defined coordinate-wise in the obvious way, by keeping positions unchanged and applying $f$ only to the labels. The unit operation

$\unit : \Sigma \to \cmonad \Sigma$

sends a label to the one-element chain with this label, and the flattening operation

$\flatt \Sigma : \cmonad\ \cmonad\ \Sigma \to \cmonad\ \Sigma$

defined in the natural way. The formal definition of flattening involves lexicographic product of orderings. One can check that all axioms of a monad are satisfied.

There are two problems with the chain monad defined above. The first problem is that $\cmonad \Sigma$ is not a set, but a class. The second problem is that the algebras for this monad can be very complicated. A corollary of a result of Shelah is that there are algebras with finite universes over this monad where it is undecidable if an element is generated by a set of other elements. (A precise formulation of this result would require some space, not to mention the proof, and is omitted.) For these vaguely sketched reasons, we will concentrate on submonads of the chain monads, where not all chains are used. We will consider the following special cases, all of which are countable chains: finite chains, countable chains that are well-founded, countable chains that are scattered, and finally all countable chains.

The case of finite chains is the case of semigroups. The remaining cases are studied in the following lectures. We begin with scattered countable chains, and their special case of well-founded countable chains.

Scattered chains.

Call a chain scattered if one cannot remove positions and end up with a chain indexed by the rational numbers. For example, any chain indexed by the integers is scattered. The following lemma, whose straightforward proof is omitted, says that scattered chains (also, countable chains and well-founded chains) are closed under the flattening operation as defined for the monad of chains.

Lemma. If $w \in \cmonad \cmonad \Sigma$ is scattered, and every position of $w$ is labelled by a scattered chain, then also the flattening of $w$ is scattered. Same for countable and well-founded chains.

A corollary of the above lemma is that if we define $\scat \Sigma$ to be the restriction of the chain monad $\cmonad \Sigma$ to scattered countable chains, with the unit and flattening restricted to the smaller domain of scattered countable chains, then it is also a monad. In this sense, $\scat$ is a submonad of $\cmonad$ .

Theorem. A $\scat$ -algebra $\alg$ with finite universe $A$ is uniquely determined by the values of its multiplication operation on structures of the form

$ab, a^\omega, a^{-\omega} \in \scat A \qquad \mbox{with $a,b \in A$}$

Proof. In the proof of this theorem, we pay pedantic attention to the distinction between a chain of chains and its flattening. In later proofs, we will not be so precise. If $u_1,\ldots,u_n$ are chains in $\scat A$ , then we write $u_1 \cdots u_n$ for the chain of chains which has $n$ positions, where the $i$ -th position is labelled by $u_i$ . To get the actual concatenation of these chains, we need to apply the flattening operation. Likewise, we write $u_1 u_2 \cdots$ for an $\omega$ -chain of chains.

The key lemma is Hausdorff’s theorem, which characterizes countable scattered chains as those that can be constructed from singleton chains using concatenation indexed by the two-element chain, $\omega$ or the reverse of $\omega$ . The theorem says that for every set of labels $\Sigma$ , one can assign ordinal numbers (call them Hausdorff ranks) to $\scat \Sigma$ , such that for every chain $w \in \scat \Sigma$ with at least two positions there exists a decomposition of at least one of three types listed below:

(1) $\begin{eqnarray*} w &=& \flatt A(w_1 w_2) \\ w &=& \flatt A(w_1 w_2 \cdots) \\ w &=& \flatt A(\cdots w_2 w_1) \end{eqnarray*}$

such that the chains $w_i$ on the right side have strictly smaller rank than $w$ .

We now proceed with the proof of the theorem. Let $A$ be a finite set. We need to show that if we have two Eilenberg-Moore algebras with this universe, which have multiplication operations

$\mult 1, \mult 2 : \scat A \to A$

that agree on the structures mentioned in the statement of the theorem, then the two multiplication operations are the same.

When $w$ is a chain of size one, then both $\mult 1 (w)$ and $\mult 2 (w)$ need to be the label used in the chain, by the axiom of Eilenberg-Moore algebras which says that multiplication composed with the unit must be the identity.

Suppose now that $w \in \scat A$ is a chain of size at least two. We will prove that

$\mult 1 (w) = \mult 2 (w)$

by induction on the Hausdorff rank of $w$ .

Let us first consider the case when $w$ admits a decomposition

$w =\flatt A(w_1 w_2)$

In this case we simply apply induction and use the assumption that the multiplication operations agree on chains of length two:

$\begin{eqnarray*} \mult 1 (w) &=& \\ \mult 1 (\flatt A (w_1 w_2)) & = & \mbox{by associativity} \\ \mult 1 (\mult 1 (w_1) \mult 2(w_2)) &= & \mbox{by induction assumption} \\ \mult 1 (\mult 2 (w_1) \mult 2 (w_2)) &=& \mbox{because $\mult 1$ and $\mult 2$ agree on chains of length two} \\ \mult 2 (\mult 2(w_1) \mult 2 (w_2) & = & \\ \mult 2 (w) \end{eqnarray}$

Consider now the case when $w$ admits a decomposition

$w =\flatt A(w_1 w_2 \cdots)$

Here we apply the Ramsey theorem. For numbers $i < j$ , define

$w_{ij} = w_i w_{i+1} \cdots w_{j-1} \in \scat \scat A$

By induction assumption, and using the same argument as in the previous paragraph, we see that

$\mult 1 (w_{ij}) = \mult 2 (w_{ij}) \qquad \mbox{for every $i < j$}.$

Let us write $a_{ij} \in A$ for the element described by both sides of the above equality. By the Ramsey theorem, there is some infinite set of natural numbers $I$ such that all $a_{ij}$ with $i<j \in I$ are the same element, call it $a \in A$ . Using associativity, we see that

$\mult 1 (w) = \mult 1 (a_{1 i_1} a_{i_1 a_2} a_{i_2 i_3} \cdots ) = \mult 1 (a_{1 i_1} \mult 1(a^\omega))$

Since the right side only depends on arguments where $\mult 1$ and $\mult 2$ are known to agree, the result follows.

The same proof as in the previous paragraph is used for the last kind of decomposition, indexed by reverse $\omega$ . $\Box$

Well-founded chains. Call a chain well-founded if its set of positions is well founded. This is a special case of a scattered chain. As for scattered countable chains, countable well-founed chains form a monad, call it $\cwf$ .

Theorem. A $\cwf$ -algebra $\alg$ is uniquely determined by the values of its multiplication operation on structures of the form

$ab, a^\omega \in \cwf A \qquad \mbox{with $a,b \in A$}$

Proof. The same proof as for the monad $\scat$ . When applying the Hausdorff theorem, we can never get a decomposition indexed by reverse $\omega$ , since this would contradict well-foundedness. $\Box$

zajęcia / courses

9. Countable scattered chains

Leave a Reply