F-algebra
From Wikipedia, the free encyclopedia
In mathematics, specifically in category theory, an F-algebra for an endofunctor
is an object A of 
together with a -morphism
.
In this sense F-algebras are dual to F-coalgebras.
A homomorphism from F-algebra (A,α) to F-algebra (B,β) is a morphism
in such that
.
Thus the F-algebras constitute a category.
[edit] Example
Consider the functor 
that sends a set X to 1 + X. Here, Set denotes the category of sets, + denotes the usual coproduct given by disjoint union, and 1 is a terminal object (i.e. any singleton set). Then the set N of natural numbers together with the function ![[\mathrm{zero},\mathrm{succ}] : 1+N\to N](../../../math/e/3/c/e3c9dd60118d8c89a9c10c3b5fe0787e.png)
, which is the coproduct of the functions 
(whose image is 0) and 
(which sends an integer n to n+1), is an F-algebra.
[edit] Initial algebra
If the category of F-algebras for a given endofunctor F has an initial object, it is called an initial algebra. The algebra (N,[zero,succ]) in the above example is an initial algebra. Various finite data structures used in programming, such as lists and trees, can be obtained as initial algebras of specific endofunctors.
See also Universal algebra.
