David Corfield
coalgebra

An algebra for an endofunctor FF on a category CC is an object cc together with a morphism α:Fcc\alpha: F c \to c.

A coalgebra for an endofunctor FF on a category CC is an object cc together with a morphism α:cFc\alpha: c \to F c.

Examples

  • The endofunctor on Set, F(X)=1+XF(X) = 1 + X has as algebras sets with a designated element and unary function. Initial algebra is the natural numbers with 00 and successor. Coalgebras are partially defined unary functions. Terminal coalgebra is {}\mathbb{N} \union \{\infty\}, with function undefined at 00, predecessor at a finite natural number, and f()=f(\infty) = \infty.

  • For XAx+1X \mapsto A x + 1, the initial algebra consists of lists (finite sequences) of elements of AA; the final coalgebra consists of streams (finite or infinite sequences) of elements of AA.

  • For XAxX \mapsto A x, the inital algebra is empty; the final coalgebra consists of (infinite) sequences of elements of A.

  • The endofunctor on Classes of sets which sends a class AA to the class of subclasses of AA which are sets has as initial algebra the class of sets and as final coalgebra the class of non-well-founded sets.

The link between coalgebra and modal logic. Given a duality such as between Stone and Bool Alg?, with endofunctors on each (see p. 3 of Strongly Complete Logics for Coalgebras), the initial L-algebra is isomorphic to the terminal T-coalgebra, so modal sentences characterise behaviour.

Induction & Coinduction

There appears to be an imbalance in the amount of algebraic to coalgebraic thinking within mathematics. Some options:

  1. It’s not a distinction worth making –- a coalgebra for (C,F)(C, F) is an algebra for (C op,F op)(C^{op}, F^{op}).

  2. It is a distinction worth making, but there’s plenty of coalgebraic thinking going on –- it’s just not flagged as such.

  3. Coalgebra is a small industry providing a few tools for specific situations, largely in computer science, but with occasional uses in topology, etc.

Blog posts

References

Last revised on July 12, 2012 at 16:16:03. See the history of this page for a list of all contributions to it.