F-Algebra

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

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

Definition[Bearbeiten | Quelltext bearbeiten]

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

Homomorphismen[Bearbeiten | Quelltext bearbeiten]

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.

Literatur[Bearbeiten | Quelltext bearbeiten]

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