coalgebra for an endofunctor

[[!include category theory - contents]]

[[!include higher algebra - contents]]

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.

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

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.

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.

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

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.

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

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.

- Jiri Adamek,
*Introduction to coalgebras*,*Theory and Applications of Categories*, Vol. 14 (2005), No. 8, 157-199.

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 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:

Last revised on October 26, 2016 at 11:37:52. See the history of this page for a list of all contributions to it.