In mathematics, an initial algebra is an initial object in the category of F-algebras for a given endofunctor F. The initiality provides a general framework for induction and recursion.
For instance, consider the endofunctor 1+(-) on the category of sets, where 1 is the one-point set, the terminal object in the category. An algebra for this endofunctor is a set X (called the carrier of the algebra) together with a point x ∈ X and a function X→X. The set of natural numbers is the carrier of the initial such algebra: the point is zero and the function is the successor map.
For a second example, consider the endofunctor 1+N×(-) on the category of sets, where N is the set of natural numbers. An algebra for this endofunctor is a set X together with a point x ∈ X and a function N×X → X. The set of finite lists of natural numbers is the initial such algebra. The point is the empty list, and the function is cons, taking a number and a finite list, and returning a new finite list with the number at the head.
Read more about Initial Algebra: Final Coalgebra, Theorems, Example, Use in Computer Science
Famous quotes containing the words initial and/or algebra:
“No punishment has ever possessed enough power of deterrence to prevent the commission of crimes. On the contrary, whatever the punishment, once a specific crime has appeared for the first time, its reappearance is more likely than its initial emergence could ever have been.”
—Hannah Arendt (1906–1975)
“Poetry has become the higher algebra of metaphors.”
—José Ortega Y Gasset (1883–1955)