Birkhoff's Covariety Theorem without limitations
Commentationes Mathematicae Universitatis Carolinae (2005)
- Volume: 46, Issue: 2, page 197-215
- ISSN: 0010-2628
Access Full Article
topAbstract
topHow to cite
topAdámek, Jiří. "Birkhoff's Covariety Theorem without limitations." Commentationes Mathematicae Universitatis Carolinae 46.2 (2005): 197-215. <http://eudml.org/doc/249568>.
@article{Adámek2005,
abstract = {J. Rutten proved, for accessible endofunctors $F$ of Set, the dual Birkhoff’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 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).},
author = {Adámek, Jiří},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {Birkhoff's Theorem; covariety; coequation; Birkhoff's theorem; covariety; coequation},
language = {eng},
number = {2},
pages = {197-215},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Birkhoff's Covariety Theorem without limitations},
url = {http://eudml.org/doc/249568},
volume = {46},
year = {2005},
}
TY - JOUR
AU - Adámek, Jiří
TI - Birkhoff's Covariety Theorem without limitations
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2005
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 46
IS - 2
SP - 197
EP - 215
AB - J. Rutten proved, for accessible endofunctors $F$ of Set, the dual Birkhoff’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 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).
LA - eng
KW - Birkhoff's Theorem; covariety; coequation; Birkhoff's theorem; covariety; coequation
UR - http://eudml.org/doc/249568
ER -
References
top- 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. (2003) Zbl1028.68077MR1976176
- Adámek J., Free algebras and automata realizations in the language of categories, Comment. Math. Univ. Carolinae 15 (1974), 589-602. (1974) MR0352209
- Adámek J., Koubek V., On the greatest fixed point of a set functor, Theoret. Comput. Sci. 150 (1995), 57-75. (1995) MR1357120
- Adámek J., Milius S., Velebil J., On coalgebra based on classes, Theoret. Comput. Sci. 316 (2004), 2-23. (2004) Zbl1047.18005MR2074922
- Adámek J., Porst H.-E., On varieties and covarieties in a category, Math. Structures Comput. Sci. 13 (2003), 201-232. (2003) Zbl1041.18007MR1994641
- Adámek J., Trnková V., Automata and Algebras in a Category, Kluwer Academic Publishers, Dordrecht, 1990. MR1071169
- Awodey S., Hughes J., Modal operators and the formal dual of Birkhoff's completness theorem, Math. Structures Comput. Sci. 13 (2003), 233-258. (2003) MR1994642
- Barr M., Terminal coalgebras in well-founded set theory, Theoret. Comput. Sci. 114 (1993), 299-315. (1993) Zbl0779.18004MR1228862
- Gumm H.P., Birkhoff's variety theorem for coalgebras, Contributions to General Algebra 13 (2000), 159-173. (2000) MR1854581
- Herrlich H., Remarks on categories of algebras defined by a proper class of operations, Quaestiones Math. 13 (1990), 385-393. (1990) Zbl0733.18004MR1084749
- Kurz A., Rosický J., Modal predicates and coequations, Electronic Notes in Theoret. Comput. Sci. 65 1 (2002). (2002)
- Reiterman J., One more categorical model of universal algebra, Math. Z. 161 (1978), 137-146. (1978) Zbl0363.18007MR0498325
- Rutten J.J.M.M., Universal coalgebra: a theory of systems, Theoret. Comput. Sci. 249 1 (2000), 30-80. (2000) Zbl0951.68038MR1791953
- 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. MR1255996
- Worrell J., On Coalgebras and Final Semantics, PhD Thesis, Oxford University Computing Laboratory, 2000, accepted for publication in Theoret. Comput. Sci.
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.