Mikołaj Bojańczyk

Recall that a monoid consists of a universe M together with a product operation

    \[\pi : M^* \to M\]

which maps each one letter word m  to m, and which is associative in the sense that the following diagram commutes

    \[\xymatrix{(M^*)^* \ar[r]^{flat} \ar[d]_{\pi^*} & M^* \ar[d]^\pi \\ M^* \ar[r]_\pi & M}\]

where flat flattens a word of words into a word in the obvious way, while \pi^* applies the product operation to every word in a word of words.

To define monoids for infinite words, we use the same definition, only * is replaced by \infty. This requires a new flattening operation

    \[\mathrm{flat} : (M^\infty)^\infty \to M^\infty\]

which we illustrate on three examples:

    \begin{eqnarray*} (aba) (\epsilon) (aa) (b) & \quad \mapsto \quad & abaaab \\ (aaa \cdots) (bbb \cdots) & \quad \mapsto \quad & aaa \cdots \\ (\epsilon) (\epsilon) (\epsilon) & \quad \mapsto \quad & \epsilon \end{eqnarray*}

Note how in the second example above, the first infinite word causes the rest of the input to be ignored. This ignoring is a little bit of a hack, which could be avoided by either using two sorts (finite and infinite word), or by considering a richer notion of words which is closed under substitution, e.g. words where the positions form a countable well-ordering.

Summing up, \infty-monoids are defined below.

Definition.  An \infty-monoid consists of a unierse M together with a product operation

    \[\pi : M^\infty \to M\]

which is the identity on one letter words and which is associative in the sense that the following diagram commutes 

    \[\xymatrix{(M^\infty)^\infty \ar[r]^{flat} \ar[d]_{\pi^\infty} & M^\infty \ar[d]^\pi \\ M^\infty \ar[r]_\pi & M}\]


It is not difficult to see that \Sigma^\infty, with flattening as the monoid operation, is an \infty-monoid. Here is an example of an \infty-monoid with a finite universe.


Example. This \infty-monoid is going to recognize the \infty-words over alphabet \set{a,b} which contain infinitely many a‘s. The  universe is 

    \[M = \set{\epsilon, a, b, a^\omega, b^\omega}\]

 The product operation is defined as follows. To define \pi(w) with w \in M^\infty, we do the following. First, remove all \epsilon letters from w. If the result is empty, return \epsilon.  If there is a letter of the form  a^\omega or b^\omega, then return the a^\omega or b^\omega, whichever comes first in w. Otherwise, if the result is an infinite word, then return a^\omega if there are infinitely many a‘s and b^\omega otherwise. Otherwise, return a if there is at least one a and b otherwise. \Box


Homomorphism. Define a homomorphism of \infty-monoids M and N to be a function h between their universes which respects the structure of \infty-morphisms in the sense that the following diagram commutes

    \[\xymatrix{M^\infty \ar[r]^{h^\infty} \ar[d]_{\pi_M} & N^\infty \ar[d]^{\pi_N} \\ M \ar[r]^h & N}\]


Compositional functions. As with normal monoids, instead of defining an associative product operation on a universe N, it is sometimes easier to give a compositional function from an existing \infty-monoid to N, and get the \infty-monoid structure on N automatically from that. We describe this now. Suppose that M is an \infty-monoid and N is a set. A function

    \[h : M \to N\]

is called compositional if every words w,v \in M^\infty satisfy

    \[h^\infty(w) = h^\infty(v) \qquad \text{implies} \qquad h(\pi(w)) = h(\pi(v))\]


Lemma. If h : M \to N is compositional, then there is a multiplication operation on N which turns it into an \infty-monoid, and which turns h into a homomorphism of \infty-monoids.

Proof. Compositionality can be rephrased as saying that there is some function \sigma which makes the following diagram commute

    \[\xymatrix{M^\infty \ar[r]^{h^\infty} \ar[d]_{\pi} & N^\infty \ar[d]^\sigma \\ M \ar[r]^h & N}\]

The above diagram then shows that h is a homomorphism, assuming that \sigma yields a structure of an \infty-monoid on N, i.e. it is associative. Associativity is not difficult to show. \Box




Leave a Reply

Your email address will not be published.