Terminal coalgebras and tree-structures
by
Christoph Schubert
University of Bremen, Department of Mathematics
Coauthors: Christian Dzierzon

It is well-known that in the category CoAlgF of F-coalgebras for a given endofunctor F:Set --> Set the terminal object can be constructed as a limit of a certain descending chain. In case of polynomial functors F=H_\Sigma for bounded signatures \Sigma, this limit-object in the corresponding category CoAlg\Sigma is interpreted as the set T of all \Sigma-labelled trees with ''tree-detupling'' dynamic \theta in [1]. In the following we give a direct and more intuitive proof of this fact, and also a direct description of the unique homomorphism (A, \alpha) --> (T, \theta) for a \Sigma-coalgebra (A, \alpha).

[1] J. Adámek, V. Koubek: On the greatest fixed point of a set functor, Theoretical Computer Science 150, S. 57-75 (1995).

Date received: January 30, 2003