F-algebra

An F-algebra is a structure that is based solely on functor properties.

Dual to the concept of F-algebra is that of F-koalgebra

definition

Let it be a category and a functor. Every morphism is then an algebra. The object is called carrier of . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle F\colon {\mathcal {C}}\to {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \alpha \colon F(X)\to X}$ ${\displaystyle F}$ ${\displaystyle X}$ ${\displaystyle \alpha }$

Homomorphisms

If and -algebras are in , a morphism is called in with the property homomorphism from to . ${\displaystyle \alpha \colon F(A)\to A}$ ${\displaystyle \beta \colon F(B)\to B}$ ${\displaystyle F}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle h\colon A\to B}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle h\circ \alpha =\beta \circ F(h)}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$

Initial F-algebras

The homomorphisms between -algebras to a fixed functor again form a category in which the objects -algebras are. An initial object in this category is called initial algebra. Is initial, is as algebra isomorphic to how the chart ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle \alpha \colon F(A)\to A}$ ${\displaystyle F(\alpha )\colon F^{2}(A)\to F(A)}$ ${\displaystyle F}$ ${\displaystyle \alpha }$

${\displaystyle {\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}}}$

shows. It is the only homomorphism from to . Therefore the left rectangle commutes. The right commutates trivially. Thus the outer rectangle commutes and is an -algebra homomorphism from to . But since is initial, it must be. On the other hand, due to the left rectangle and the equation just found . ${\displaystyle ?\colon A\to F(A)}$ ${\displaystyle \alpha }$ ${\displaystyle F(\alpha )}$ ${\displaystyle \alpha \circ {?}}$ ${\displaystyle F}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha \circ {?}=\operatorname {id} _{A}}$ ${\displaystyle {?}\circ \alpha =F(\alpha )\circ F(?)=F(\alpha \circ {?})=F(\operatorname {id} _{A})=\operatorname {id} _{F(A)}}$

The meaning of initial algebras lies in the fact that certain recursive structures can be mapped in an orderly manner. If there is an initial -algebra and any other -algebra, then there exists and there is exactly one morphism that is the solution of the equation . This is called catamorphism . ${\displaystyle F}$ ${\displaystyle \alpha \colon F(A)\to A}$ ${\displaystyle F}$ ${\displaystyle \beta \colon F(B)\to B}$ ${\displaystyle F}$ ${\displaystyle \alpha ^{-1}}$ ${\displaystyle h\colon A\to B}$ ${\displaystyle h=\beta \circ F(h)\circ \alpha ^{-1}}$

Theorems of existence for initial algebras

• In Set _C , the category of countable sets and functions, there is an initial algebra for each endofunctioner . ${\displaystyle F}$
• In Rel _C , the category of countable sets and relations, there is an initial algebra for every endo-functor . ${\displaystyle F}$

literature

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 file; 426 kB), vol. 62, 1997