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.
Other articles related to "algebras, initial, initial algebra, algebra, initial algebras":
... If the category of F-algebras for a given endofunctor F has an initial object, it is called an initial algebra ... The algebra in the above example is an initial algebra ... such as lists and trees, can be obtained as initial algebras of specific endofunctors ...
... used in programming, such as lists and trees, can be obtained as initial algebras of specific endofunctors ... While there may be several initial algebras for a given endofunctor, they are unique up to isomorphism, which informally means that the "observable" properties of a data structure can be adequately ... into one function, they give , which makes this an F-algebra for the endofunctor F sending to ...
Famous quotes containing the words algebra and/or initial:
“Poetry has become the higher algebra of metaphors.”
—José Ortega Y Gasset (18831955)
“For those parents from lower-class and minority communities ... [who] have had minimal experience in negotiating dominant, external institutions or have had negative and hostile contact with social service agencies, their initial approaches to the school are often overwhelming and difficult. Not only does the school feel like an alien environment with incomprehensible norms and structures, but the families often do not feel entitled to make demands or force disagreements.”
—Sara Lawrence Lightfoot (20th century)