coalgebra for an endofunctor


Category theory




A coalgebra over an endofunctor is like a coalgebra over a comonad, but without a notion of associativity.

The concept plays a role in computer science for models of state-based computation (see also monad (in computer science)). The concept of the terminal coalgebra of an endofunctor is a way of encoding coinductive types.



For a category CC and endofunctor FF, a coalgebra of FF is an object XX in CC together with a morphism α:XF(X)\alpha: X \to F(X).

Given two coalgebras (x,η:xFx)(x, \eta: x \to F x), (y,θ:yFy)(y, \theta: y \to F y), a coalgebra homomorphism is a morphism f:xyf: x \to y which respects the coalgebra structures:

θf=F(f)η\theta \circ f = F(f) \circ \eta

(The object XX is sometimes called the carrier of the coalgebra.)


The dual concept is an algebra for an endofunctor. Both algebras and coalgebras for endofunctors on CC are special cases of algebras for C-C bimodules.


If FF is equipped with the structure of a monad, then a coalgebra for it is equivalently an endomorphism in the corresponding Kleisli category. In this case the canonical monoidal category structure on endomorphisms induces a tensor product on those coalgebras.


Coalgebras for functors on SetSet

  • XF(X)=D(X)X \to F(X) = D(X), the set of probability distributions on XX: Markov chain on XX.
  • XF(X)=𝒫(X)X \to F(X) = \mathcal{P}(X), the power set on XX: binary relation on XX, and also the simplest type of Kripke frames.
  • XF(X)=X A×boolX \to F(X) = X^A \times bool: deterministic automaton.
  • XF(X)=𝒫(X A×bool)X \to F(X) = \mathcal{P}(X^A \times bool): nondeterministic automaton.
  • XF(X)=A×X×XX \to F(X) = A \times X \times X, for a set of labels, AA: labelled binary tree.
  • XF(X)=𝒫(A×X)X \to F(X) = \mathcal{P}(A\times X), for a set of labels, AA: labelled transition system.

See coalgebra for examples on categories of modules.

The real line as a terminal coalgebra

Let PosPos be the category of posets. Consider the endofunctor

F 1:PosPos F_1 : Pos \to Pos

that acts by ordinal product? with ω\omega

F 1:XXω, F_1 : X \mapsto X \cdot \omega \,,

where the right side is given the dictionary order, not the usual product order.


The terminal coalgebra of F 1F_1 is order isomorphic to the non-negative real line +\mathbb{R}^+, with its standard order.


This is theorem 5.1 in


The real interval [0,1][0, 1] may be characterized, as a topological space, as the terminal coalgebra for the functor on two-pointed topological spaces which takes a space XX to the space XXX \vee X. Here, XYX \vee Y, for (X,x ,x +)(X, x_-, x_+) and (Y,y ,y +)(Y, y_-, y_+), is the disjoint union of XX and YY with x +x_+ and y y_- identified, and x x_- and y +y_+ as the two base points.


This is discussed in

More information may be found at coalgebra of the real interval.


There are connections between the theory of coalgebras and modal logic for which see

and with quantum mechanics, for which see this and

Here are two blog discussions of coalgebra theory:

Revised on January 11, 2014 15:58:07 by Urs Schreiber (