Monads via Algebra

A bit of univeral algebra

We will need some basic universal algebra for todays constructions. Intuitively what we are doing capturing classes of structures given by operations and equations they must satisfy, such as groups, rings and monoids.

We consider a signature $\Sigma$ of operation symbols. The elements of the signature are operation symbols, each with a specified arity in the natural numbers. Given a signature, and a set of variables $X$ , the set of $\Sigma$ –terms is defined inductively as follows:

Each $x \in X$ is a term.
If $t_1,\ldots,t_n$ are terms, and $o \in \Sigma$ has arity $n$ , then $o(t_1,\ldots,t_n)$ is a term.

We will generalize this notation to allow infix application of operations, writing $x + y$ rather than $+(x,y)$ when it is clearer to do so.

A $\Sigma$ –algebra consists of:

A set $A$ , the universe.
For each $o \in \Sigma$ of arity $n$ , a function $o^A : A^n \rightarrow A$ .

$\Sigma$ -algebras form a category $\mathsf{Alg}(\Sigma)$ , with morphisms functions $h : A \rightarrow B$ between algebra universes, such that for every $o \in \Sigma$ :

$h(o^A(a_1,\ldots,a_n)) = o^B(h(a_1),\ldots,h(a_n))$ .

For each term $t$ with variables in $X$ , and variable assignment $(-)^A : X \rightarrow A$ , we define the interpretation of $t$ in $A$ , denoted $t^A$ , as follows:

If $t$ is a variable $x$ , then $t^A = x^A$ .
If $t = o(t_1,\ldots,t_n)$ , then $t^A = o^A(t^A_1,\ldots,t^A_n)$ .

For a fixed $\Sigma$ , a set of formal equations $E$ is a set of pairs of terms over some set of variables $X$ . A pair $(\Sigma,E)$ is referred to as an equational presentation for a class of algebras. A $(\Sigma,E)$ -algebra is a $\Sigma$ -algebra such that for each $(t_1,t_2) \in E$ and variable assignment $(-)^A : X \rightarrow A$ :

$t^A_1 = t^A_2$

Example: A monoid is a $(\Sigma,E)$ -algebra where $\Sigma = \{ 1, \times \}$ and $E = \{ (1 \times x, x), (x \times 1, x), ((x \times y) \times z, x \times (y \times z)) \}$ . Here, $1$ has arity 0 (is a constant), and $\times$ has arity $2$ (is a binary operation). A morphism of $\Sigma$ -algebras is then a monoid morphism.

The category $\mathsf{Alg}(\Sigma,E)$ , of $(\Sigma,E)$ -algebras, is the obvious full subcategory of $\mathsf{Alg}(\Sigma)$ .

Back to adjunctions and monads

We now have enough abstract machinery in place to return to our efforts to construct monads. For an equational presentation $(\Sigma,E)$ , there is a forgetful functor

$U : \mathsf{Alg}(\Sigma,E) \rightarrow \mathsf{Set}$

sending an algebra to its underlying universe. The key fact that we need is that this forgetful functor always has a left adjoint

$F : \mathsf{Set} \rightarrow \mathsf{Alg}(\Sigma,E)$

which is also relatively easy to describe. $F(X)$ is called the free algebra on $X$ . For a set $X$ , the universe of $F(X)$ is the set of terms with variables in $X$ , quotiented by provable equality in equational logic, from the equations in $E$ . In general, describing these equivalence classes may be extremely difficult, although is manageable in many examples of interest. Writing $[t]$ for the equivalence class containing $t$ , for an algebra $B$ , and function $f : X \rightarrow U(B)$ , we define $\hat{f} : F(X) \rightarrow B$ inductively on representatives as follows:

$\hat{f}([x]) = f(x)$ .
$\hat{f}([o(t_1,\ldots,t_n)]) = o^B(\hat{f}([t_1]),\ldots,\hat{f}([t_n]))$ .

With this in place, we see that every equational presentation $(\Sigma,E)$ induces a monad $\mathbb{T}$ , with:

Endofunctor: $\mathbb{T}(X)$ is the set of equivalence classes of terms.
Unit: The unit maps variables to their equivalence classes $\eta(x) = [x]$ .
Multiplication: The multiplication is a flattening operation on nested equivalence classes. Formally, $\mu_X = U( \widehat{\mathsf{id}_{UF(X)}})$ .

The multiplication is probably easier to follow from an example.

Example: Returning to the equational presentation of monoids above, an example of the multiplication would be $\mu([w + [y + z] ]) = [w + (y + z)]$ .

Any choice of operations and equations then produces a monad on the category $\mathsf{Set}$ , yielding boundless examples.

Example: There are monads on $\mathsf{Set}$ induced by the equational presentations of monoids, commutative monoids, groups, Abelian groups, rings, join semilattices, semigroups…

The monads that arise from equational presentations are known as the finitary monads. We may return to the question of exactly what that means in a future post. Possibly more important to note is that if we consider sufficiently liberal generalizations of the arities in our equational presentations, every $\mathsf{Set}$ monad can be described in such a way.

One thought on “Monads via Algebra”

Pingback: Lawvere Theories – Dan Marsden

A bit of univeral algebra

Back to adjunctions and monads

Share this:

Like this:

Related

One thought on “Monads via Algebra”

Leave a Reply Cancel reply