RECURSIVE DATA-TYPES IN ALGEBRAICALLY OMEGA-COMPLETE CATEGORIES

A category ($) under bar K (of data types) is called algebraically ome ga-complete provided that for each endofunctor T the data-type equatio n T(X) congruent to X has a solution constructed as a colimit of the o mega-chain perpendicular to --> T(perpendicular to) --> T-2(perpendicu lar to)..., where perpendicular to is the initial data-type. Examples include the categories of (1) countable sets and (total, partial, or n ondeterministic) functions, (2) countably dimensional vector spaces an d linear functions, (3) countable well-ordered sets and join-preservin g functions. In the case of categories enriched over CPO (the category of complete partial orders and strict, continuous functions) a strong er property holds for all locally continuous functors T:the data-type equation is both a limit and a colimit of the finite iterations of T o ver the initial data-type. (C) 1995 Academic Press, Inc.