Initial algebra

In mathematics, an initial algebra is an initial object in the category of F {displaystyle F} -algebras for a given endofunctor F {displaystyle F} . This initiality provides a general framework for induction and recursion. In mathematics, an initial algebra is an initial object in the category of F {displaystyle F} -algebras for a given endofunctor F {displaystyle F} . This initiality provides a general framework for induction and recursion. For instance, consider the endofunctor 1 + ( − ) {displaystyle 1+(-)} on the category of sets, where 1 {displaystyle 1} is the one-point (singleton) set, the terminal object in the category. An algebra for this endofunctor is a set X {displaystyle X} (called the carrier of the algebra) together with a point x ∈ X {displaystyle xin X} and a function X → X {displaystyle X o 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 × ( − ) {displaystyle 1+mathbf {N} imes (-)} on the category of sets, where N {displaystyle mathbf {N} } is the set of natural numbers. An algebra for this endofunctor is a set X {displaystyle X} together with a point x ∈ X {displaystyle xin X} and a function N × X → X {displaystyle mathbf {N} imes X o 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. In categories with binary coproducts, the definitions just given are equivalent to the usual definitions of a natural number object and a list object, respectively. Dually, a final coalgebra is a terminal object in the category of F {displaystyle F} -coalgebras. The finality provides a general framework for coinduction and corecursion. For example, using the same functor 1 + ( − ) {displaystyle 1+(-)} as before, a coalgebra is a set X {displaystyle X} together with a truth-valued test function p : X → 2 {displaystyle pcolon X o 2} and a partial function f : X → X {displaystyle fcolon X o X} whose domain is formed by those x ∈ X {displaystyle xin X} for which p ( x ) = 0 {displaystyle p(x)=0} . The set N ∪ { ω } {displaystyle mathbf {N} cup {omega }} consisting of the natural numbers extended with a new element ω {displaystyle omega } is the carrier of the final coalgebra in the category, where p {displaystyle p} is the test for zero: p ( 0 ) = 1 {displaystyle p(0)=1} and p ( n + 1 ) = p ( ω ) = 0 {displaystyle p(n+1)=p(omega )=0} , and f {displaystyle f} is the predecessor function (the inverse of the successor function) on the positive naturals, but acts like the identity on the new element ω {displaystyle omega } : f ( n + 1 ) = n {displaystyle f(n+1)=n} , f ( ω ) = ω {displaystyle f(omega )=omega } . This set N ∪ { ω } {displaystyle mathbf {N} cup {omega }} that is the carrier of the final coalgebra of 1 + ( − ) {displaystyle 1+(-)} is known as the set of conatural numbers. For a second example, consider the same functor 1 + N × ( − ) {displaystyle 1+mathbf {N} imes ({mathord {-}})} as before. In this case the carrier of the final coalgebra consists of all lists of natural numbers, finite as well as infinite. The operations are a test function testing whether a list is empty, and a deconstruction function defined on nonempty lists returning a pair consisting of the head and the tail of the input list. Consider the endofunctor F : S e t → S e t {displaystyle F:mathbf {Set} o mathbf {Set} } sending X {displaystyle X} to 1 + X {displaystyle 1+X} . Define