Is there a clone on a three element set which is not finitely generated?

Question

Let 3 be the three element set $\{0,1,2\}$. Is there a clone (in the sense of universal algebra) on 3 which is not finitely generated? I know that every clone on a two element set is finitely generated, so what about a three element set? And if the answer is yes, can someone exhibit a clone on 3 which is not finitely generated, along with the proof that it is not?

Answer 1

Let $f_n\colon \mathbf{3}^n\to \mathbf{3}$ be the operation defined by $f_n(x_1,\ldots,x_n)=0$ whenever $(x_1,x_2,\ldots,x_n)\neq (2,2,\ldots,2)$ and $f_n(2,2,\ldots,2)=1$. The clone $\mathfrak{C}$ that is generated by $\{f_n\;|\; n\in \omega\}$ is not finitely generated.

Reason:
The operations $f_n$ are defined to have the properties that (i) $f_n(\mathbf{3},\ldots,\mathbf{3})\subseteq \{0,1\}$ and (ii) $f_n(\mathbf{3},\ldots,\mathbf{3},\{0,1\},\mathbf{3},\ldots,\mathbf{3})\subseteq \{0\}$. If you generate a clone on $\{0,1,2\}$ with these operations, all nonprojections in the clone will still have properties (i) and (ii).

The effect of this is that if you compose nonprojections of $\mathfrak{C}$, you almost always obtain an operation that is constant zero. Explicitly, if $g, h\in \mathfrak{C}$ are nonprojections, then

$g(x_{1},\ldots,x_{j-1},h(y_{1},\ldots,y_{m}),x_{j+1}\ldots,x_{n})=0$

for any $j, m, n$ and any substitution of values to the variables. From this we derive that the operations in $\mathfrak{C}$ are the projections, the constant zero operation of each arity ($0(x_1,\ldots,x_n) =0$) and the operations obtained from the generating operations by variable manipulation (from $f_n(x_1,\ldots,x_n)$, we can replace each variable $x_i$ with a variable $x_{i_j}$ to obtain $f_n(x_{j_1},\ldots,x_{j_n})$).

This is sufficient to imply that $\mathfrak{C}$ is not finitely generated. The subclone generated by any finite subset $\{g_1,\ldots,g_m\}\subseteq \mathfrak{C}$ will not contain any $f_n$ if $n$ is greater than the arity of each of the $g_i$'s.

Answer 2

Since comments are ephemeral, I'm making my footnote to Keith Kearnes' answer more permanent:

If we modify the answer above slightly, we get an even stronger phenomenon. Let $$j_n:{\bf 3}^n\rightarrow{\bf 3}: (x_1,...,x_n)\mapsto\begin{cases} 1 & \mbox{ if }\vert\{i:x_i\not=2\}\vert\le 1,\\ 0 & \mbox{ otherwise.}\\ \end{cases}$$

Then it turns out that for any $n\not\in X\subseteq\mathbb{N}$, $j_n$ is not in the clone generated by $\{j_m:m\in X\}$. This isn't true of the $f_n$s above, since we can define e.g. $f_2$ in terms of $f_5$: $$f_2(x,y)=f_5(x,x,x,x,y).$$ Besides proving that the clone generated by the $j_n$s is not finitely generated, this also gives a proof that there are continuum-many clones on a three-element set. (Of course this is well-known, but it seems weirdly hard to find a proof online.)

---

EDIT: Note that each of the size-continuum family of clones constructed above is missing lots of of constant functions. A natural question is whether there are continuum-many clones on a three-element set each of which contains every constant function. This question was posed by McKenzie, and answered affirmatively by Agoston/Demetrovics/Hannack. Generally, my understanding is that the lattice of clones on a three-element set is generally considered too complicated to describe fully, with most clone properties that don't obviously force countability occurring continuum often, but somewhat contra that theme see Csakany.