Recursive Data Types in Algebraically ω-Complete Categories

A category K (of data types) is called algebraically ω-complete provided that for each endofunctor T the data-type equation T(X) ≅ X has a solution constructed as a colimit of the ω-chain ⊥ → T(⊥) → T 2(⊥). .. , where ⊥ is the initial data-type. Examples include the categories of (1) countable sets and (total, partial, or nondeterministic) functions, (2) countably dimensional vector spaces and linear functions, (3) countable well-ordered sets and join-preserving functions. In the case of categories enriched over CPO (the category of complete partial orders and strict, continuous functions) a stronger 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 over the initial data-type.

Authors

• J. Adamek

Keywords

No keywords are indexed for this paper.