David Corfield coalgebra

An algebra for an endofunctor $F$ on a category $C$ is an object $c$ together with a morphism $\alpha: F c \to c$.

A coalgebra for an endofunctor $F$ on a category $C$ is an object $c$ together with a morphism $\alpha: c \to F c$.

Examples

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

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

• For $X \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 $A$ to the class of subclasses of $A$ 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)$ is an algebra for $(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.

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.