# Notes on Recognisable Languages over Monads


In this post, take some notes about Bojańczyk’s paper Recognisable Languages over Monads. These notes are mainly for myself (I find it helpful to write stuff down), so I presuppose some category theory, some formal language theory, and a certain acquaintance with Stone duality. I may write about another approach to profinite monads as codensity monads soon. Or not. We’ll see.

In the following, let $(T \colon \mc C \to \mc C, \mu, \eta)$ be a monad on $\mc C$. A $T$-algebra is an object $A$ of $\mc C$ together with an arrow $e_A \colon TA \to A$ such that

commute. We will write $(A, e_A)$ for this $T$-algebra and occasionally also just$A$. The simplest example of a $T$-algebra is $(TA, \mu_a)$, the free $T$-algebra.
Given two $T$-algebras $(A, e_A)$ and $(B, e_B)$, a $T$-algebra morphism $h \colon (A, e_A) \to (B, e_B)$ is an arrow $h \colon A \to B$ such that

commutes. This data defines a category, the Eilenberg-Moore category $Set^T$ of algebras of $T$ with their morphisms.

Our running example will be the monoid monad $M$ that arises as the composition $UF$ of the adjoint functors $F \colon Set \to Mon$ and $U \colon Mon \to Set$, where $U$ is the forgetful functor and $F$ takes a set $\Sigma$ to the free monoid $F\Sigma = \Sigma^*$ with the usual action on maps. In other words, $MA$ is the set of finite words on $A$. This monad has as its unit $\eta_\Sigma \colon \Sigma \to \Sigma^*$ the embedding of elements from $\Sigma$ as words of length one and as its multiplication the collapsing of finite words of finite words over $\Sigma$ to finite words over $\Sigma$. It is easily seen that the algebras for $M$ are simply monoids, and the $M$-algebra morphisms are monoid homomorphisms: The idea here is that the free monoid consists of all terms that make sense for a monoid and $e_A$ is the evaluation of these terms to elements of the actual monoid $A$. The laws now simply ensure that this evaluation works as you would expect.

Let $(A, e_A)$ be a $T$-algebra and $X$ any object of $\mc C$. An arrow $f \colon A \to X$ (in $\mc C$) is recognized be a $T$-morphism $h \colon (A, e_A) \to (B, e_B)$ if $f = g \circ h$ for some arrow$g \colon B \to X$ in $\mc C$. Such an arrow $f$ is recognized by a $T$-algebra $(B, e_B)$, if there is a $T$-algebra morphism $h \colon (A, e_A) \to (B, e_B)$ that recognizes it. Pictographically:

