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.

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\left(X\right)$. (The object $X$ may be called the carrier of the coalgebra)

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

$\theta \circ f=F\left(f\right)\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.

Examples

Coalgebras for functors on $\mathrm{Set}$

• $X\to F\left(X\right)=D\left(X\right)$, the set of probability distributions on $X$: Markov chain on $X$.
• $X\to F\left(X\right)=𝒫\left(X\right)$, the power set on $X$: binary relation on $X$, and also the simplest type of Kripke frames.
• $X\to F\left(X\right)={X}^{A}×\mathrm{bool}$: deterministic automaton.
• $X\to F\left(X\right)=𝒫\left({X}^{A}×\mathrm{bool}\right)$: nondeterministic automaton.
• $X\to F\left(X\right)=A×X×X$, for a set of labels, $A$: labelled binary tree.
• $X\to F\left(X\right)=𝒫\left(A×X\right)$, 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↦X\cdot \omega \phantom{\rule{thinmathspace}{0ex}},$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

Proposition

The real interval $\left[0,1\right]$ 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 $\left(X,{x}_{-},{x}_{+}\right)$ and $\left(Y,{y}_{-},{y}_{+}\right)$, 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

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

References

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

Here are two blog discussions of coalgebra theory:

Revised on September 17, 2012 18:42:09 by Todd Trimble (67.81.93.25)