nLab coalgebra for an endofunctor

Contents

Context

Category theory

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 CC and endofunctor FF, a coalgebra of FF is an object XX in CC together with a morphism α:XF(X)\alpha: X \to F(X).

Given two coalgebras (x,η:xFx)(x, \eta: x \to F x), (y,θ:yFy)(y, \theta: y \to F y), a coalgebra homomorphism is a morphism f:xyf: x \to y which respects the coalgebra structures:

θf=F(f)η\theta \circ f = F(f) \circ \eta

(The object XX 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 CC are special cases of algebras for C-C bimodules.

Remark

If FF 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 FF is a copointed endofunctor with copoint ϵ:FId\epsilon : F \to Id, then by a coalgebra for FF one usually means a pointed coalgebra, i.e. one such that ϵ Xα=id X\epsilon_X \circ \alpha = id_X.

Examples

Coalgebras for endofunctors on SetSet

Each of the following examples is of the form XF(X)X\to F(X), (description of endofunctor F:SetSetF\colon Set\to Set) : (description of coalgebra). Where it appears, AA is a given fixed set.

See coalgebra for examples on categories of modules.

The real line as a terminal coalgebra

Let PosPos be the category of posets. Consider the endofunctor

F 1:PosPos F_1 : Pos \to Pos

that acts by ordinal product? with ω\omega

F 1:XXω, 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 1F_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][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 XX to the space XXX \vee X. Here, XYX \vee Y, for (X,x ,x +)(X, x_-, x_+) and (Y,y ,y +)(Y, y_-, y_+), is the disjoint union of XX and YY with x +x_+ and y y_- identified, and x x_- and y +y_+ as the two base points.

Proof

This is discussed in

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

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.