F-Algebra

Eine F-Algebra ist eine Struktur, welche allein auf Funktoreigenschaften beruht.

Dual zum Begriff der F-Algebra ist der der F-Koalgebra.

Definition

Es sei $𝒞$ eine Kategorie und $F:𝒞\to 𝒞$ ein Funktor. Jeder $𝒞$-Morphismus $\alpha :F(X)\to X$ ist dann eine $F$-Algebra. Das Objekt $X$ heißt Träger von $\alpha$.

Homomorphismen

Sind $\alpha :F(A)\to A$ und $\beta :F(B)\to B$ $F$-Algebren in $𝒞$, so heißt ein Morphismus $h:A\to B$ in $𝒞$ mit der Eigenschaft $h\circ \alpha =\beta \circ F(h)$ Homomorphismus von $\alpha$ nach $\beta$.

Initiale F-Algebren

Die Homomorphismen zwischen $F$-Algebren zu einem festen Funktor $F$ bilden ihrerseits wieder eine Kategorie, in der die Objekte $F$-Algebren sind. Ein initiales Objekt dieser Kategorie heißt initiale $F$-Algebra. Ist $\alpha :F(A)\to A$ initial, so ist $F(\alpha ):F^2(A)\to F(A)$ als $F$-Algebra isomorph zu $\alpha$, wie das Diagramm

$\begin{array}{ccccc}F(A)& \stackrel{F(?)}{\to }& F^2(A)& \stackrel{F(\alpha )}{\to }& F(A)\\ \alpha \downarrow & & \downarrow F(\alpha )& & \downarrow \alpha \\ A& \stackrel{?}{\to }& F(A)& \stackrel{\alpha }{\to }& A\end{array}$

zeigt. Es sei $?:A\to F(A)$ der einzige Homomorphismus von $\alpha$ nach $F(\alpha )$. Deshalb kommutiert das linke Rechteck. Das rechte kommutiert trivialerweise. Somit kommutiert das äußere Rechteck und $\alpha \circ ?$ ist ein $F$-Algebra-Homomorphismus von $\alpha$ nach $\alpha$. Da $\alpha$ aber initial ist, muss $\alpha \circ ?={\mathrm{id}}_A$ sein. Andererseits ist aufgrund des linken Rechtecks und der soeben gefundenen Gleichung $?\circ \alpha =F(\alpha )\circ F(?)=F(\alpha \circ ?)=F({\mathrm{id}}_A)={\mathrm{id}}_{F(A)}$.

Die Bedeutung initialer $F$-Algebren liegt nun darin, dass gewisse rekursive Strukturen in geordneter Weise abgebildet werden können. Ist nämlich $\alpha :F(A)\to A$ eine initiale $F$-Algebra, und $\beta :F(B)\to B$ eine beliebige andere $F$-Algebra, so existiert ${\alpha }^{-1}$ und es gibt genau einen Morphismus $h:A\to B$, der Lösung der Gleichung $h=\beta \circ F(h)\circ {\alpha }^{-1}$ ist. Dieser heißt Katamorphismus.

Existenzsätze für initiale Algebren

• In Set_C, der Kategorie abzählbarer Mengen und Funktionen, existiert zu jedem Endofunktor $F$ eine initiale Algebra.
• In Rel_C, der Kategorie abzählbarer Mengen und Relationen, existiert zu jedem Endofunktor $F$ eine initiale Algebra.

Literatur

Adámek et al.: Initial algebras and terminal coalgebras: a survey

• B. Jacobs, J. Rutten: A Tutorial on (Co) Algebras and (Co) Induction. In: Bulletin of the European Association for Theoretical Computer Science, Nr. 62, 1997.