Initial Algebra

Definition

Let $F:\mathcal{C}\to \mathcal{C}$ be an endofunctor. An F-algebra is a pair $(X,\alpha )$ where $X\in \mathcal{C}$ is an object and $\alpha :FX\to X$ is a morphism. The object $X$ is the carrier and $\alpha$ is the structure map.

Homomorphisms

Given $F$-algebras $(X,\alpha )$ and $(Y,\beta )$, an algebra homomorphism is a morphism $\theta :X\to Y$ in $\mathcal{C}$ such that the following diagram commutes:

\usepackage{tikz-cd}
\begin{document}
\begin{tikzcd}
FX \arrow[r, "F\theta"] \arrow[d, "\alpha"'] & FY \arrow[d, "\beta"] \\
X \arrow[r, "\theta"'] & Y
\end{tikzcd}
\end{document}

Initial Algebra

An initial F-algebra is an initial object in the category $Alg(F)$. It is typically denoted $(\mu F,in)$ where $in:F(\mu F)\to \mu F$. By Lambek’s Lemma, if an initial $F$-algebra exists, the structure map $in$ is an isomorphism in $\mathcal{C}$, meaning $\mu F\cong F(\mu F)$. This identifies $\mu F$ as a least fixed point of the functor $F$.

Catamorphisms

For any $F$-algebra $(A,\beta )$, the unique homomorphism $h:(\mu F,in)\to (A,\beta )$ from the initial algebra is called a catamorphism. In functional programming and type theory, this corresponds to the principle of iteration or recursion over an inductive type.

See Also

• Initial Algebra
• Coalgebra (Category Theory)
• Generalized Algebraic Theory
• Universal Algebra
• Algebra over a Monad

References

• riehl2016-category-theory