nLab coalgebra for an endofunctor

Given two coalgebras $(x, η : x \to F x) (x, \eta: x \to F x)$ , $(y, θ : y \to F y) (y, \theta: y \to F y)$ , a coalgebrahomomorphism is amorphism $f : x \to y f: x \to y$ which respects the coalgebra structures:

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

(The object $X X$ is sometimes called thecarrier of the coalgebra.)

Remark

The dual concept is analgebra for an endofunctor. Bothalgebras and coalgebras for endofunctors on $C C$ are special cases ofalgebras for C-C bimodules.

Remark

If $F F$ is equipped with the structure of amonad, then a coalgebra for it is equivalently anendomorphism in the correspondingKleisli category. In this case the canonicalmonoidal category structure on endomorphisms induces atensor product on those coalgebras.

If $F F$ is acopointed endofunctor with copoint $ϵ : F \to Id \epsilon : F \to Id$ , then by acoalgebra for $F F$ one usually means apointed coalgebra, i.e. one such that $ϵ_{X} \circ α = {id}_{X} \epsilon_X \circ \alpha = id_X$ .

Examples

Coalgebras for endofunctors on $Set Set$

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

$X \to D (X) X \to D(X)$ , the set ofprobability distributions on $X X$ :Markov chain on $X X$ .
$X \to 𝒫 (X) X \to \mathcal{P}(X)$ , thepower set of $X X$ : binary relation on $X X$ , and also the simplest type ofKripke frames.
$X \to X^{A} \times bool X \to X^A \times bool$ , with $X^{A} X^A$ the set of functions $A \to X A\to X$ and $bool = {0, 1} bool = \{0,1\}$ :deterministic automaton.
$X \to 𝒫 (X)^{A} \times bool X \to \mathcal{P}(X)^A\times bool$ :nondeterministic automaton.
$X \to A \times X \times X X \to A \times X \times X$ : labelled binary tree with labels from $A A$ .
$X \to 𝒫 (A \times X) X \to \mathcal{P}(A\times X)$ :labelled transition system with labels from $A A$ .

Seecoalgebra for examples on categories of modules.

The real line as a terminal coalgebra

Let $Pos Pos$ be the category ofposets. Consider the endofunctor

F_{1} : Pos \to Pos F_1 : Pos \to Pos

that acts byordinal product? with $ω \omega$

F_{1} : X \mapsto X \cdot ω, 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} F_1$ is order isomorphic to the non-negativereal line $ℝ^{+} \mathbb{R}^+$ , 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] [0, 1]$ may be characterized, as atopological space, as the terminal coalgebra for the functor on two-pointed topological spaces which takes a space $X X$ to the space $X \lor X X \vee X$ . Here, $X \lor Y X \vee Y$ , for $(X, x_{-}, x_{+}) (X, x_-, x_+)$ and $(Y, y_{-}, y_{+}) (Y, y_-, y_+)$ , is the disjoint union of $X X$ and $Y Y$ with $x_{+} x_+$ and $y_{-} y_-$ identified, and $x_{-} x_-$ and $y_{+} y_+$ as the two base points.

Proof

This is discussed in

Peter Freyd,cat list

More information may be found atcoalgebra of the real interval.

Related concepts

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 Categories14 8 (2005) 157-199 [tac:14-08,pdf]

There are connections between the theory of coalgebras andmodal logic for which see

Bart Jacobs,Introduction to Coalgebra. Towards Mathematics of States and Observations (book pdf,slides)

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 withquantum mechanics, for which see this and

Samson Abramsky,Coalgebras, Chu Spaces, and Representations of Physical Systems (arXiv:0910.3959)

Here are two blog discussions of coalgebra theory:

Last revised on October 8, 2024 at 22:12:13. See thehistory of this page for a list of all contributions to it.

Edit DiscussPrevious revisionChanges from previous revision History (24 revisions)Cite Print Source

Movatterモバイル変換

nLab coalgebra for an endofunctor

Context

Category theory

Concepts

Universal constructions

Theorems

Extensions

Applications

Algebra

Algebraic theories

Algebras and modules

Higher algebras

Model category presentations

Geometry on formal duals of algebras

Theorems

Contents

Idea

Definition

Definition

Remark

Remark

Examples

Coalgebras for endofunctors onSetSet

The real line as a terminal coalgebra

Proposition

Proof

Proposition

Proof

Related concepts

References

Coalgebras for endofunctors on $Set Set$