Birkhoff's Covariety Theorem without limitations

Jiří Adámek

Commentationes Mathematicae Universitatis Carolinae (2005)

  • Volume: 46, Issue: 2, page 197-215
  • ISSN: 0010-2628

Abstract

top
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).

How to cite

top

Adá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
  1. 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
  2. Adámek J., Free algebras and automata realizations in the language of categories, Comment. Math. Univ. Carolinae 15 (1974), 589-602. (1974) MR0352209
  3. Adámek J., Koubek V., On the greatest fixed point of a set functor, Theoret. Comput. Sci. 150 (1995), 57-75. (1995) MR1357120
  4. Adámek J., Milius S., Velebil J., On coalgebra based on classes, Theoret. Comput. Sci. 316 (2004), 2-23. (2004) Zbl1047.18005MR2074922
  5. Adámek J., Porst H.-E., On varieties and covarieties in a category, Math. Structures Comput. Sci. 13 (2003), 201-232. (2003) Zbl1041.18007MR1994641
  6. Adámek J., Trnková V., Automata and Algebras in a Category, Kluwer Academic Publishers, Dordrecht, 1990. MR1071169
  7. 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
  8. Barr M., Terminal coalgebras in well-founded set theory, Theoret. Comput. Sci. 114 (1993), 299-315. (1993) Zbl0779.18004MR1228862
  9. Gumm H.P., Birkhoff's variety theorem for coalgebras, Contributions to General Algebra 13 (2000), 159-173. (2000) MR1854581
  10. Herrlich H., Remarks on categories of algebras defined by a proper class of operations, Quaestiones Math. 13 (1990), 385-393. (1990) Zbl0733.18004MR1084749
  11. Kurz A., Rosický J., Modal predicates and coequations, Electronic Notes in Theoret. Comput. Sci. 65 1 (2002). (2002) 
  12. Reiterman J., One more categorical model of universal algebra, Math. Z. 161 (1978), 137-146. (1978) Zbl0363.18007MR0498325
  13. Rutten J.J.M.M., Universal coalgebra: a theory of systems, Theoret. Comput. Sci. 249 1 (2000), 30-80. (2000) Zbl0951.68038MR1791953
  14. 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
  15. Worrell J., On Coalgebras and Final Semantics, PhD Thesis, Oxford University Computing Laboratory, 2000, accepted for publication in Theoret. Comput. Sci. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.