Centre for Mathematics, University of Coimbra

<Reference List>
Type:	Preprint
National /International:	International
Title:	On final coalgebras of power-set functors and saturated trees
Publication Date:	2012-10-24
Authors:	- Jirí Adámek - Paul Levy - Stefan Milius - Lawrence S. Moss - Lurdes Sousa
Abstract:	The final coalgebra for the finite power-set functor was described by Worrell who also proved that the final chain converges in $\omega + \omega$ steps. We describe the step $\omega$ as the set of saturated trees, a concept equivalent to the modally saturated trees introduced by K. Fine in the 1970s in his study of modal logic. And for the bounded power-set functors $\PP_\lambda$, where $\lambda$ is an infinite regular cardinal, we prove that the construction needs precisely $\lambda+\omega$ steps. We also generalize Worrell's result to $M$-labeled trees for a commutative monoid $M$, yielding a final coalgebra for the corresponding functor $\MM_f$ studied by H.-P. Gumm and T. Schr\"oder. We describe the final chain of the power-set functor by introducing the concept of $i$-saturated tree for all ordinals $i$, and then prove that for $i$ of cofinality $\omega$, the $i$-th step in the final chain consists of all $i$-saturated, strongly extensional trees.
Institution:	DMUC 12-39
Online version:	http://www.mat.uc.pt...prints/eng_2012.html
Download:	Not available