F-Algebra

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

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

Es sei eine Kategorie und ein Funktor. Jeder -Morphismus ist dann eine -Algebra. Das Objekt heißt Träger von .

Sind und -Algebren in , so heißt ein Morphismus in mit der Eigenschaft Homomorphismus von nach .

Initiale F-Algebren

[Bearbeiten | Quelltext bearbeiten]

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

[Bearbeiten | Quelltext bearbeiten]
  • 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.

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