Erkko Lehtonen (Khalifa University), On clonoids of Boolean functions

Tue, 17 Oct 2023, 1:25 pm MDT

Let $C_1$ and $C_2$ be clones on sets $A$ and $B$, respectively. A set $K$ of functions of several arguments from $A$ to $B$ is called a $(C_1,C_2)$-clonoid if $K C_1 \subseteq K$ and $C_2 K \subseteq K$. Sparks classified the clones $C$ on $\{0,1\}$ according to the cardinality of the lattice $\mathcal{L}_{(\mathsf{J}_A, C)}$ of $(\mathsf{J}_A, C)$-clonoids (here $\mathsf{J}_A$ denotes the clone of projections on a finite set $A$): $\mathcal{L}_{(\mathsf{J}_A, C)}$ is finite if and only if $C$ contains a near-unanimity operation; $\mathcal{L}_{(\mathsf{J}_A, C)}$ is countably infinite if and only if $C$ contains a Mal'cev operation but no majority operation; $\mathcal{L}_{(\mathsf{J}_A, C)}$ has the cardinality of the continuum if and only if $C$ contains neither a near-unanimity operation nor a Mal'cev operation. We sharpen Sparks's result by completely describing the lattices $\mathcal{L}_{(\mathsf{J}_A, C)}$ and the $(\mathsf{J}_A, C)$-clonoids when $A = \{0,1\}$ and $C$ contains a near-unanimity operation or a Mal'cev operation, i.e., when $\mathcal{L}_{(\mathsf{J}_A, C)}$ is finite or countably infinite.

[video]