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 <math>\mathcal C</math> eine Kategorie und <math>F\colon\mathcal C\to\mathcal C</math> ein Funktor. Jeder <math>\mathcal C</math>-Morphismus <math>\alpha\colon F(X)\to X</math> ist dann eine <math>F</math>-Algebra. Das Objekt <math>X</math> heißt Träger von <math>\alpha</math>.
Homomorphismen
Sind <math>\alpha\colon F(A)\to A</math> und <math>\beta\colon F(B)\to B</math> <math>F</math>-Algebren in <math>\mathcal C</math>, so heißt ein Morphismus <math>h\colon A\to B</math> in <math>\mathcal C</math> mit der Eigenschaft <math>h\circ\alpha=\beta\circ F(h)</math> Homomorphismus von <math>\alpha</math> nach <math>\beta</math>.
Initiale F-Algebren
Die Homomorphismen zwischen <math>F</math>-Algebren zu einem festen Funktor <math>F</math> bilden ihrerseits wieder eine Kategorie, in der die Objekte <math>F</math>-Algebren sind. Ein initiales Objekt dieser Kategorie heißt initiale <math>F</math>-Algebra. Ist <math>\alpha\colon F(A)\to A </math> initial, so ist <math>F(\alpha)\colon F^2(A)\to F(A)</math> als <math>F</math>-Algebra isomorph zu <math>\alpha</math>, wie das Diagramm
- <math>
\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} </math> zeigt. Es sei <math>?\colon A\to F(A)</math> der einzige Homomorphismus von <math>\alpha</math> nach <math>F(\alpha)</math>. Deshalb kommutiert das linke Rechteck. Das rechte kommutiert trivialerweise. Somit kommutiert das äußere Rechteck und <math>\alpha\circ{?}</math> ist ein <math>F</math>-Algebra-Homomorphismus von <math>\alpha</math> nach <math>\alpha</math>. Da <math>\alpha</math> aber initial ist, muss <math>\alpha\circ{?}= \operatorname{id}_A</math> sein. Andererseits ist aufgrund des linken Rechtecks und der soeben gefundenen Gleichung <math>{?}\circ\alpha = F(\alpha)\circ F(?) = F(\alpha\circ{?}) = F(\operatorname{id}_A) = \operatorname{id}_{F(A)}</math>.
Die Bedeutung initialer <math>F</math>-Algebren liegt nun darin, dass gewisse rekursive Strukturen in geordneter Weise abgebildet werden können. Ist nämlich <math>\alpha\colon F(A)\to A</math> eine initiale <math>F</math>-Algebra, und <math>\beta\colon F(B)\to B</math> eine beliebige andere <math>F</math>-Algebra, so existiert <math>\alpha^{-1}</math> und es gibt genau einen Morphismus <math>h\colon A\to B</math>, der Lösung der Gleichung <math>h = \beta\circ F(h)\circ \alpha^{-1}</math> ist. Dieser heißt Katamorphismus.
Existenzsätze für initiale Algebren
- In SetC, der Kategorie abzählbarer Mengen und Funktionen, existiert zu jedem Endofunktor <math>F</math> eine initiale Algebra.
- In RelC, der Kategorie abzählbarer Mengen und Relationen, existiert zu jedem Endofunktor <math>F</math> 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.