Subject: categories: preprint: `Iteration Monads'

From: Jiri Velebil <[email-masked]>
Date: Mon, 27 Nov 2000 10:40:13 +0100 (MET)

The paper (for abstract, see below)

Aczel P., Adamek J., Velebil J.: Iteration Monads, preprint 

is now available from

http://math.feld.cvut.cz/velebil/

Jiri Velebil

----------------------------------------------------------------

Abstract:

It has already been noticed by C. Elgot and his
collaborators that the algebra of (finite and infinite)
trees is completely iterative, i.e., every system of
ideal recursive equations has a unique solution.
We prove that this is a special case of a very general
coalgebraic phenomenon: suppose that an endofunctor
H of an abstract category A is ``iterative'',
i.e., that it has the property that for every object
X in A a final coalgebra for H(_)+X
exists. Then these final coalgebras, TX, form a
monad on A, called the iteration monad of H.
And every ideal equation e : X --> T(X+Y) has 
a unique solution e^+: X --> TY.

We also present a more general view substituting
the category [A,A] of all endofunctors
of A by a monoidal category B: an  object H in B 
is called iterative if the endofunctor 
H tensor (_)+I  of B has a final coalgebra. This coalgebra 
is, then, a monoid in B, called the iteration monoid
of H. And the assignment of an iteration monoid
to all objects forms a monoid in [B,B].