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

Homomorphismen

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

Initiale F-Algebren

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

${\displaystyle {\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 ${\displaystyle ?\colon A\to F(A)}$ der einzige Homomorphismus von ${\displaystyle \alpha }$ nach ${\displaystyle F(\alpha )}$. Deshalb kommutiert das linke Rechteck. Das rechte kommutiert trivialerweise. Somit kommutiert das äußere Rechteck und ${\displaystyle \alpha \circ {?}}$ ist ein ${\displaystyle F}$-Algebra-Homomorphismus von ${\displaystyle \alpha }$ nach ${\displaystyle \alpha }$. Da ${\displaystyle \alpha }$ aber initial ist, muss ${\displaystyle \alpha \circ {?}=\operatorname {id} _{A}}$ sein. Andererseits ist aufgrund des linken Rechtecks und der soeben gefundenen Gleichung ${\displaystyle {?}\circ \alpha =F(\alpha )\circ F(?)=F(\alpha \circ {?})=F(\operatorname {id} _{A})=\operatorname {id} _{F(A)}}$.

Die Bedeutung initialer ${\displaystyle F}$-Algebren liegt nun darin, dass gewisse rekursive Strukturen in geordneter Weise abgebildet werden können. Ist nämlich ${\displaystyle \alpha \colon F(A)\to A}$ eine initiale ${\displaystyle F}$-Algebra, und ${\displaystyle \beta \colon F(B)\to B}$ eine beliebige andere ${\displaystyle F}$-Algebra, so existiert ${\displaystyle \alpha ^{-1}}$ und es gibt genau einen Morphismus ${\displaystyle h\colon A\to B}$, der Lösung der Gleichung ${\displaystyle 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 ${\displaystyle F}$ eine initiale Algebra.
• In Rel_C, der Kategorie abzählbarer Mengen und Relationen, existiert zu jedem Endofunktor ${\displaystyle 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.