Coalgebra

A kind a generalization of Transition Systems

Given a (covariant) Functor $F:\mathcal{C}\to \mathcal{C}$ A $F$-coalgebra consists of a carrier $x:\mathcal{C}$ and a map

$$\zeta :x\to Fx$$

Eg.

$$X\to \mathbb{Z}\text{texttimes}X$$

Distribution: countably-supported set: countablly many non-zero values. Distribution operator is a functor

Powerset: is a functor

Pointed coalgebra

A $F$-coalgebra $(X,\zeta :X\to FX,x_0\in X)$.

This forms a category with the following arrows.

$$\text{require}AMScd\begin{array}{ccc}FX& \stackrel{Ff}{\to }& FY\\ \xi \downarrow & & \zeta \downarrow \\ GX& \stackrel{Gf}{\to }& Gy\end{array}$$

An $F$-coalgebra over $\mathcal{C}$ is the same thing as an $F^{\mathrm{op}}$-algebra over ${\mathcal{C}}^{\mathrm{op}}$.

Coalgebra-to-algebra morphism

Created by Eppendahl. Never talk about algebra-to-coalgebra.

$$\text{require}AMScd\begin{array}{ccc}FX& \stackrel{Ff}{\to }& FY\\ \zeta \uparrow & & \theta \downarrow \\ X& \stackrel{f}{\to }& Y\end{array}$$

Need to check, this commutes, you can compose with a coalgebra morphism $(x^{\prime },\xi )\to (x,\zeta )$ Other rules are required, such as composition of these arrows.

This is a Bimodule from one category to another.

Examples

Unreliable Integer

Let $E$ be a set of errors. Let $F(X)=E+\mathbb{Z}\text{texttimes}X$ Then we have a set of behaviours $A^{\ast }\text{texttimes}B+A^{\omega }$

Have

$$A^{\ast }\text{texttimes}B+A^{\omega }\cong B+A\text{texttimes}(A^{\ast }\text{texttimes}B+A^{\omega })$$

Initial algebras are the minimal states $A^{\ast }\text{texttimes}B$

Generative Interactive Integer

$$F(X)=\mathbb{Z}\to (\mathbb{Z}\text{texttimes}X)$$

G(X)=\mathbb{Z} {\texttimes} (\mathbb{Z} \to X)

\require{AMScd} \begin{CD} B{\texttimes} (A\to X) @>>> B{\texttimes} (A\to (A^* \to B))\\ @A{\zeta}AA @VVV\\ X @>f>> A^*{\texttimes} B \end{CD} $$ Where f is the unique [[Anamorphism]] that makes the diagram commute. ### Colorful Integers Let $C$ be a set of colors (rgb). $$ F(X) = \mathrm{List}(C)\to (C\to Set) $$ Idea: possible plays for m a tree The [[initial algebra]] is the [[W Type|Well-Founded Tree]]s. ## See also [[Subfunctor]] [[Algebra (Category Theory)]] ## Resources https://pblevy.github.io/coalglect.pdf