nLab coalgebra for an endofunctor

category theory

Applications

Algebra

higher algebra

universal 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 $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.

Examples

Coalgebras for functors on $Set$

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

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

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