Adamek, Jiri ;
Milius, Stefan ;
Moss, Lawrence S. ;
Sousa, Lurdes
PowerSet Functors and Saturated Trees
Abstract
We combine ideas coming from several fields, including modal logic, coalgebra, and set theory. Modally saturated trees were introduced by K. Fine in 1975. We give a new purely combinatorial formulation of modally saturated trees, and we prove that they form the limit of the final omegaopchain of the finite powerset functor Pf. From that, we derive an alternative proof of J. Worrell's description of the final coalgebra as the coalgebra of all strongly extensional, finitely branching trees. In the other direction, we represent the final coalgebra for Pf in terms of certain maximal consistent sets in the modal logic K. We also generalize Worrell's result to Mlabeled trees for a commutative monoid M, yielding a final coalgebra for the corresponding functor Mf studied by H. P. Gumm and T. Schröder. We introduce the concept of an isaturated tree for all ordinals i, and then prove that the ith step in the final chain of the power set functor consists of all isaturated trees. This leads to a new description of the final coalgebra for the restricted powerset functors Plambda (of subsets of cardinality smaller than lambda).
BibTeX  Entry
@InProceedings{adamek_et_al:LIPIcs:2011:3219,
author = {Jiri Adamek and Stefan Milius and Lawrence S. Moss and Lurdes Sousa},
title = {{PowerSet Functors and Saturated Trees}},
booktitle = {Computer Science Logic (CSL'11)  25th International Workshop/20th Annual Conference of the EACSL},
pages = {519},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897323},
ISSN = {18688969},
year = {2011},
volume = {12},
editor = {Marc Bezem},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3219},
URN = {urn:nbn:de:0030drops32194},
doi = {10.4230/LIPIcs.CSL.2011.5},
annote = {Keywords: saturated tree, extensional tree, final coalgebra, powerset functor, modal logic}
}
2011
Keywords: 

saturated tree, extensional tree, final coalgebra, powerset functor, modal logic 
Seminar: 

Computer Science Logic (CSL'11)  25th International Workshop/20th Annual Conference of the EACSL

Issue date: 

2011 
Date of publication: 

2011 