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]

Es sei \mathcal C eine Kategorie und F\colon\mathcal C\to\mathcal C ein Funktor. Jeder \mathcal C-Morphismus \alpha\colon F(X)\to X ist dann eine F-Algebra. Das Objekt X heißt Träger von \alpha.

Homomorphismen[Bearbeiten]

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

Initiale F-Algebren[Bearbeiten]

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


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

Die Bedeutung initialer F-Algebren liegt nun darin, dass gewisse rekursive Strukturen in geordneter Weise abgebildet werden können. Ist nämlich \alpha\colon F(A)\to A eine initiale F-Algebra, und \beta\colon F(B)\to B eine beliebige andere F-Algebra, so existiert \alpha^{-1} und es gibt genau einen Morphismus h\colon A\to B, der Lösung der Gleichung h = \beta\circ F(h)\circ \alpha^{-1} ist. Dieser heißt Katamorphismus.

Existenzsätze für initiale Algebren[Bearbeiten]

  • In SetC, der Kategorie abzählbarer Mengen und Funktionen, existiert zu jedem Endofunktor F eine initiale Algebra.
  • In RelC, der Kategorie abzählbarer Mengen und Relationen, existiert zu jedem Endofunktor F eine initiale Algebra.

Literatur[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