Colóquio 

11/01/2001, 16:30 — 17:30 — Anfiteatro Pa1, Pavilhão de Matemática
Jiri Adamek, Technische Universität Braunschweig

Initial algebras, final coalgebras and specification of systems

The fact that natural numbers can be presented as an initial algebra of a very simple endofunctor \(F\) of the category of sets (viz., \(F: X \mapsto X + 1 )\), and the algebra of finite binary trees as an initial algebra of the endofunctor \(G: X \mapsto (X \times X) + 1\) has inspired in the l970s the theory of abstract data types. A part of that theory has been concerned with infinite structures (e.g., infinite words and infinite trees), for which the formalism of complete partial orders (CPO) or complete metric spaces has been applied. It turns out that another very natural approach to these infinite structures is to consider the dual concept of intial algebra, namely, final coalgebra. As recently demonstrated by J. Rutten, coalgebras present a convenient formalism for describing systems. And final coalgebras often represent important structures, e.g. the (co-)algebra of finite and infinite binary trees is final for the above functor \(G\). Moreover, each of these coalgebras carries a natural CPO structure which, thus, need not be assumed a priori.