Can a clone be defined as a structure in a first order theory?

Question

Can a clone be defined as a structure in a first order theory?

Clones are described in A Short Introduction to Clones by Kerkhoff, Pöschel, and Schneider.

I think they're collections of graphs of functions that are closed under composition. Importantly, in an algebraic theory with $+$ and $*$ for example, the exact way that a function was obtained is ignored (such as the usage of $+$ and $*$ $\lambda a,b,c \mathop. (a*a+b+c)$ where $\lambda$ creates an anonymous function).

A structure in model theory also hides details about the elements of its domain, and relabelling the elements of the domain will always preserve whether a sentence holds at a particular structure.

I'm curious whether this construction works as an alternative definition/characterization of what a clone is.

I wrote this question before reading the paper the whole way through, but I'm also curious if this is just a rehashing of what a model of a Lawvere theory is, as described in section 5 (with a possibly-unnecessary notion of argument rotation). Based on reading the paper, I'm not sure what the equivalent of the thing I'm calling extensionality is in the Lawvere theory setting.

---

Let $\mathcal{S}$ be a set of sorts $\{D, S^1, S^2, \cdots\}$. Sorts are not guaranteed to be inhabited.

Let $\alpha : S^n \times D \cdots D \to D$ be function application.

Let $\alpha(f, \vec{x})$ be abbreviated as $f[\vec{x}]$.

We have an extensionality-like axiom.

$$ \forall f : S^n \mathop. \forall g :S^n \mathop. \forall x_1\cdots x_n \mathop. f[\vec{x}] = g[\vec{x}] \;\; \text{for each $n$ in $\mathbb{Z}_{\ge 1}$} $$

We have closure under argument rotation.

$$ \forall f :S^n \mathop. \exists g:S^n \mathop. f[x_1, x_2, \cdots x_n] = g[x_2, \cdots x_n, x_1] \;\; \text{for each $n$ in $\mathbb{Z}_{\ge 1}$} $$

We also have closure under composition in the first position.

$$ \forall f: S^a \mathop. g: S^b \mathop. \exists h:S^{-1+a+b} \mathop. \forall x_1 \cdots x_{-1+a+b} \mathop. \\ g[f[x_1 \cdots x_a], x_{-1 + a + 2}, x_{-1 +a + 3} \cdots x_{-1+a+b}] = h[x_1, \cdots x_{-1 + a + b}] \\ \text{for each $a$ and $b$ in $\mathbb{Z}_{\ge 1}$} $$

And we have a final axiom for the presence of projections.

$$ \exists f : S^n \mathop. \forall x_1 \cdots x_n \mathop. f(x_1\cdots x_n) = x_a \\ \text{for each $n$ in $\mathbb{Z}_{\ge 1}$ and each $a$ in $\{1, 2, \cdots, n\}$} $$

The cardinality of the domain of underlying algebra $\mathcal{A}$ is immediately recoverable as the size of $D$ (and is preserved by model isomorphism), but this is true anyway for a non-empty clone. Since clones are composed exclusively of graphs of total functions, given an element $f$ of a clone $c$, $|f|^{1/(-1+n)}$ where $n$ is the arity of $f$ as a relation will give us back the size of the domain.

We can build up any term function using argument rotation and composition, and extensionality guarantees us that we won't get spuriously nonequal function graphs by, for example, redundantly applying $n$ rotations in a row to an $n$-ary function.

(It also seems to me that if we Skolemize the above theory and introduce explicit functions for compositions and rotations, as well as explicit projections, the notion of model isomorphism also lines up with what we want.)

Answer 1

Your/my construction does not work. In a clone generated by $+$, the graph of the function $\lambda x \mathop. x+x$ will not be included.

The Wikipedia article on clones has a clear statement of what closure under composition means.

$C$ is closed under (finitary multiple) composition or superposition. If $f, g_1, \cdots, g_m$ are members of $C$ such that $f$ is $m$-ary, and $g_j$ is $n$-ary for all $j$, then the $n$-ary operation $h(x_1, \cdots, x_n) := f(g_1(x_1, \cdots x_n), \cdots, g_m(x_1, \cdots, x_n)) $ is in $C$.

In order to fix this, you need to replace the axiom for composition to be the following or similar.

$$ \forall f: S^a \mathop. \forall g_1 \cdots g_a : S^b \mathop. \exists h : S^a \mathop. \forall \vec{x} \mathop. f[g_1[\vec{x}] \cdots g_a[\vec{x}]] = h[\vec{x}] $$

Given this, permuting arguments is not necessary. A permutation can be built if desired by superposition of projections.

With that issue resolved, this does represent a concrete clone (you are just replacing the graph of each function with an opaque domain element in a 1:1 way).

It does not however represent an abstract clone because you are forcing the size of the domain of the algebra to be recoverable. This construction can also distinguish, say, $\pi_{(1, 2)}$ from other functions of arity $2$ in the clone, which cannot be done in an abstract clone.