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 ${\mathcal {C}}$ eine Kategorie und $F\colon {\mathcal {C}}\to {\mathcal {C}}$ ein Funktor. Jeder ${\mathcal {C}}$-Morphismus $\alpha \colon F(X)\to X$ ist dann eine $F$-Algebra. Das Objekt $X$ heißt Träger von $\alpha$.

Homomorphismen

Sind $\alpha \colon F(A)\to A$ und $\beta \colon F(B)\to B$ $F$-Algebren in ${\mathcal {C}}$, so heißt ein Morphismus $h\colon A\to B$ in ${\mathcal {C}}$ 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 \colon F(A)\to A$ initial, so ist $F(\alpha )\colon F^{2}(A)\to F(A)$ als $F$-Algebra isomorph zu $\alpha$, wie das Diagramm

${\begin{matrix}F(A)&{\xrightarrow {\ F(?)\ }}&F^{2}(A)&{\xrightarrow {\ F(\alpha )\ }}&F(A)\\\alpha {\Bigg \downarrow }&&{\Bigg \downarrow }F(\alpha )&&{\Bigg \downarrow }\alpha \\A&{\xrightarrow {\quad ?\quad }}&\!\!\!F(A)&{\xrightarrow {\quad \alpha \quad }}&\!\!\!A\end{matrix}}$

zeigt. Es sei $?\colon 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 {?}=\operatorname {id} _{A}$ sein. Andererseits ist aufgrund des linken Rechtecks und der soeben gefundenen Gleichung ${?}\circ \alpha =F(\alpha )\circ F(?)=F(\alpha \circ {?})=F(\operatorname {id} _{A})=\operatorname {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 \colon F(A)\to A$ eine initiale $F$-Algebra, und $\beta \colon F(B)\to B$ eine beliebige andere $F$-Algebra, so existiert $\alpha ^{-1}$ und es gibt genau einen Morphismus $h\colon 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. Bulletin of the European Association for Theoretical Computer Science (PDF-Datei; 426 kB), vol. 62, 1997