For finite $k$, let $\mathscr{C}_k$ be the set of clones on a $k$-element set, viewed as a metric space by setting $d(A,B)=2^{-n}$ for distinct clones $A,B$ where $n$ is the smallest number such that the $n$-ary parts of $A$ and $B$ are different. Note that $\mathscr{C}_2$ is countable but $\mathscr{C}_k$ has cardinality continuum as soon as $k>2$; see here for an easy proof of the latter fact.
Question: Is there a continuous (or even Lipschitz) function $m:\mathscr{C}_4\rightarrow\mathscr{C}_3$ which is a lattice embedding, that is, satisfies $A\subseteq A'\iff m(A)\subseteq m(A')$?
EDIT: per Keith Kearnes' answer, this may be over-ambitious - it's not even clear whether there is a lattice embedding $\mathscr{C}_4\rightarrow\mathscr{C}_3$ at all.
There is certainly such a map in the other direction: given a clone $A$ on $\{1,2,3\}$, consider the new clone $B$ on $\{1,2,3,4\}$ whose $n$-ary functions are those $f$ satisfying $$f(x_1,...,x_n)=g(\min\{3,x_1\}, ...,\min\{3,x_n\})$$ for some $n$-ary $g\in B$. Basically, we just "treat $4$ as $3$." An $n$-ary difference between $A$ and $A'$ gets converted into an $n$-ary difference between the corresponding $B$ and $B'$, so this is in fact $1$-Lipschitz.
In some sense the question I really want to ask is whether the set of clones on $\{1,...,4\}$ is "structurally more complicated" than the set of clones on $\{1,...,3\}$; this is just one way of trying to make that question precise. Any comments addressing this vaguer question would also be welcome!
In some sense the question I really want to ask is whether the set of clones on $\{1,\ldots,4\}$ is "structurally more complicated" than the set of clones on $\{1,\ldots,3\}$; this is just one way of trying to make that question precise. Any comments addressing this vaguer question would also be welcome!
As suggested in the question, "structural complexity" can be measured by maps. One might say that $A$ and $B$ are equally complex from viewpoint $X$ if there are $X$-maps between them in both directions. If identity maps are $X$-maps and compositions of $X$-maps are $X$-maps, this can be reformulated equivalently as: is it true that, for every $C$, there is an $X$-map from $C$ into $A$ iff there is an $X$-map from $C$ into $B$? This suggest that one could study "similarity of complexity" by investigating which objects $C$ have $X$-maps into either $A$ or $B$.
Some work has been done on this, where $A={\mathscr C}_3$, $B={\mathscr C}_4$, and $X$-maps = lattice embeddings = meet and join preserving injections.
It is not hard to see that $A={\mathscr C}_3$ embeds into $B={\mathscr C}_4$, so any lattice $C$ that embeds into $A$ will also embed into $B$. I don't think anybody knows yet whether there is a lattice embedding of ${\mathscr C}_4$ into ${\mathscr C}_3$. It was shown in
Bulatov, A. A.
Finite sublattices in a lattice of clones.
Algebra and Logic 33, no. 5, 287-306 (1995)
that if $C$ is any countable direct product of finite lattices, then $C$ is embeddable into $B={\mathscr C}_4$, but it was posed as an open problem in this paper whether every such $C$ also embeds into $A={\mathscr C}_3$. If No, then this would provide a sense in which $B={\mathscr C}_4$ is more complex than $A={\mathscr C}_3$.
Let me mention another result which suggests the possibility that ${\mathscr C}_4$ is more complex than ${\mathscr C}_3$. Let $F_n$ be the free semigroup on $n$ generators. Let ${\mathscr L}_n$ be the dual of the lattice of subsemigroups of $F_n$. In
Bulatov, A. A.
Identities in lattices of closed classes.
Discrete Math. Appl. 3 (1993), no. 6, 601-609
it is shown that $C={\mathscr L}_n$ embeds in $B={\mathscr C}_4$ for every $n\geq 1$. It is also shown that $C={\mathscr L}_n$ is embeddable in $A={\mathscr C}_3$ for $\mathbf{n=1}$, but it is not known whether $C={\mathscr L}_n$ is embeddable in $A={\mathscr C}_3$ for any $n>1$. If, for example, ${\mathscr L}_2$ does not embed in $A={\mathscr C}_3$, then this would provide a sense in which $B={\mathscr C}_4$ is more complex than $A={\mathscr C}_3$.