nLab
algebra for an endofunctor

Context

Category theory

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 CC and endofunctor FF, an algebra (or module) of FF is an object XX in CC and a morphism α:F(X)X\alpha\colon F(X) \to X. (XX is called the carrier of the algebra)

A homomorphism between two algebras (X,α)(X, \alpha) and (Y,β)(Y, \beta) of FF is a morphism m:XYm\colon X \to Y in CC such that the following square commutes:

F(X) F(m) F(Y) α β X m Y. \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 CC. This yields the category of FF-algebras, which comes with a forgetful functor to CC.

Remark

The dual concept is a coalgebra for an endofunctor. Both algebras and coalgebras for endofunctors on CC 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 CC and FF are well-behaved, then algebras over an endofunctor FF are equivalent to algebras over a certain monad, the algebraically-free monad generated by FF (Maciej, Gambino-Hyland 04, section 6).

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

Returning to the endofunctor case, the general statement is:

Proposition

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

Actually, this proposition is merely a definition of the term “algebraically-free monad”. If FF has an algebraically-free monad, denoted say F *F^*, then in particular the forgetful functor FAlgCF Alg \to C has a left adjoint, and F *F^* is the monad on CC generated by this adjunction. Conversely, if such a left adjoint exists, then the monad it generates is algebracially-free on FF; for the straightforward proof, see for instance (Maciej).

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

Remark

It turns out that an algebraically-free monad on FF is also free in the sense that it receives a universal arrow from FF 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 CC 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)