2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ The quote only define "initial" not "initial algebra". $\endgroup$ – Dave Clarke Jan 17 '13 at 12:05
  • $\begingroup$ Algebra is pair of (S,F) where S is a set and F is the functions on this set $\endgroup$ – M.M Jan 17 '13 at 12:10
5
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ What are $1$, $+$, an $\times$ notations in F(X) definition above? $\endgroup$ – qartal May 22 '15 at 19:55
  • 1
    $\begingroup$ terminal object, coproduct and product (respectively) in C $\endgroup$ – Romuald Jul 9 '15 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.