imported>M Huhn: Literaturangabe

2024-01-24T22:24:46Z

Literaturangabe

Neue Seite

Eine '''F-Algebra''' ist eine Struktur, welche allein auf [[Funktor (Mathematik)|Funktor]]eigenschaften beruht.

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

== Definition ==
Es sei <math>\mathcal C</math> eine [[Kategorientheorie|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 '''Set'''<sub>C</sub>, der Kategorie abzählbarer Mengen und Funktionen, existiert zu jedem Endofunktor <math>F</math> eine initiale Algebra.
* In '''Rel'''<sub>C</sub>, der Kategorie abzählbarer Mengen und Relationen, existiert zu jedem Endofunktor <math>F</math> eine initiale Algebra.

== Literatur ==
[http://www.tu-braunschweig.de/Medien-DB/iti/survey_full.pdf Adámek et al.: Initial algebras and terminal coalgebras: a survey]
* B. Jacobs, J. Rutten: [http://www.cs.ru.nl/~bart/PAPERS/JR.pdf ''A Tutorial on (Co) Algebras and (Co) Induction'']. In: ''Bulletin of the European Association for Theoretical Computer Science'', Nr. 62, 1997.

[[Kategorie:Kategorientheorie]]

F-Algebra - Versionsgeschichte

imported>M Huhn: Literaturangabe