# Fixed Points of Functors - A Short Abstract

Jiří Adámek

► To cite this version:

Jiří Adámek. Fixed Points of Functors - A Short Abstract. 13th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2016, Eindhoven, Netherlands. pp.1-4, 10.1007/978-3-319-40370-0_1 . hal-01446029

HAL Id: hal-01446029

https://inria.hal.science/hal-01446029

Submitted on 25 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# FIXED POINTS OF FUNCTORS - A SHORT
ABSTRACT

Jiří Adámek

Institute for Theoretical Computer Science, Technische Universität Braunschweig
j.adamek@tu-braunschweig.de

Fixed points of endofunctors play a central role in program semantics (initial algebras as recursive specification of domains), in coalgebraic theory of systems (terminal coalgebras and coinduction) and in a number of other connections such as iterative theories (rational fixed point). In this survey we present some older and new results on the structure of the three fixed points we have mentioned.

## 1 INITIAL ALGEBRAS

The classical example of $\Sigma$-algebras as algebras for the polynomial set functor $F_\Sigma$ yields the initial algebra

$$ \mu F_\Sigma = \text{all finite } \Sigma\text{-trees.} $$

This holds for all finitary signatures, whereas for the infinitary ones the initial algebra is formed by all well-founded trees. These are the trees in which every path is finite. The concept of well-foundedness is fundamental for initial algebras. This is a property of coalgebras studied by Osius [9] and Taylor [12]. In [4] we have proved that for all set functors $F$ the initial algebra coincides with the terminal well-founded coalgebra. And every fixed point of $F$ has a largest well-founded part which is the initial algebra of $F$, see [3]

The iterative construction of $\mu F$ as $F^i(0)$ (for some ordinal $i$), introduced in [1], converges for every set functor with a fixed point, see [13]. Moreover the least such ordinal $i$ is an infinite regular cardinal or at most 3, as proved in [6]. In contrast,

- on the category of many-sorted sets convergence can take place at any ordinal, and

- on the category of graphs endofunctors exist having an initial algebra although the iterative construction does not converge,

see [6].

Most of the above results extend from set functors to enfodunctors of "reasonable" categories preserving monomorphisms. For example locally finitely presentable categories whose initial object is simple are "reasonable".
## 2 TERMINAL COALGEBRAS

The importance of terminal coalgebras as systems was demonstrated by Rutten in his fundamental paper [10].

A number of classical examples are special cases of the following:

$$ \nu F_{\Sigma} = \text{all } \Sigma\text{-trees.} $$

The case of automata with $n$ inputs, $H_n X = X^n \times \{0, 1\}$, is an example where $\Sigma$ consists of two $n$-ary operations (and $\Sigma$-trees just represent languages in $n^*$). And streams, $FX = A \times X + B$, correspond to unary operations in $A$ and constants in $B$.

In case of set functors, it is useful to work with pointed coalgebras. E.g., the classical automata are pointed coalgebras for $H_n$.

**Definition 1.** A well-pointed coalgebra is a pointed coalgebra having no proper subobject and no proper quotient.

Thus minimal automata are precisely the well-pointed coalgebras for $H_n$. Let $T$ be the collection of all well-pointed coalgebras up to isomorphism. If $F$ is a set functor preserving intersections, every pointed coalgebra has a canonical "minimization" to a well-pointed one. This yields a coalgebra structure on $T$. And in [4] we presented the following characterizations:

$$ \nu F = \text{all well-pointed coalgebras(up to isomorphism)} $$

and

$$ \mu F = \text{all well-founded well-pointed coalgebras (up to isomorphism).} $$

"The dual of the iterative initial-algebra construction, i.e. the cochain $F^i(1)$ as a construction of $\nu F$, was first explicitly considered by Barr [7]. In contrast to the initial chain the convergence does not always happen at a cardinal: Worrell proved that for the finite power-set functor that cochain converges in $\omega+\omega$ steps. And for all $\lambda$-accessible set functors (i.e., those preserving $\lambda$-filtered colimits), he proved that the construction converges in $\lambda+\lambda$ steps or sooner, see [14]. Until recently, for uncountable $\lambda$, no example has been known where the full $\lambda+\lambda$ steps are actually needed. Such an example is the functor of all $\lambda$-generated filters, see [2].

