Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T01:10:49.441Z Has data issue: false hasContentIssue false

A general final coalgebra theorem

Published online by Cambridge University Press:  27 May 2005

JIŘÍ ADÁMEK
Affiliation:
Institute of Theoretical Computer Science, Technical University of Braunschweig, Germany E-mail: adamek@iti.cs.tu-bs.de
STEFAN MILIUS
Affiliation:
Institute of Theoretical Computer Science, Technical University of Braunschweig, Germany E-mail: milius@iti.cs.tu-bs.de
JIŘÍ VELEBIL
Affiliation:
Faculty of Electrical Engineering, Czech Technical University, Prague
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

By the Final Coalgebra Theorem of Aczel and Mendler, every endofunctor of the category of sets has a final coalgebra, which, however, may be a proper class. We generalise this to all ‘well-behaved’ categories ${\frak K}$. The role of the category of classes is played by a free cocompletion ${\frak K}^\infty$ of ${\frak K}$ under transfinite colimits, that is, colimits of ordinal-indexed chains. Every endofunctor $F$ of ${\frak K}$ has a canonical extension to an endofunctor $F^\infty$ of ${\frak K}^\infty$, which is proved to have a final coalgebra (and an initial algebra). Based on this, we prove a general solution theorem: for every endofunctor of a locally presentable category ${\frak K}$ all guarded equation-morphisms have unique solutions. The last result does not need the extension ${\frak K}^\infty$: the solutions are always found within the category ${\frak K}$.

Information

Type
Paper
Copyright
2005 Cambridge University Press