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