nLab
algebra for an endofunctor

Contents

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.

If FF is a pointed endofunctor with point η:IdF\eta : Id \to F, then by an algebra for FF one usually means a pointed algebra, i.e. one such that αη X=id X\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 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.

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.

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)

Last revised on December 30, 2018 at 18:52:36. See the history of this page for a list of all contributions to it.