Adjunctions between monoids

In the last post, I talked about Monads on Monoids. We defined these by turning each monoid into a category (its delooping), and then looking at monads on this category. This data could then be reexpressed in terms of the original monoid.

We can also apply exactly the same process to define adjunctions between monoids. These were studied by Vladimir Molotkov in his paper ‘Adjunction in Monoids‘.

Definition 1

An adjuction from a monoid $M$ to a monoid $N$ consists of homomorphisms $\lambda:M\to N$ and $\rho:N\to M$ along with elements $h\in M$ and $e\in N$ such that

\begin{align} &&\rho(e)h&=1_M,\tag{1}\\ &&e\lambda(h)&=1_N,\tag{2}\\ &\forall x\in M:&\rho(\lambda(x))h&= hx,\tag{3}\\ &\forall y\in N:& e\lambda(\rho(y))&= ye.\tag{4} \end{align}

The homomorphisms $\lambda$ and $\rho$ correspond to the functors of the adjunction. The elements $h$ and $e$ are the unit and the counit natural transformations. Axioms (1) and (2) are the axioms of the adjunction, and axioms (3) and (4) are the naturality axioms for $h$ and $e$.

Relation to monads

In the case of general categories, adjunctions are closely connected to monads. For every adjunction between two categories we may compose the two functors to obtain a monad. For each monad there might be many adjunctions that compose to it, but there are two canonical such adjunctions: one with the category of modules (the Eilenberg-Moore category) and one with the category of free modules (the Kleisli category).

The case of adjunctions and monads on monoids turns out to be much simpler. Note that the Eilenberg-Moore category of a monad on a monoid needn’t itself be the delooping of a monoid (as we saw last time). But $\mathbf BM$ only has one object, so there is only one free module. Therefore the Kleisli category is always the delooping of some monoid, since it only has one object.

It turns out that this is the only adjunction between monoids that composes to produce the given monad. For any monad on a monoid there’s exactly one adjunction of monoids that composes to give it, the Kleisli adjunction. The Eilenberg-Moore category either has more than one object (as we saw in last time’s Example 5) or it’s isomorphic to the Kleisli category (as we saw in Example 3).

This is proven in Molotkov’s paper. But he seems not to realise what he’s done! He’s merely trying to rearrange Definition 1 into an equivalent form that only involves $M$ and not $N$. But he eventually arrives at his Proposition 4, which you can check is identical to our definition we gave for ‘monad on a monoid’. But he never states that this is precisely a monad! Nevertheless, he’s proved the following.

Theorem 2

Define a morphism of monads on monoids $(M,\theta,h,m)\to(M’,\theta’,h’,m’)$ to be a homomorphism $f:M\to M’$ such that $f\theta=\theta’f$, $f(h) = h’$ and $f(m) = m’$.

Similarly define a morphism of adjunctions between monoids $(M,N,\lambda,\rho,h,e)\to(M’,N’,\lambda’,\rho’,h’,e’)$ to be a pair of homomorphisms $f:M\to M’$ and $g:N\to N’$ such that $f\rho=\lambda’g$, $\lambda’f=g\rho$, $f(h)=h’$ and $g(e) = e’$.

Then the category of monads on monoids is equivalent to the category of adjunctions between monoids. One direction of the equivalence is given by composing an adjunction to get a monad, and the other is given by the Kleisli construction.

Proof

(For details, see Vladimir Molotkov ‘Adjunctions in Monoids’ (2006).)

The interesting part is to show that there is a most one adjunction for each monad. Given a monad $(M,\theta,h,m)$, the Kleisli monoid is the submonoid of $M$ containing the $p$ such that $m\theta(p) = pm$. The monad corresponding to the adjunction $(M,N,\lambda,\rho,h,e)$ is given by $(M,\rho\circ\lambda,h,\rho(e))$. Therefore the Kleisli monoid of this monad consists of the $p\in M$ such that $\rho(e)\rho(\lambda(p)) = p\rho(e)$.

