From Iterative Algebras to Iterative Theories

Abstract. Iterative theories introduced by Calvin Elgot formalize potentially infinite computations as unique solutions of recursive equations. One of the main results of Elgot and his coauthors is a description of a free iterative theory as the theory of all rational trees. Their algebraic proof of this fact is extremely complicated. In our paper we show that by starting with “iterative algebras”, i. e., algebras admitting a unique solution of all systems of flat recursive equations, a free iterative theory is obtained as the theory of free iterative algebras. The (coalgebraic) proof we present is dramatically simpler than the original algebraic one. And our result is, nevertheless, much more general: we describe a free iterative theory on any finitary endofunctor of every locally presentable category. This allows us, e. g., to consider iterative algebras over every equationally specified class of finitary algebras. Reportedly, a blow from the welterweight boxer Norman Selby, also known as Kid McCoy, left one victim proclaiming, “It’s the real McCoy!