# nLab coalgebra for an endofunctor

Contents

### Context

category theory

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

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

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

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

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

Here are two blog discussions of coalgebra theory:

Last revised on February 26, 2024 at 22:34:31. See the history of this page for a list of all contributions to it.