Initial Algebra example

Question

If the definition of Initial Algebra is:

"An object is initial if there exists a unique morphism from the object to every object in the category"

Why do we need such object, and could any one give an example ?

Answer 1

An initial algebra is an initial object in the category of $F$-algebras for a given endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$.

This construction is widely used to gives semantics to data-structures in (functional) programming languages. Intuitively, the functor $F$ captures the "shape" of the data-structure (e.g., $F(X) = 1 + A \times X$, with $A$ a fixed set for instance).

The underlying set $\mu F$ of the initial algebra $\langle \mu F, \alpha \rangle$ intuitively captures the set of syntactic expressions you can build by induction on the shape functor (e.g., for the previous functor with $A = \{a,b \}$, $\mu F = \{(1), (a,1), (b,1), (a,a,1), (a,b,1) \ldots \}$ is the set of finite lists of $A$-elements).

The initiality is the key property to construct inductive function (see catamorphism). Some excellent references on this topic:

• Lectures on Semantics: The initial algebra and final coalgebra perspectives
• A Tutorial on (Co)Algebras and (Co)Induction