Monoidal intervals in the clone lattice
by
Michael Pinsker
TU Wien

Let X be a set. A clone on X is a set of finitary functions which is closed under composition and which contains all projections. This is a generalization of a monoid, a set of unary functions closed under composition and containing the identity function. The set of all clones on X forms a complete algebraic lattice with respect to inclusion. The generalization of a monoid to a clone can be retraced in the clone lattice: For any monoid M of unary functions on X, the set of all clones having M as their unary part form a so-called monoidal interval in the clone lattice. If X is finite, then monoidal intervals of various finite sizes, countably infinite intervals, and intervals of size continuum are known. Moreover, no sizes between countable and continuum can appear. We treat the case of a countably infinite base set X, presenting many huge (as large as the clone lattice) intervals, an interval of size continuum, a countable one, and for each finite n an interval of size n.

Date received: May 21, 2004