Abstract
This paper studies fundamental questions concerning category-theoretic models of induction and recursion. We are concerned with the relationship between well-founded and recursive coalgebras for an endofunctor. For monomorphism preserving endofunctors on complete and well-powered categories every coalgebra has a well-founded part, and we provide a new, shorter proof that this is the coreflection in the category of all well-founded coalgebras. We present a new more general proof of Taylor’s General Recursion Theorem that every well-founded coalgebra is recursive, and we study conditions which imply the converse. In addition, we present a new equivalent characterization of well-foundedness: a coalgebra is well-founded iff it admits a coalgebra-to-algebra morphism to the initial algebra.
A full version of this paper including full proof details is available on arXiv [5].
J. Adámek—Supported by the Grant Agency of the Czech Republic under grant 19-00902S.
S. Milius—Supported by Deutsche Forschungsgemeinschaft (DFG) under project MI 717/5-2.
L. S. Moss—Supported by grant \(\#\)586136 from the Simons Foundation.
Chapter PDF
Similar content being viewed by others
References
Adámek, J.: Free algebras and automata realizations in the language of categories. Comment. Math. Univ. Carolin. 15, 589–602 (1974)
Adámek, J., Herrlich, H., Strecker, G.E.: Abstract and Concrete Categories: The Joy of Cats. Dover Publications, 3rd edn. (2009)
Adámek, J., Lücke, D., Milius, S.: Recursive coalgebras of finitary functors. Theor. Inform. Appl. 41(4), 447–462 (2007)
Adámek, J., Milius, S., Moss, L.S.: Fixed points of functors. J. Log. Algebr. Methods Program. 95, 41–81 (2018)
Adámek, J., Milius, S., Moss, L.S.: On well-founded and recursive coalgebras (2019), full version; available online at http://arxiv.org/abs/1910.09401
Adámek, J., Milius, S., Moss, L.S., Sousa, L.: Well-pointed coalgebras. Log. Methods Comput. Sci. 9(2), 1–51 (2014)
Adámek, J., Milius, S., Sousa, L., Wißmann, T.: On finitary functors. Theor. Appl. Categ. 34, 1134–1164 (2019). available online at https://arxiv.org/abs/1902.05788
Adámek, J., Rosický, J.: Locally Presentable and Accessible Categories. Cambridge University Press (1994)
Borceux, F.: Handbook of Categorical Algebra: Volume 1, Basic Category Theory. Encyclopedia of Mathematics and its Applications, Cambridge University Press (1994)
Capretta, V., Uustalu, T., Vene, V.: Recursive coalgebras from comonads. Inform. and Comput. 204, 437–468 (2006)
Capretta, V., Uustalu, T., Vene, V.: Corecursive algebras: A study of general structured corecursion. In: Oliveira, M., Woodcock, J. (eds.) Formal Methods: Foundations and Applications, Lecture Notes in Computer Science, vol. 5902, pp. 84–100. Springer Berlin Heidelberg (2009)
Eppendahl, A.: Coalgebra-to-algebra morphisms. In: Proc. Category Theory and Computer Science (CTCS). Electron. Notes Theor. Comput. Sci., vol. 29, pp. 42–49 (1999)
Gumm, H.: From \(T\)-coalgebras to filter structures and transition systems. In: Fiadeiro, J.L., Harman, N., Roggenbach, M., Rutten, J. (eds.) Algebra and Coalgebra in Computer Science, Lecture Notes in Computer Science, vol. 3629, pp. 194–212. Springer Berlin Heidelberg (2005)
Jacobs, B.: The temporal logic of coalgebras via Galois algebras. Math. Structures Comput. Sci. 12(6), 875–903 (2002)
Jeannin, J.B., Kozen, D., Silva, A.: Well-founded coalgebras, revisited. Math. Structures Comput. Sci. 27, 1111–1131 (2017)
Kurz, A.: Logics for Coalgebras and Applications to Computer Science. Ph.D. thesis, Ludwig-Maximilians-Universität München (2000)
Lawvere, W.F.: Quantifiers and sheaves. Actes Congès Intern. Math. 1, 329–334 (1970)
Manna, Z., Pnüeli, A.: The Temporal Logic of Reactive and Concurrent Systems: Specification. Springer-Verlag (1992)
Meseguer, J., Goguen, J.A.: Initiality, induction, and computability. In: Algebraic methods in semantics (Fontainebleau, 1982), pp. 459–541. Cambridge Univ. Press, Cambridge (1985)
Milius, S.: Completely iterative algebras and completely iterative monads. Inform. and Comput. 196, 1–41 (2005)
Milius, S., Pattinson, D., Wißmann, T.: A new foundation for finitary corecursion and iterative algebras. Inform. and Comput. 217 (2020), available online at https://doi.org/10.1016/j.ic.2019.104456
Osius, G.: Categorical set theory: a characterization of the category of sets. J. Pure Appl. Algebra 4(79–119) (1974)
Taylor, P.: Towards a unified treatment of induction I: the general recursion theorem (1995–6), preprint, available at www.paultaylor.eu/ordinals/#towuti
Taylor, P.: Practical Foundations of Mathematics. Cambridge University Press (1999)
Trnková, V., Adámek, J., Koubek, V., Reiterman, J.: Free algebras, input processes and free monads. Comment. Math. Univ. Carolin. 16, 339–351 (1975)
Trnková, V.: Some properties of set functors. Comment. Math. Univ. Carolin. 10, 323–352 (1969)
Trnková, V.: On a descriptive classification of set functors I. Comment. Math. Univ. Carolin. 12, 143–174 (1971)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2020 The Author(s)
About this paper
Cite this paper
Adámek, J., Milius, S., Moss, L.S. (2020). On Well-Founded and Recursive Coalgebras. In: Goubault-Larrecq, J., König, B. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2020. Lecture Notes in Computer Science(), vol 12077. Springer, Cham. https://doi.org/10.1007/978-3-030-45231-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-45231-5_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45230-8
Online ISBN: 978-3-030-45231-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)