Eilenberg-Moore Algebras

We shall now start to explore one of the two categories that accompany every monad. The second construction, the Kleisli category, will follow shortly after.

For a monad $\mathbb{T}$ on category $\mathcal{C}$ , an Eilenberg-Moore algebra is a $\mathcal{C}$ -object $A$ , and a $\mathcal{C}$ -morphism $\mathbb{T}(A) \rightarrow A$ , satisfying the following two axioms:

Unit axiom: $\alpha \circ \eta = \mathsf{id}$ .
Multiplication axiom: $\alpha \circ \mu = \alpha \circ \mathbb{T}(\alpha)$ .

A morphism of Eilenberg-Moore algebras $h : (A,\alpha) \rightarrow (B,\beta)$ is a $\mathcal{C}$ -morphism $h : A \rightarrow B$ such that $h \circ \alpha = \beta \circ \mathbb{T}(h)$ . Eilenberg-Moore algebras and their morphisms form a category, the Eilenberg-Moore category, denoted $\mathcal{C}^{\mathbb{T}}$ . Composition and identities are as in $\mathcal{C}$ .

To get some intuition for this definition, lets assume that the monad $\mathbb{T}$ is given by an equational presentation, with a signature consisting of a single binary operation $o$ , and no equations. For a set $A$ , $\mathbb{T}(A)$ consists of terms built up from elements of $A$ by repeated applying the operation $o$ . For example, the following are all terms:

$a, o(a_1,a_2), o(o(a_1,a_2),a_3), o(a,a)$

A function $\alpha : \mathbb{T}(A) \rightarrow A$ can be seen as a way of evaluating a term built up of elements of $A$ , to yield a new element. If we consider the unit axiom, it is equivalent to requiring:

$\alpha(a) = a$

That is, bare variables are evaluated to themselves.

To see what the multiplication axiom means, we must first introduce a bit of notation for substitution. If $t$ is a term, we shall write $t[t'/x]$ for the term resulting from substituting $t'$ for each occurrence of $x$ in $t$ . For example:

$o(x,y)[o(z,z)/x] = o(o(z,z),y)$

We shall also write $t[t_x / x \mid x \in X]$ a shorthand for multiple simultaneous substitutions, when it is well-defined to do so. For example if $t_{w} = o(y,y)$ and $t_{x} = o(z,z)$ , then:

$o(w,x)[t_i/ i \mid i \in \{ w, x \}] = o(o(y,y),o(z,z))$

The multiplication axiom is then equivalent to requiring:

$\alpha(t[t_x/ x \mid x \in X]) = \alpha(t[\alpha(t_x) / x \mid x \in X]$

So evaluating a composite term can be broken up into evaluating sub-terms and then evaluating the parent term to combine the results. For example, we must have:

$\alpha(o(o(y,y),o(z,z)) = \alpha(o(\alpha(o(y,y), \alpha(o(z,z)))$

These two axioms force $\alpha$ to behave exactly as if it had picked a binary function $o^A : A \times A \rightarrow A$ , and then evaluates all terms by recursively applying $o^A$ in the obvious way.

For our example, we only required the set of equations to be empty to avoid lots of distracting equivalence class brackets everywhere. For a general equational presentation $(\Sigma,E)$ , the axioms again force that the Eilenberg-Moore algebras must evaluate by recursively applying fixed functions for each operation symbol. The quotient by provable equality simply forces that terms that are provably equal syntactically are evaluated to the same value.

Example: For the list monad, an Eilenberg-Moore algebra on $A$ is a function $\mathbb{L}(A) \xrightarrow{\alpha} A$ such that

$\alpha([a]) = a$ .
$\alpha(\mathsf{concat}([l_1,\ldots,l_n])) = \alpha([\alpha(l_1),\ldots,\alpha(l_n)])$ .

Example: For a closure operator $c : P \rightarrow P$ , the Eilenberg-Moore algebras are elements $p \in P$ such that $c(p) \leq p$ . The two axioms are trivial in this case. As every closure operator has $p \leq c(p)$ , by irreflexivity, the Eilenberg-Moore algebras can be identified with the elements of the form $c(p)$ , the closed elements of $P$ .