nLab
coalgebra for an endofunctor

Idea

A coalgebra over an endofunctor is like a coalgebra over a comonad, but without a notion of associativity.

Definition

For a category $C$ and endofunctor $F$, a coalgebra of $F$ is an object $X$ in $C$ and a map $\alpha :X\to F(X)$. (The object $X$ may be called the carrier of the coalgebra)

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

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

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.

See also terminal coalgebra.

Examples

Coalgebras for functors on $\mathrm{Set}$

• $X\to F(X)=D(X)$, the set of probability distributions on $X$: Markov chain on $X$.
• $X\to F(X)=𝒫(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 \mathrm{bool}$: deterministic automaton.
• $X\to F(X)=𝒫(X^A\times \mathrm{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)=𝒫(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 $\mathrm{Pos}$ be the category of posets. Consider the endofunctor

$$F_1:\mathrm{Pos}\to \mathrm{Pos}$$F_1 : Pos \to Pos

that acts by ordinal product? with $\omega$

$$F_1:X\mapsto X\cdot \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 ${ℝ}^{+}$, 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

• well-founded coalgebra

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

References

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

There are important connections beteen the theory of coalgebras and modal logic, for which see

• Bart Jacobs, Introduction to Coalgebra. Towards Mathematics of States and Observations. Two-thirds of a book in preparation;

Here are two blog discussions of coalgebra theory:

• David Corfield, Coalgebraically Thinking

• David Corfield, The Status of Coalgebra