Charles Explorer logo
🇬🇧

Fixed Points of Set Functors: How Many Iterations are Needed?

Publication at Faculty of Mathematics and Physics |
2016

Abstract

The initial algebra for a set functor can be constructed iteratively via a well-known transfinite chain, which converges after a regular infinite cardinal number of steps or at most three steps. We extend this result to the analogous construction of relatively initial algebras.

For the dual construction of the terminal coalgebra Worrell proved that if a set functor is alpha-accessible, then convergence takes at most alpha + alpha steps. But until now an example demonstrating that fewer steps may be insufficient was missing.

We prove that the functor of all alpha-small filters is such an example. We further prove that for beta aecurrency sign alpha the functor of all alpha-small beta-generated filters requires precisely alpha + beta steps and that a certain modified power-set functor requires precisely alpha steps.

We also present an example showing that whether a terminal coalgebra exists at all does not depend solely on the object mapping of the given set functor. (This contrasts with the fact that existence of an initial algebra is equivalent to existence of a mere fixed point.).