Terminal Coalgebras as Sets or Classes
For endofunctors H of Set, coalgebras represent dynamical systems of the type expressed by H, and a terminal coalgebra T represents the collection of all possible behaviours of states of such systems.
This collection can be a class: not every set functor has a terminal coalgebra, but every endofunctor of the category of classes has one. And every set functor has an essentially unique extension to the category of classes.
Example: the power-set functor P extends to the functor P' assigning to every class X the class P'X of all (small) subsets of X . A terminal coalgebra is the algebra of all rooted, non-ordered trees modulo the greatest bisimulation.
The above result sharpens the Final Coalgebra Theorem of Aczel and Mendler: they proved that every set-based endofunctor has a terminal coalgebra. We now prove that all endofunctors are set-based.
Areas of interest
Jirí Adámek (University of Braunschweig)
October 13, 2003