# nLab coalgebra for an endofunctor

Contents

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.

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

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

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

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

###### Remark

If $F$ 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.

## Examples

### Coalgebras for endofunctors on $Set$

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

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

See coalgebra for examples on categories of modules.

### The real line as a terminal coalgebra

Let $Pos$ be the category of posets. Consider the endofunctor

$F_1 : Pos \to Pos$

that acts by ordinal product? with $\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 $\mathbb{R}^+$, with its standard order.

###### Proof

This is theorem 5.1 in

###### 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