nLab
coalgebra for an endofunctor

Context

Category theory

Algebra

Contents

Idea

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.

Definition

Definition

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

Remark

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.

Remark

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.

Examples

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.

Proposition

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

Proof

This is theorem 5.1 in

Proposition

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.

Proof

This is discussed in

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

References

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 (89.204.139.199)