Algebra and coalgebra

Algebra and coalgebra are terms used to describe some classes of mathematical structures which are commonly met in mathematics and in computer science. The relationship between algebras and coalgebras appears clear only when their definition is formulated inside category theory: "Algebra" and "coalgebra" are dual concepts. This duality has been observed informally for long time, with algebras used to describe data types, and coalgebras used to describe systems (i.e., abstract machines).

An algebra is commonly described as a set plus some operations on it, and as such is usually used to formalize many kinds of data types in programming languages, like stacks. Let us consider the set of the integer numbers Z, with sum (a binary operation), negation (a unary operation) and the number zero (a constant, i.e., a zero-ary operation). This is an algebra. The signature of an algebra is the information relative to the arity of its operation, being their name ininfluent. For instance, we can consider the three operations of the previous example as a unique "bundle operation" defined as follows. This operation picks a pair of numbers and return their sum - or picks just one number and return its negated - or picks no number at all (say, it picks a fixed nonnumeric input we indicate with *) and returns the number zero. Let us indicate with AxB the cartesian product of two sets A and B, i.e., the sets of all the ordered pairs of elements drawn one from each set, and let us indicate AxA with the simpler notation A^2. Let us also indicate with 1 the singleton set, 1 = {*}, and the union of the (disjoint!) sets A and B with A+B. By synthesizing, the three operations of our algebra can be seen as a single function from Z^2 + Z + 1 to Z. The signature of our algebra can be written as _^2 + _ + 1, where _ is a placeholder for the carrier of choice - Z in our example.

If we consider a generic signature F, an algebra with signature F and carrier A is any function from F(A) to A, i.e., any function picking a complexly structured value, among whose subparts there may be values from A, and returning a value from A.

Coalgebras are defined dually. Given a signature F, a coalgebra with signature F and carrier A is any function from A to F(A), i.e., any function picking a value from A and returning a complexly structured value, among whose subparts there may be values from A.

As algebras are used to formalize data types, coalgebras are used to formalize automata and similar computational systems, or assimilable data types like streams. Let us consider a finite state automaton with states in the set S, with I as input alphabet and with O as output alphabet. An automaton is defined by its transition function, taking a pair (state, input) and returning a pair (new_state, output). In a word, by a function from SxI to SxO. If we apply currying, any function of two arguments can be conveniently described by an equivalent function consuming its first argument, and returning another function which consumes the second one. This means, any function from SxI to SxO can be conveniently described by an equivalent function from S to (SxO)^I, where (SxO)^I is the set of all the functions from I to SxO. In a word: An automaton with input alphabet I and output alphabet O is a coalgebra with signature (_xO)^I, whose carrier is the set of its states.

Algebras and coalgebras have similar properties. For instance, there is a class of algebras (initial algebras) allowing proof and definition of functions by induction, while the corresponding dual class of coalgebras (final coalgebras) allow proof and definition by coinduction. Initial algebras and final coalgebras are used as the meant semantics of formal data type/system specification, because "it is very clear how they are done".

Final remarks:

Note that the notation B^A to mean the set of all the total functions from A to B does NOT clash with the notation where A^2 was used to indicate AxA. Indeed, if 2 is the set with two elements, 2 = {*, **}, a function from 2 to A is an ordered pair, mapping * to its car and ** to its cdr. Then the set of all these functions is, precisely, the set of all these pairs, i.e., the cartesian product AxA! (more precisely, it is isomorphic, i.e. indistinguishable, to it.)
In category theory, signatures are represented by functors. Functors based on the combination of sum (disjoint union), cartesian product and exponentiation _^n are said polynomial functors. Polynomial functors have pleasant properties and are common signatures for many interesting algebras (our example algebra has precisely a polynomial functor as its signature). Unfortunately, interesting coalgebras usually have functors more complex than polynomial ones.

This page is linked from: Bisimulation Congruence Duality Feature-Oriented Programming Induction and Co-induction Initiality and finality