On the reconstruction of the action of a clone from its algebraic structure

Yonah Maissel and Matatyahu Rubin Ben Gurion University, Beer Sheva, Israel Ralph McKenzie proved that if $G$ is a group of permutations of a set $A$ with cardinality different from 6 and 1, then the action of $G$ on $A$ can be recovered from the group $G$ using first order formulas. The analogous problems for semigroups of functions from a set $A$ to itself and for clones on $A$ have not been considered (so it seems). I shall present four analogues of McKenzie’s theorem. Here is one of them. Theorem 1: Let $A$ be a set whose cardinality is different from 6 and 1, and let $S$ be a semigroup of functions from $A$ to $A$ containing all transpositions of $A$. Then the action of $S$ on $A$ can be recovered from the algebraic structure of the semigroup $S$ using first order formulas. A function $f$ from $A$ to $A$ is called a semi-transposition, if there are distinct $a,b \in A$ such that $f(a) = b$, and for every $c \in A$: if $c \neq a$, then $f(c) = c$. Theorem 2: Let $A$ be a set whose cardinality different from 1, and let $S$ be a semigroup of functions from $A$ to $A$ containing all semi-transpositions of $A$. Then the action of $S$ on $A$ can be recovered from the algebraic structure of the semigroup $S$ using first order formulas. Theorem 3: The analogues of Theorems 1 and 2 for clones are also true. I shall present several open questions both for semigroups of functions and for clones.