nLab algebra for an endofunctor

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 (which would not make sense).

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) & \stackrel{F(m)}{\rightarrow} & F(Y) \\ \alpha\downarrow && \downarrow \beta \\ X & \stackrel{m}{\rightarrow} & Y } \,.$

Composition of such morphisms 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.

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$ (Maciej, 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 algebracially-free on $F$; for the straightforward proof, see for instance (Maciej).

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.

References

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)

Revised on January 8, 2014 17:11:55 by Urs Schreiber (82.113.106.24)