Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
Birkhoff's Theorem; covariety; coequation
Birkhoff's Theorem; covariety; coequation
Summary:
J. Rutten proved, for accessible endofunctors $F$ of {\bf Set}, the dual Birk\-hoff's Variety Theorem: a collection of $F$-coalgebras is presentable by coequations ($=$ subobjects of cofree coalgebras) iff it is closed under quotients, subcoalgebras, and coproducts. This result is now proved to hold for all endofunctors $F$ of {\bf Set} provided that coequations are generalized to mean subchains of the cofree-coalgebra chain. For the concept of coequation introduced by H. Porst and the author, which is a subobject of a member of the cofree-coalgebra chain, the analogous result is false, in general. This answers negatively the open problem of A. Kurz and J. Rosick'y whether every covariety can be presented by equations w.r.t. co-operations. In contrast, in the category of classes Birkhoff's Covariety Theorem is proved to hold for all endofunctors (using Rutten's original concept of coequations).
References:
[AAMV] Aczel P., Adámek J., Milius S., Velebil J.: Infinite trees and completely iterative theories - a coalgebraic view. Theoret. Comput. Sci. 300 (2003), 1-45. MR 1976176 | Zbl 1028.68077
[A] Adámek J.: Free algebras and automata realizations in the language of categories. Comment. Math. Univ. Carolinae 15 (1974), 589-602. MR 0352209
[AK] Adámek J., Koubek V.: On the greatest fixed point of a set functor. Theoret. Comput. Sci. 150 (1995), 57-75. MR 1357120
[AMV] Adámek J., Milius S., Velebil J.: On coalgebra based on classes. Theoret. Comput. Sci. 316 (2004), 2-23. MR 2074922 | Zbl 1047.18005
[AP] Adámek J., Porst H.-E.: On varieties and covarieties in a category. Math. Structures Comput. Sci. 13 (2003), 201-232. MR 1994641 | Zbl 1041.18007
[AT] Adámek J., Trnková V.: Automata and Algebras in a Category. Kluwer Academic Publishers, Dordrecht, 1990. MR 1071169
[AH] Awodey S., Hughes J.: Modal operators and the formal dual of Birkhoff's completness theorem. Math. Structures Comput. Sci. 13 (2003), 233-258. MR 1994642
[B] Barr M.: Terminal coalgebras in well-founded set theory. Theoret. Comput. Sci. 114 (1993), 299-315. MR 1228862 | Zbl 0779.18004
[G] Gumm H.P.: Birkhoff's variety theorem for coalgebras. Contributions to General Algebra 13 (2000), 159-173. MR 1854581
[H] Herrlich H.: Remarks on categories of algebras defined by a proper class of operations. Quaestiones Math. 13 (1990), 385-393. MR 1084749 | Zbl 0733.18004
[KR] Kurz A., Rosický J.: Modal predicates and coequations. Electronic Notes in Theoret. Comput. Sci. 65 1 (2002).
[Re] Reiterman J.: One more categorical model of universal algebra. Math. Z. 161 (1978), 137-146. MR 0498325 | Zbl 0363.18007
[Ru] Rutten J.J.M.M.: Universal coalgebra: a theory of systems. Theoret. Comput. Sci. 249 1 (2000), 30-80. MR 1791953 | Zbl 0951.68038
[RT] Rutten J.J.M.M., Turi D.: On the foundations of final semantics: nonstandard sets, metric spaces, partial orders. Lecture Notes in Comput. Sci. 666, Springer, Berlin, 1993, pp.477-530. MR 1255996
[W] Worrell J.: On Coalgebras and Final Semantics. PhD Thesis, Oxford University Computing Laboratory, 2000, accepted for publication in Theoret. Comput. Sci.
Search
Partner of