Note how this generalizes the notion of recognition for monoids: A subset $K$ of a monoid $N$ is recognized by a monoid $N'$ if there exists $K' \subseteq N'$ and a monoid morphism $h \colon N \to N'$ such that $K = h^{-1}(K')$. In our definition above, this is the case of $X = \{0,1\}$ and $f$ as the characteristic function $\chi_K$ of $K$. Any $Set$-arrow $g \colon B \to X$ then defines a subset $g^{-1}(1)$ of $B$, and vice-versa. So $\chi_K = g \circ h$ translates $x \in K$ if $h(x) \in g^{-1}(1)$, therefore $K = h^{-1}(g^{-1}(1))$.

Also, this definition readily implies that all such arrows $f \colon A \to X$ are recognized by $\id_A \colon (A, e_A) \to (A, e_A)$ – which is no problem, since usually we are interested in what arrows can be recognized by ‘finite’ $T$-algebras. Unfortunately, there is no obvious way how to define what finite means for an arbitrary monad. We will presuppose that a sensible choice for finite has been made in the context we are considering. The recognizable arrows of $T$ are then the arrows of $T$ that are recognized by finite algebras.

I will first describe how Bojańczyk extends a monad $T$ on $Set$ to its profinite version $\overline T$.

In the following, let $\mc C = Set$ and let $(A, e_A)$ be a $T$-algebra. A generalized element of $A$ is a map $\tau$ associating to every surjective $T$-algebra morphism $h \colon (A, e_A) \to (B, e_B)$ an element $h^\tau \in B$ such that for every finite $T$-algebra $(C, e_C)$ and $T$-algebra morphism $g \colon (B, e_B) \to (C, e_C)$

The set of all generalized elements of $A$ is written $\bar A$.

The comparison to the case of the free profinite monoid $\widehat{\Sigma^*}$ is illuminating: Seen as the completion of $\Sigma^*$ with the profinite metric, we see that elements of $\widehat{\Sigma^*}$ are either finite words or (equivalence classes of) non-convergent Cauchy-sequences. One of the main points about the profinite completion of $\Sigma^*$ is that any monoid homomorphism $h \colon \Sigma^* \to N$, where $N$ is finite, can be uniquely extended to a uniformly continuous monoid homomorphism $\hat h \colon \widehat{\Sigma^*} \to N$. To define $\hat h$, we set $\hat h(w) = h(w)$ whenever $w \in \Sigma^*$, and if $w = (w_n)_{n\in\mathbf{N}}$ is a Cauchy-sequence, we set $\hat h(w) = \lim_{n \to \infty} h(w_n)$, which must exist by the definition of the profinite metric. We can now turn this upside down and instead consider the elements of $\widehat{\Sigma^*}$ as acting on the morphisms, where each $w \in \widehat{\Sigma^*}$ acts as $h \mapsto \hat h(w)$. In the context of Bojańczyk’s work, $\hat h$ is written $\bar h$ and is defined as $\bar h(\tau) = h^\tau$.

The set $\bar A$ can be equipped with a topology generated by the opens of the form $\{\tau \in \bar A \mid h^\tau = b\}$ with $h \colon (A, e_A) \to (B, e_B)$, $b \in B$, which makes it homeomorphic to the Stone dual $\mc S(\rec(A))$ of the recognizable languages of $A$. Note that the topology of $\mc S(\rec(A))$ is generated by the opens $\{\mc F \in \mc S(\rec(A)) \mid L \in \mc F \}$ with $L \in \rec(A)$. This suggests that is the homemorphism in question.

Bojańczyk calls my generalized elements of $A$ instead $T$-algebra morphism types over $A$ and refers to $\bar A$ as the compactification of $A$. I find this nomenclature confusing, since type has a rather different meaning for me and there are several ways to compactify $A$ as a discrete space.

Now we can define the profinite monad $(\overline T \colon Set \to Set, \bar \mu, \bar \eta)$ for $T$. It acts on sets via $\overline T \Sigma = \overline{T \Sigma}$. The operations $\overline T f$ for $f \colon \Gamma \to \Sigma$, $\bar\eta_\Sigma$, and $\bar\mu_\Sigma$ are completely fixed by requiring that, for each finite $T$-algebra $(A, e_A)$ and each surjective $T$-algebra morphism $h \colon (T\Sigma, e_{T\Sigma}) \to (A, e_A)$, the following diagrams commute:

Since each element $\tau \in \overline T \Sigma$ is defined by its action $h^\tau$ on each $h \colon (T\Sigma, e_{T\Sigma}) \to (A, e_A)$ for each finite $T$-algebra $(A, e_A)$, the diagrams actually define the operations.

Again I think it is helpful to see what this means in the familiar case of the free profinite monoid. The embedding $\bar \eta_\Sigma$ is straight forward and turns a word $w \in \Sigma^*$ into the generalized element $h \mapsto h(w)$, or the principal ultrafilter of $w$, or the constant sequence $(w,w,w,w,\ldots)$, depending on your point of view.
The lifting of functions $f \colon \Gamma \to \Sigma$ is given by $\bar h(\overline Tf(x)) = \overline{h \circ Tf}$, which makes use of the fact that $h \circ Tf \colon (TA, e_{TA}) \to (A, e_A)$ is a monoid homomorphism into a finite monoid that can be extended continously. In terms of profinite words this means that $\overline Tf((w_n)_{n\in\mathbf{N}}) = (Tf(w_n))_{n\in\mathbf{N}}$, since then $\bar h(Tf(w_n)_{n\in\mathbf{N}}) = \lim_{n\to\infty} h(Tf(w_n))$.
The case of the multiplication is less obvious. The right-most diagram states that $\bar h(\bar\mu_\Sigma(x)) = \overline{e_A} \circ \overline T \bar h$. I am still trying to find meaning in this one.