nLab
initial algebra of an endofunctor

Definition

An initial algebra for an endofunctor $F$ on a category $C$ is an initial object in the category of algebras of $F$.

Properties

Relation to algebras over a monad

The concept of an algebra of an endofunctor is arguably somewhat odd, a more natural concept being that of an algebra over a monad. However, the former can often be reduced to the latter.

Proposition

If $𝒞$ is a complete category, then the category of algebras of an endofunctor $F:𝒞\to 𝒞$ is equivalent to the category of algebras over a monad of the free monad on $F$, if the latter exists.

The proof is fairly straightforward, see for instance (Maciej) or at free monad.

The existence of free monads, on the other hand, can be a tricky question. One general technique is the transfinite construction of free algebras.

Lambek’s theorem

Theorem

If $F$ has an initial algebra $\alpha :F(X)\to X$, then $X$ is isomorphic to $F(X)$ via $\alpha$.

Remark

In this sense, $X$ is a fixed point of $F$. Being initial, $X$ is the smallest fixed point of $F$ in that there is a map from $X$ to any other fixed point (indeed, any other algebra), and this map is an injection if $C$ is Set.

Remark

The dual concept is terminal coalgebra, which is the largest fixed point of $F$.

Proof

Given an initial algebra structure $\alpha :F(X)\to X$, define an algebra structure on $F(X)$ to be $F(\alpha ):F(F(X))\to F(X)$. By initiality, there exists an $F$-algebra map $i:X\to F(X)$, so that

$$\begin{array}{ccc}F(X)& \stackrel{F(i)}{\to }& F(F(X))\\ \alpha \downarrow & & \downarrow F(\alpha )\\ X& \underset{i}{\to }& F(X)\end{array}$$\array{ F(X) & \overset{F(i)}{\to} & F(F(X)) \\ \alpha \downarrow & & \downarrow F(\alpha) \\ X & \underset{i}{\to} & F(X) }

commutes. Now it is trivial, in fact tautological that $\alpha$ is itself an $F$-algebra map $F(X)\to X$. Thus $\alpha \circ i=1_X$, since both sides of the equation are $F$-algebra maps $X\to X$ and $X$ is initial. As a result, $F(\alpha )\circ F(i)=1_{F(X)}$, so that $i\circ \alpha =1_{F(X)}$ according to the commutative square. Hence $\alpha$ is an isomorphism, with inverse $i$.

Adámek’s theorem

In many cases, initial algebras can be constructed in recursive fashion, using the following special case of a theorem due to Adámek.

Theorem (Adámek)

Let $C$ be a category with an initial object $0$ and transfinite composition of lengh $\omega$, hence colimits of sequences $\omega \to C$ (where $\omega$ is the first infinite ordinal), and suppose $F:C\to C$ preserves colimits of $\omega$-chains. Then the colimit $\gamma$ of the chain

$$0\stackrel{i}{\to }F(0)\stackrel{F(i)}{\to }\dots \to F^{(n)}(0)\stackrel{F^{(n)}(i)}{\to }{F}^{(n+1)}(0)\to \dots$$0 \overset{i}{\to} F(0) \overset{F(i)}{\to} \ldots \to F^{(n)}(0) \overset{F^{(n)}(i)}{\to} F^{(n+1)}(0) \to \ldots

carries a structure of initial $F$-algebra.

Proof

The $F$-algebra structure $F\gamma \to \gamma$ is inverse to the canonical map $\gamma \to F\gamma$ out of the colimit (which is invertible by the hypothesis on $F$). The proof of initiality may be extracted by dualizing the corresponding proof given at terminal coalgebra.

This approach can be generalized to the transfinite construction of free algebras.

Semantics for inductive types

Initial algebras of endofunctors are the categorical semantics of extensional inductive types. The generalization to weak initial algebras? captures the notion in intensional type theory and homotopy type theory.

Examples

Natural numbers

The archetypical example of an initial algebra is the set of natural numbers.

Proposition

Let $𝒯$ be topos and let $F:𝒯\to 𝒯$ the functor given by

$$F:X\mapsto *\coprod X.$$F : X \mapsto * \coprod X \,.

Then an initial algebra over $F$ is precisely a natural number object $\mathbb{N}$ in $𝒯$.

Proof

By definition, an $F$-algebra is an object $X$ equipped with a morphism

$$(0,s):*\coprod X\to X,$$(0,s) : * \coprod X \to X \,,

hence equivalently with a point $0:*\to X$ and an endomorphism $s:X\to X$. This being inital means that for $(0_Y,s_Y):*\coprod Y\to Y$ any other morphism, there is a unique morphism $f:X\to Y$ such that the diagram

