Initiality and finality
These terms indicate dual concepts in category theory. An object in a category is initial if there is exactly one morphism from it to any other object in the category. An object is final if there is exactly one morphism from any other object in the category to it. In a sense, an initial object is a sort of global minimum, while a terminal object is a sort of global maximum. It is precisely so in ordered sets, which are special cases of categories. It is not exactly so in other categories as the category of sets, where the initial object is the empty set and the terminal object is the singleton set.Initiality and finality are especially important concepts when we refer them to (the categories of) algebras and coalgebras. An algebra is initial if there is exactly one homomorphism from it to any other algebra (with the same signature, of course). Dually, a coalgebra is final if there is exactly one homomorphism from any other coalgebra (again, with the same signature) to it. Initial algebras and final coalgebras are, in a sense, prototypical: Every algebra contains an "image" of an initial algebra, and dually the final coalgebra contains the image of every coalgebra. It will not be a surprise, therefore, that if some signature has an initial algebra, this is unique (up to isomorphism), and similarly the final coalgebra, if exists for a signature, is unique (up to isomorphism). It will also not be a surprise that an initial algebra is minimal and a final coalgebra is simple (intuitively, if an initial algebra were not minimal, there would be a proper subalgebra of the initial algebra, which also would be contained in all other algebras in a unique way: but a proper subalgebra cannot be isomorphic to the containing one. Dually for final coalgebras). Another interesting property is the fact that the operation of an initial algebra (and similarly for a final coalgebra) is an isomorphism.
The properties of initial algebras and final coalgebras make them especially suited as standard models (i.e., as the standard semantics) of algebraic and coalgebraic specifications. They are informally known as "no junk" (for initial algebras it means that they do not contain objects other than those that you can define by means of constructors) and "no surprises" (for initial algebras it means that objects that you would expect different are indeed different, and thus that the algebra has the properties you specified it should have, not other compatible properties you did not specify). Moreover, minimality/simplicity imply that we can use the induction/coinduction principles to prove properties and to define functions on them. Finally, polynomial functors always have initial algebras and final coalgebras, which can be built by means of standard constructions. (Unfortunately, one of the most relevant functors for coalgebras, used to represent infinite forms of nondeterminism, is the powerset functor 2^_, for which there is not the final coalgebra. If it were, the operation f: A -> 2^A would be an isomorphism, and in standard (Cantorian) set theory a set cannot be isomorphic to the set of its subsets. However, in the world of non-well-founded sets and classes such an isomorphism exists.)
A very nice example of initial algebra is the initial algebra of the functor 1 + _, which is the algebra of natural number with zero and successor. This is perhaps the niftiest definition of natural numbers, which has all the properties of Peano's definition: Initiality implies that the operation <0,S> : 1 + N -> N is an isomorphism, i.e., that the natural numbers are "as many as" (i.e. isomorphic) the natural numbers plus another element, the zero, and that the successor operation S is a bijection on the naturals without that element. This fixes the first four Peano axioms. Minimality yields the induction principle, which is the fifth axiom. The functor 1 + _ is almost the simplest we can imagine.
An example of final coalgebra is the usual coalgebra of streams, i.e., of the infinitely long sequences of symbols from an alphabet S (or equivalently of the functions s : N -> S), which is the final coalgebra of the functor S x _.
This page is linked from: Algebra and coalgebra Duality Induction and Co-induction