F-coalgebra

Examples

Consider the endofunctor ${\displaystyle X\mapsto X\bigsqcup \{\ast \}:\mathbf{S}\mathbf{e}\mathbf{t}\to \mathbf{S}\mathbf{e}\mathbf{t}}$ that sends a set to its disjoint union with the singleton set ${\displaystyle \{\ast \}}$. A coalgebra of this endofunctor is given by ${\displaystyle (\overline{\mathbb{N}},\alpha )}$, where ${\displaystyle \overline{\mathbb{N}}=\{0,1,2,\dots \}\bigsqcup \{\mathrm{\infty }\}}$ is the so-called conatural numbers, consisting of the nonnegative integers and also infinity, and the function ${\displaystyle \alpha }$ is given by ${\displaystyle \alpha (0)=\ast }$, ${\displaystyle \alpha (n)=n-1}$ for ${\displaystyle n=1,2,\dots }$ and ${\displaystyle \alpha (\mathrm{\infty })=\mathrm{\infty }}$. In fact, ${\displaystyle (\overline{\mathbb{N}},\alpha )}$ is the terminal coalgebra of this endofunctor.

More generally, fix some set ${\displaystyle A}$, and consider the functor ${\displaystyle F:\mathbf{S}\mathbf{e}\mathbf{t}⟶\mathbf{S}\mathbf{e}\mathbf{t}}$ that sends ${\displaystyle X}$ to ${\displaystyle (X\times A)\cup \{1\}}$. Then an ${\displaystyle F}$-coalgebra ${\displaystyle \alpha :X⟶(X\times A)\cup \{1\}=FX}$ is a finite or infinite stream over the alphabet ${\displaystyle A}$, where ${\displaystyle X}$ is the set of states and ${\displaystyle \alpha }$ is the state-transition function. Applying the state-transition function to a state may yield two possible results: either an element of ${\displaystyle A}$ together with the next state of the stream, or the element of the singleton set ${\displaystyle \{1\}}$ as a separate "final state" indicating that there are no more values in the stream.

In many practical applications, the state-transition function of such a coalgebraic object may be of the form ${\displaystyle X\to f_1\times f_2\times \dots \times f_n}$, which readily factorizes into a collection of "selectors", "observers", "methods" ${\displaystyle X\to f_1,X\to f_2\dots X\to f_n}$. Special cases of practical interest include observers yielding attribute values, and mutator methods of the form ${\displaystyle X\to X^{A_1\times \dots \times A_n}}$ taking additional parameters and yielding states. This decomposition is dual to the decomposition of initial ${\displaystyle F}$-algebras into sums of 'constructors'.

Let P be the power set construction on the category of sets, considered as a covariant functor. The P-coalgebras are in bijective correspondence with sets with a binary relation. Now fix another set, A. Then coalgebras for the endofunctor P(A×(-)) are in bijective correspondence with labelled transition systems, and homomorphisms between coalgebras correspond to functional bisimulations between labelled transition systems.

Applications

In computer science, coalgebra has emerged as a convenient and suitably general way of specifying the behaviour of systems and data structures that are potentially infinite, for example classes in object-oriented programming, streams and transition systems. While algebraic specification deals with functional behaviour, typically using inductive datatypes generated by constructors, coalgebraic specification is concerned with behaviour modelled by coinductive process types that are observable by selectors, much in the spirit of automata theory. An important role is played here by final coalgebras, which are complete sets of possibly infinite behaviours, such as streams. The natural logic to express properties of such systems is coalgebraic modal logic.