$$\begin{array}{ccccc}*& \stackrel{0}{\to }& X& \stackrel{s}{\to }& X\\ \downarrow & & {\downarrow }^f& & {\downarrow }^f\\ *& \stackrel{0}{\to }& Y& \stackrel{s}{\to }& Y\end{array}$$\array{ * &\stackrel{0}{\to}& X &\stackrel{s}{\to}& X \\ \downarrow && \downarrow^{\mathrlap{f}} && \downarrow^{\mathrlap{f}} \\ * &\stackrel{0}{\to}& Y &\stackrel{s}{\to}& Y }

commutes. This is the very definition of natural number object $X=\mathbb{N}$.

More examples

Theorem 2 applies in particular to any functor $F:\mathrm{Set}\to \mathrm{Set}$ which is a colimit of finitely representable functors $\mathrm{hom}(n,-):X\mapsto X^n$, as in the following examples.

• Let $A$ be a set, and let $F:\mathrm{Set}\to \mathrm{Set}$ be the functor $F(X)=1+A\times X$. Then the initial $F$-algebra is $A^{*}$, the free monoid on $A$. The $F$-algebra structure is

  $$(e,m\mid ):1+A\times A^{*}\to A^{*}$$(e, m| ): 1 + A \times A^* \to A^*

  where $e:1\to A^{*}$ is the identity and $m\mid :A\times A^{*}\to A^{*}$ is the restriction of the monoid multiplication along the evident inclusion $i\times 1:A\times A^{*}\to A^{*}\times A^{*}$.

  This “fixed point” of $F$ can be thought of as the result of the (slightly nonsensical) calculation

  $$1+A\times X=X\Rightarrow X=\frac{1}{1-A}=1+A+A^2+\dots =A^{*}$$1 + A \times X = X \Rightarrow X = \frac1{1 - A} = 1 + A + A^2 + \ldots = A^*

  which can be made rigorous by interpreting the initial equality as defining the solution $X$ by recursion, and applying the theorem above.

• Let $F:\mathrm{Set}\to \mathrm{Set}$ be the functor $F(X)=1+X^2$. Then the initial $F$-algebra is the set $T$ of isomorphism classes of finite (planar, rooted) binary trees. The $F$-algebra structure is

  $$(r,j):1+T^2\to T$$(r, j): 1 + T^2 \to T

  where $r:1\to T$ names the tree consisting of just a root vertex, and $j:T^2\to T$ creates a tree $t\vee t\prime$ from two trees $t$, $t\prime$ by joining their roots to a new root, so that the root of $t$ becomes the left child and the root of $t\prime$ the right child of the new root.

  The recursive equation

  $$T=1+T^2$$T = 1 + T^2

  would seem to imply that the structure $T$ behaves something like a structural “sixth root of unity”, and indeed the structural isomorphism $T\cong F(T)$ allows one to exhibit an isomorphism

  $$T=T^7$$T = T^7

  constructively, as famously explored in the paper by Andreas Blass, Seven Trees in One.

• Let $F:\mathrm{Set}\to \mathrm{Set}$ be the functor $F(X)=X^{*}$ (the free monoid from an earlier example). Then the initial $F$-algebra is the set of isomorphism classes of finite planar rooted trees (not necessarily binary as in the previous example).

• Let $C$ be the coslice category $\mathbb{Z}\downarrow \mathrm{Ab}$, and let $F:C\to C$ be the functor which pushes out along the multiplication-by-$p$ map $p\cdot -:\mathbb{Z}\to \mathbb{Z}$. Then the initial $F$-algebra is the Pruefer group $\mathbb{Z}[p^{-1}]/\mathbb{Z}$. See the discussion at the n-Category Café, starting here.

• Let $\mathrm{Ban}$ be the category of complex Banach spaces and maps of norm bounded above by $1$, and let $F:ℂ\downarrow \mathrm{Ban}\to ℂ\downarrow \mathrm{Ban}$ be the squaring functor $X\mapsto X\times X$. Then the initial $F$-algebra is $L^1([0,1])$ (with respect to the usual Lebesgue measure). This result is due to Tom Leinster; see this MathOverflow discussion.

Related entries

• inductive type, initial algebra of an endofunctor

• higher inductive type, initial algebra of a presentable ∞-monad

References

A textbook account of the basic theory is in chapter 10 of

• Steve Awodey, Category theory lecture notes (2011) (web)

A brief review of some basics with an eye towards inductive types is in section 2 of

• Steve Awodey, Nicola Gambino, Kristina Sojakova, Inductive types in homotopy type theory (arXiv:1201.3898)

The relation to free monads is discussed in

• Maciej, Free monads and their algebras