A Coalgebraic View of Infinite Trees and Iteration
Peter Aczel, Jiřı́ Adámek, Jiřı́ Velebil · Electronic Notes in Theoretical Computer Science · 2001
The algebra of infinite trees is, as proved by C. Elgot, completely iterative, i.e., all ideal recursive equations are uniquely solvable. This is proved here to be a general coalgebraic phenomenon: let H be an endofunctor such that for every object X a final coalgebra, TX, of H(_) + X exists. Then TX is an object-part of a monad which is completely iterative. Moreover, a similar contruction of a “completely iterative monoid” is possible in every monoidal category satisfying mild side conditions.