An important classical result concerns enriched endofunctors of the cartesian closed category CPO (of posets with directed joins and a bottom and strict continuous maps): Smyth and Plotkin proved in [11] that the terminal coalgebra equals the initial algebra, and both constructions converge in $\omega$ steps. This is
based on the limit-colimit coincidence for embedding-projection pairs of Scott. In [3] we prove that for the (much wider) class of endofunctors that are just locally monotone the existence of a fixed point implies that the terminal coalgebra exists and equals the initial algebra.

# 3 RATIONAL FIXED POINT

This (much younger) fixed point arose in the study of iterative algebras. These are algebras $A$ that have a unique solution of every finite guarded system of recursive equations (with parameters in $A$). In [5] we proved that every finitary set functor has an initial iterative algebra which is a fixed point, notation: $\rho F$. And we called this the rational fixed point. Classical examples: for automata as coalgebras we have

$$ \rho H_n = \text{all regular languages in } n^*, $$

and for general signatures

$$ \rho F_{\Sigma} = \text{all rational } \Sigma\text{-trees,} $$

that is, trees that have, up to isomorphism, only finitely many subtrees.

The rational fixed point can be described as the filtered colimit of all finite coalgebras. This has inspired Milius [8] to define locally finite coalgebras for a set functor as coalgebras that are directed unions of finite subcoalgebras. And then he proved that

$$ \rho F = \text{the terminal locally finite coalgebra.} $$

In a complete analogy to the above characterization of the initial and terminal fixed point we have that

$$ \rho F = \text{all finite well-pointed coalgebras (up to isomorphism).} $$

All the above generalizes easily to finitary endofunctors of all finitely locally presentable categories.

Can we play the same game with countable sets in place of finite ones? No, only finite sets yield something new: the terminal locally countable coalgebra is all of $\nu F$, see [5].

# References

1. Adámek, J.: Free algebras and automata realizations in the language of categories. Comment. Math. Univ. Carolinae 15, 589–602 (1974)

2. Adámek, J., Koubek, V., Palm, T.: Fixed points of set functors: how many iterations are needed?, submitted.

3. Adámek, J., Milius, S., Moss, L.: Initial algebras and terminal coalgebras, to appear
4. Adámek, J., Milius, S., Moss, S., Sousa, L.: Well-pointed coalgebras. Logical Meth. Comput. Sci. 9, 1–51 (2013)

5. Adámek, J., Milius, S., Velebil, J.: Iterative algebras at work. Math. Struct. Comput. Sci. 16, 1085–1131 (2006)

6. Adámek, J., Trnková, V.: Initial algebras and terminal coalgebras in many-sorted sets. Mathem. Str. Comput. Sci. 21, 481–509 (2011)

7. Barr, M.: Terminal coalgebras in well-founded set theory. Theoret. Comput. Sci. 124, 182–192 (1994)

8. Milius, S.: A sound and complete calculus for finite stream circuits. Proc. 25th Annual Symposium on Logic in Computer Science (LICS’10), IEEE Computer Society (2010)

9. Osius, G.: Categorical set theory: a characterization of the category of sets. J. Pure Appl. Algebra 4, 79–119 (1974)

10. Rutten, J.J.M.M.: Universal coalgebra: a theory of systems. Theoret. Comput. Sci. 249, 3–80 (2000)

11. Smyth, M., Plotkin, G.: Category-theoretical solution of recursive domain equations. SIAM Journ. Comput. 11, 761–783 (1982)

12. Taylor, P.: Towards a unified treatment of induction i: the general recursion theorem. preprint (1995-6), see http://www.paultaylor.eu/ordinals/#towuti

13. Trnková, V., Adámek, J., Koubek, V., Reiterman, J.: Free algebras, input processes and free monads. Comment. Math. Univ. Carolinae 16, 339–351 (1975)

14. Worrell, J.: On the final sequence of a finitary set functor. Theoret. Comput. Sci. 338 (2005)