Infinite trees and completely iterative theories: a coalgebraic view

✍ Scribed by Peter Aczel; Jiřı́ Adámek; Stefan Milius; Jiřı́ Velebil

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 533 KB
• Volume: 300
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00728-4

✦ Synopsis

Inÿnite trees form a free completely iterative theory over any given signature-this fact, proved by Elgot, Bloom and Tindell, turns out to be a special case of a much more general categorical result exhibited in the present paper. We prove that whenever an endofunctor H of a category has ÿnal coalgebras for all functors H ( ) + X , then those coalgebras, TX , form a monad. This monad is completely iterative, i.e., every guarded system of recursive equations has a unique solution. And it is a free completely iterative monad on H . The special case of polynomial endofunctors of the category Set is the above mentioned theory, or monad, of inÿnite trees.

This procedure can be generalized to monoidal categories satisfying a mild side condition: if, for an object H , the endofunctor H ⊗ + I has a ÿnal coalgebra, T , then T is a monoid. This specializes to the above case for the monoidal category of all endofunctors.