Document Open Access Logo

On Terminal Coalgebras Derived from Initial Algebras

Author Jiří Adámek

PDF

File

Thumbnail PDF
PDF
LIPIcs.CALCO.2019.12.pdf
  • Filesize: 493 kB
  • 21 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Categorical semantics
Keywords
  • terminal coalgebras
  • initial algebras
  • algebraically complete category
  • finitary functor
  • fixed points of functors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

A number of important set functors have countable initial algebras, but terminal coalgebras are uncountable or even non-existent. We prove that the countable cardinality is an anomaly: every set functor with an initial algebra of a finite or uncountable regular cardinality has a terminal coalgebra of the same cardinality.
We also present a number of categories that are algebraically complete and cocomplete, i.e., every endofunctor has an initial algebra and a terminal coalgebra.
Finally, for finitary set functors we prove that the initial algebra mu F and terminal coalgebra nu F carry a canonical ultrametric with the joint Cauchy completion. And the algebra structure of mu F determines, by extending its inverse continuously, the coalgebra structure of nu F.

Cite As Get BibTex

Jiří Adámek. On Terminal Coalgebras Derived from Initial Algebras. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CALCO.2019.12

Author Details

Jiří Adámek
  • Department of Mathematics, Faculty of Electrical Engineering, Czech Technical University in Prague, Czech Republic

Funding

  • Adámek, Jiří: Supported by the Grant Agency of the Czech Republic under the grant 19-00902S.

Acknowledgements

The referees helped improving the presentation of this paper by numerous valuable suggestions.

References

  1. J. Adámek. Free algebras and automata realizations in the language of categories. Comment. Math. Univ. Carolinae, 15:589-602, 1974. Google Scholar
  2. J. Adámek. Final coalgebras are ideal completions of initial algebras. J. Logic Comput., 12:217-242, 2002. Google Scholar
  3. J. Adámek and V. Koubek. Least fixed point of a functor. J. Comput. System Sciences, 19:163-168, 1979. Google Scholar
  4. J. Adámek and V. Koubek. On the greatest fixed point of a set functor. Theoret. Comput. Sci., 150:57-75, 1995. Google Scholar
  5. J. Adámek, S. Milius, L. Sousa, and T. Wissmann. On finitary functors and finitely presentable algebras. CoRR, 2019. arXiv:1902.05788. Google Scholar
  6. J. Adámek and J. Rosický. Locally presentable and accessible categoreis. Cambridge University Press, 1994. Google Scholar
  7. J. Adámek and V. Trnková. Automata and Algebras in Categories. Kluwer Acad. Publ., London, 1990. Google Scholar
  8. M. Barr. Terminal coalgebras in well-founded set theory. Theoret. Comput. Sci., 114:299-315, 1993. Google Scholar
  9. P. Freyd. Algebraically complete categories. Lecture Notes in Math., 1488:95-104, 1970. Google Scholar
  10. T. Jech. Set theory. Academic Press, 1978. Google Scholar
  11. J. Rutten. Universal coalgebra. Theoret. Comput. Sci., 249:3-80, 2000. Google Scholar
  12. M.B. Smyth and G.D. Plotkin. The category-theoretic solution of recursive domain equations. SIAM J. Comput., 11:761-788, 1982. Google Scholar
  13. A. Tarski. Sur la de composition des ensembles en sous-ensembles prèsque disjoint. Fund. Math., 14:205-2015, 1929. Google Scholar
  14. V. Trnková. On descriptive classification of set-functors I., II. Comment. Math. Univ. Carolinae, 12:143-175 and 345-357, 1971. Google Scholar
  15. V. Trnková, J. Adámek, V. Koubek, and J. Reiterman. Free algebras, input processes and free monads. Comment. Math. Univ. Carolinae, 15:589-602, 1974. Google Scholar
  16. J. Worrell. On the final sequence of a finitary set functor. Theoret. Comput. Sci., 338:184-199, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact