Relative completeness with respect to transpositions


Jovanka Pantović, Ratko Tošić, Ratko Vojvodić




One of the most important results in the theory of clones of operations is the fact that the number of clones is a continuum for $\geq3$, while the corresponding set for $k=2$ is countable. This shows a sharp difference when we go from the binary to the ternary case. This paper discusses the relative completeness with respect to the clone generated by two unary functions and show the sharp difference when we go from the four-valued logic to $k$-valued logic for $k>4$, as well. The number of maximal clones over a finite set is finite and increases with increase in $k$. However, there are two relative maximal clones if $k=3,4$ and there is one relative maximal clone if $k>4$.