# nLab algebra for an endofunctor

Contents

category theory

## Applications

#### Algebra

higher algebra

universal algebra

# Contents

## 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 the straightforward proof, see for instance (Pirog). 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 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.

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

The relation to free monads is discussed in

• 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)