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 \Sigmaterms 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 \Sigmaalgebra 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: