Erkko Lehtonen

Subfunctions and Burle's clones

We consider operations on a fixed base set $A$. Let $\mathcal{C}$ be a class of operations on $A$. We say that $f$ is a $\mathcal{C}$-subfunction of $g$, if $f = g(h_1, \ldots, h_n)$ for some $h_1, \ldots, h_n \in \mathcal{C}$. The $\mathcal{C}$-subfunction relation is a preorder on the set of all operations on $A$ if and only if $\mathcal{C}$ is a clone.

In this presentation, we focus on those subfunction relations which are defined by the clones containing all unary operations on a finite base set. As shown by Burle, there are $k+1$ such clones on a $k$-element base set $A$ and they constitute a chain in the lattice of clones on $A$. We investigate certain order-theoretical properties of these subfunction relations.