Uniform functors on sets

Lawrence S. Moss

pp. 420-448

in: Kokichi Futatsugi, Jean-Pierre Jouannaud, José Meseguer (eds), Algebra, meaning, and computation, Berlin, Springer, 2006

Abstrakt

This paper studies uniformity conditions for endofunctors on sets following Aczel [1], Turi [21], and others. The "usual" functors on sets are uniform in our sense, and assuming the Anti-Foundation Axiom AFA, a uniform functor H has the property that its greatest fixed point H ^* is a final coalgebra whose structure is the identity map. We propose a notion of uniformity whose definition involves notions from recent work in coalgebraic recursion theory: completely iterative monads and completely iterative algebras (cias). Among our new results is one which states that for a uniform H, the entire set-theoretic universe V is a cia: the structure is the inclusion of HV into the universe V itself.