# Notes on Recognisable Languages over Monads

$\require{AMScd} \require{AMSmath} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\id}{\mathrm{id}} \newcommand{\rec}{\mathrm{Rec}}$

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.