nLab coalgebra for an endofunctor

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 $C$ and endofunctor $F$, a coalgebra of $F$ is an object $X$ in $C$ together with a morphism $\alpha: X \to F(X)$.

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

$$\theta \circ f = F(f) \circ \eta$$

(The object $X$ 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 $C$ are special cases of algebras for C-C bimodules.

Remark

If $F$ 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.

If $F$ is a copointed endofunctor with copoint $\epsilon : F \to Id$, then by a coalgebra for $F$ one usually means a pointed coalgebra, i.e. one such that $\epsilon_X \circ \alpha = id_X$.

Examples

Coalgebras for endofunctors on $Set$

Each of the following examples is of the form $X\to F(X)$, (description of endofunctor $F\colon Set\to Set$) : (description of coalgebra). Where it appears, $A$ is a given fixed set.

• $X \to D(X)$, the set of probability distributions on $X$: Markov chain on $X$.
• $X \to \mathcal{P}(X)$, the power set of $X$: binary relation on $X$, and also the simplest type of Kripke frames.
• $X \to X^A \times bool$, with $X^A$ the set of functions $A\to X$ and $bool = \{0,1\}$: deterministic automaton.
• $X \to \mathcal{P}(X)^A\times bool$: nondeterministic automaton.
• $X \to A \times X \times X$: labelled binary tree with labels from $A$.
• $X \to \mathcal{P}(A\times X)$: labelled transition system with labels from $A$.

See coalgebra for examples on categories of modules.

The real line as a terminal coalgebra

Let $Pos$ be the category of posets. Consider the endofunctor

$$F_1 : Pos \to Pos$$

that acts by ordinal product? with $\omega$

$$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_1$ is order isomorphic to the non-negative real line $\mathbb{R}^+$, with its standard order.

Proof

This is theorem 5.1 in

• D. Pavlovic, Vaughan Pratt, On coalgebra of real numbers (web)

Proposition

The real interval $[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 $X$ to the space $X \vee X$. Here, $X \vee Y$, for $(X, x_-, x_+)$ and $(Y, y_-, y_+)$, is the disjoint union of $X$ and $Y$ with $x_+$ and $y_-$ identified, and $x_-$ and $y_+$ as the two base points.

Proof

This is discussed in

• Peter Freyd, cat list

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

Related concepts

• copointed endofunctor

• list of notable initial algebras and terminal coalgebras

• well-founded coalgebra

• algebra over a monad, algebra over an endofunctor, algebra over a profunctor

References

• Michael Barr, Terminal coalgebras for endofunctors on sets, Theoretical Comp. Sci. 114 (1993) 299–315 [pdf, pdf]

• Dirk Pattinson, An Introduction to the Theory of Coalgebras (2003) [pdf, pdf]

• Jiri Adamek, Introduction to coalgebras, Theory and Applications of Categories 14 8 (2005) 157-199 [tac:14-08, pdf]

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

• Bart Jacobs, Introduction to Coalgebra. Towards Mathematics of States and Observations (book pdf, slides)

and also

• Corina Cırstea, Alexander Kurz, Dirk Pattinson, Lutz Schroder and Yde Venema, Modal Logics are Coalgebraic, from the Computer Journal 2011, here.

and with quantum mechanics, for which see this and

• Samson Abramsky, Coalgebras, Chu Spaces, and Representations of Physical Systems (arXiv:0910.3959)

Here are two blog discussions of coalgebra theory:

• David Corfield, Coalgebraically Thinking

• David Corfield, The Status of Coalgebra