We claim that $\rho$ is injective and the Kleisli monoid is its image. Hence the Kleisli construction recovers $N$ from the monad. To see that $\rho$ is injective, note that (2) and (4) together imply that for all $y\in N$ we have $y = e\lambda(\rho(y))\lambda(h)$. Hence $\rho$ has a left inverse. Next note that for any $y\in N$, $\rho(y)$ satisfies the equation to be in the Kleisli monoid, $\rho(e)\rho(\lambda(\rho(y))) = \rho(y)\rho(e)$, since this is simply $\rho$ applied to (4). Finally we wish to show that every $p$ in the Kleisli monoid is of the form $\rho(y)$ for some $y$ in $N$. Let $y = e\lambda(p)\lambda(h)$. Then $\rho(y) = \rho(e)\rho(\lambda(p))\rho(\lambda(h))$ $= p\rho(e)\rho(\lambda(h))$ $= p\rho(e\lambda(h))$ which is then equal to $p$ by (2).

Another monad on a monoid

The main problem that Molotkov solves in his paper is to find an adjunction of monoids in which the maps $\lambda$ and $\rho$ are not isomorphisms. It turns out that this is exactly the same as the problem we were trying to solve last time, of finding a monad on a monoid that wasn’t conjugation. It’s just been converted into the language of adjunctions using the above theorem. But the example he finds is quite different from the example we found in the previous post.

He constructs the initial object in the category of monads on monoids. To find this you just take elements $h$ and $m$ and a function $\theta$, combine them in all possible ways, and then quotient by the axioms that you want them to obey, those for a monad on a monoid. This yields the following.

Example 3

The initial object in the category of monads on monoids is given by the free monoid on elements $h$, $\theta(h)$, $\theta^2(h)$, … and $m$, $\theta(m)$, $\theta^2(m)$, …, subject to the relations

\begin{align} \theta^i(m)\theta^j(m) &= \theta^{j-1}(m)\theta^i(m)&i<j,\tag{5}\\ \theta^i(h)\theta^j(h) &= \theta^j(h)\theta^{i-1}(h)&i>j,\tag{6}\\ \theta^i(m)\theta^j(h) &= \begin{cases}\theta^j(h)\theta^{i-1}(m)\\ 1_M\\ \theta^{j-1}(h)\theta^i(m)\end{cases}&\begin{split}i>j\\i=j\text{ or }j-1\\i<j-1\end{split}.\tag{7}\end{align}

In other words, $M$ is given by the set of lists of elements of the form $\theta^i(m)$ and $\theta^j(h)$, except that we’re allowed to rearrange these elements by applying the rules (5) to (7). For example one element of $M$ would be $h\theta^7(m)\theta^{10}(m)\theta^2(h)$. We could rewrite this as $h\theta^9(m)\theta^7(m)\theta^2(h)$ by applying axiom (5) to rewrite the $\theta^7(m)\theta^{10}(m)$ in the middle as $\theta^9(m)\theta^7(m)$. Composition of these terms is given by simply joining them together end-to-end. The homomorphism $\theta$ acts by increasing the power of $\theta$ in front of each $h$ and $m$ by one.

This seems like a very complicated monoid! Luckily it can be expressed in a simpler way.

Order preserving maps

The relations (5) to (7) looked familiar to me, but I couldn’t quite recall where I recognized them from. So I ran to the internet for help, and reddit user u/halftrainedmule pointed out that these are a version the simplicial identities.

The simplicial identities are a way of describing the simplex category. But the simplex category can also be defined as the category of nonempty finite totally ordered sets and order preserving maps between them.

Taking inspiration from this allows us to define Example 3 in a much simpler way.

Let $M$ be the monoid of order preserving functions $\mathbb N \to\mathbb N$ which are eventually translations, i.e. with the property that for all sufficiently large $n\in\mathbb N$ they have the form $n\mapsto n+c$ for some $c\in\mathbb Z$.

Define $h$ by $h(n)=n+1$, and define $m$ by $m(n+1)=n$ and $m(0)=0$. Define $\theta$ by $\theta(f)(n+1) = f(n)+1$ and $\theta(f)(0)=0$.

Let’s finish up by working out what the category of modules is. We know the modules are precisely the $k\in M$ with $kh=1_M$ and $k\theta(k)=km$. The first of these equations is already enough to imply that the only such $k$ is $m$. So the Eilenberg-Moore category is the same as the Kleisli category. The morphisms $m\to m$ are the $p\in M$ with $m\theta(p)=pm$. Evaluating both sides of this equation at $n+1$ only yields $p(n)=p(n)$, and evaluating both sides at $0$ gives $0 =p(0)$. So the Kleisli monoid is simply the submonoid of $M$ that fixes $0$.