nLab Adámek's fixed point theorem

Context

Algebra

Induction

Contents

Idea

Adámek’s fixed point theorem gives a method to construct an initial algebra of an endofunctor by “iterating” the functor. The fact that this gives a “fixed point” of the endofunctor is given by Lambek's theorem.

Construction

This theorem is attributed to Jiří Adámek but note that the same construction for set-functors already appeared in (Pohlova,1973)).

Theorem (Adámek)

Let CC be a category with an initial object 00 and transfinite composition of length ω\omega, hence colimits of sequences ωC\omega \to C (where ω\omega is the first infinite ordinal), and suppose F:CCF: C \to C preserves colimits of Cω\omega-chains. Then the colimit γ\gamma of the chain

0iF(0)F(i)F (n)(0)F (n)(i)F (n+1)(0)0 \overset{i}{\to} F(0) \overset{F(i)}{\to} \ldots \to F^{(n)}(0) \overset{F^{(n)}(i)}{\to} F^{(n+1)}(0) \to \ldots

carries a structure of initial FF-algebra.

Proof

The FF-algebra structure FγγF\gamma \to \gamma is inverse to the canonical map γFγ\gamma \to F\gamma out of the colimit (which is invertible by the hypothesis on FF). The proof of initiality may be extracted by dualizing the corresponding proof given at terminal coalgebra.

This approach can be generalized to the transfinite construction of free algebras.

References

  • Věra Pohlová. “On sums in generalized algebraic categories.” Czechoslovak Mathematical Journal 23.2 (1973) 235-251 [eudml:12718]

  • Jiří Adámek, Free algebras and automata realizations in the language of categories, Commentationes Mathematicae Universitatis Carolinae 15.4 (1974) 589-602 [eudml:16649]

  • Jiří Adámek, Věra Trnková, Automata and algebras in categories 37 Springer (1990) [ISBN:9780792300106]

Last revised on October 3, 2024 at 17:55:10. See the history of this page for a list of all contributions to it.