Concept

Initial algebra

In mathematics, an initial algebra is an initial object in the of F-algebras for a given endofunctor F. This initiality provides a general framework for induction and recursion. Consider the endofunctor F : Set → Set sending X to 1 + X, where 1 is the one-point (singleton) 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 function f : (1 + X) → X. Defining such a function amounts to defining a point and a function X → X. Define and Then the set N of natural numbers together with the function [zero,succ]: 1 + N → N is an initial F-algebra. The initiality (the universal property for this case) is not hard to establish; the unique homomorphism to an arbitrary F-algebra (A, [e, f]), for e: 1 → A an element of A and f: A → A a function on A, is the function sending the natural number n to fn(e), that is, f(f(...(f(e))...)), the n-fold application of f to e. The set of natural numbers is the carrier of an initial algebra for this functor: the point is zero and the function is the successor function. 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 function 1 + N × X → X. To define such a function, we need a point and a function N × X → X. The set of finite lists of natural numbers is an initial algebra for this functor. 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-coalgebras. The finality provides a general framework for coinduction and corecursion. For example, using the same functor 1 + (−) as before, a coalgebra is defined as a set X together with a function f : X → (1 + X).

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.