nLab algebra for an endofunctor

Idea

An algebra over an endofunctor is like an algebra over a monad, but without a notion of associativity (given that a plain endofunctor is not equipped with a multiplication-operation that would make it a monad).

Definition

Definition

For a category $C$ and endofunctor $F$, an algebra (or module) of $F$ is an object $X$ in $C$ and a morphism $\alpha\colon F(X) \to X$. ($X$ is called the carrier of the algebra)

A homomorphism between two algebras $(X, \alpha)$ and $(Y, \beta)$ of $F$ is a morphism $m\colon X \to Y$ in $C$ such that the following square commutes:

$$\array{ F(X) & \overset{F(m)}{\longrightarrow} & F(Y) \\ \mathllap{{}^{\alpha}}\big\downarrow && \big\downarrow\mathrlap{{}^{\beta}} \\ X & \underset{m}{\longrightarrow} & Y } \,.$$

Composition of such homomorphisms of algebras is given by composition of the underlying morphisms in $C$. This yields the category of $F$-algebras, which comes with a forgetful functor to $C$.

Remark

The dual concept is a coalgebra for an endofunctor. Both algebras and coalgebras for endofunctors on $C$ are special cases of algebras for bimodules.

If $F$ is a pointed endofunctor with point $\eta : Id \to F$, then by an algebra for $F$ one usually means a pointed algebra, i.e. one such that $\alpha \circ \eta_X = id_X$.

Properties

Relation to algebras over a monad

To a category theorist, algebras over a monad may be more familiar than algebras over just an endofunctor. In fact, when $C$ and $F$ are well-behaved, then algebras over an endofunctor $F$ are equivalent to algebras over a certain monad, the algebraically-free monad generated by $F$ (Pirog, Gambino-Hyland 04, section 6).

This is analogous to the relationship between an action $M \times B \to B$ of a monoid $M$ and a binary function $A \times B \to B$ (an action of a set): such a function is the same thing as an action of the free monoid $A^*$ on $B$.

Returning to the endofunctor case, the general statement is:

Proposition

The category of algebras of the endofunctor $F\colon \mathcal{C} \to \mathcal{C}$ is equivalent to the category of algebras of the algebraically-free monad on $F$, should such exist.

Actually, this proposition is merely a definition of the term “algebraically-free monad”. If $F$ has an algebraically-free monad, denoted say $F^*$, then in particular the forgetful functor $F Alg \to C$ has a left adjoint, and $F^*$ is the monad on $C$ generated by this adjunction. Conversely, if such a left adjoint exists, then the monad it generates is algebraically-free on $F$; for a mechanised proof in cubical Agda, see (1Lab). An explicit construction of the algebraically free monad in terms of inductive types is given below.

Algebraically-free monads exist in particular when $C$ is a locally presentable category and $F$ is an accessible functor; see transfinite construction of free algebras.

Remark

It turns out that an algebraically-free monad on $F$ is also free in the sense that it receives a universal arrow from $F$ relative to the forgetful functor from monads to endofunctors. The converse, however, is not necessarily true: a free monad in this sense need not be algebraically-free. It is true when $C$ is complete, however.

Entirely analogous facts are true for pointed algebras over pointed endofunctors.

Relationship to inductive types

The initial algebra of an endofunctor provides categorical semantics for inductive types.

The construction of an algebraically free monad may be cast in the language of such initial algebras. Suppose $C$ is a category with coproducts and $F: C \to C$ is an endofunctor. Let $F$-$alg$ be the category of $F$-algebras, and let $U: F\text{-}alg \to C$ be the usual forgetful functor. A left adjoint to $U$ then takes an object $d$ of $C$ to the initial algebra $\Phi(d)$ of the endofunctor $c \mapsto d + F(c)$, provided this initial algebra exists. For, by the usual comma category description (see for example adjoint functor theorem), $\Phi(d)$ is the initial object of the category $(d \downarrow U)$. However, an object of $(d \downarrow U)$ is a triple $(c, \alpha: F(c) \to c, \beta: d \to c)$, equivalently a pair $(c, \gamma: d + F(c) \to c)$, equivalently an algebra of $c \mapsto d + F(c)$. Hence an initial object of $(d \downarrow U)$ is an initial algebra of an endofunctor.

The monad structure of the algebraically free monad $F^\ast = U\Phi$ may be straightforwardly extracted from this initial algebra description. This is made explicit in Pirog. For example, to describe the multiplication $\mu: F^\ast F^\ast \to F^\ast$, let $d$ be an object; then $F^\ast d$ has an algebra structure $[i, \theta]: d + F(F^\ast d) \to F^\ast d$. It therefore also has a structure of algebra over the endofunctor $c \mapsto F^\ast d + F(c)$, namely $[1, \theta]: F^\ast d + F(F^\ast d) \to F^\ast d$. But since $F^\ast F^\ast d$ is the initial algebra for the monad $c \mapsto F^\ast d + F(c)$, we obtain a unique algebra map $F^\ast F^\ast d \to F^\ast d$. This is the component $\mu_d$ of the monad multiplication.

Related concepts

• free monad

• endofunctor, pointed endofunctor

• algebra over a monad, algebra over a profunctor, coalgebra over an endofunctor

• algebraically compact category

References

A textbook account of the basic theory is in chapter 10 of

• Steve Awodey, Category theory lecture notes (2011) (web)

The relation to free monads is discussed in

• Maciej Pirog, Free monads and their algebras

• Nicola Gambino, Martin Hyland, Wellfounded trees and dependent polynomial functors. In Types for proofs and programs, volume 3085 of Lecture Notes in Comput. Sci., pages 210–225. Springer-Verlag, Berlin, 2004 (web)

Formalization in cubical Agda:

• 1lab, Algebras over an endofunctor