Clones of inductive superpositions of terms

1.   Introduction

One of the fundamental concepts in universal algebra is the concept of terms. Terms can be initially constructed from the simplest forms called variables. They are elements from the finite set $X_n = \{x_1, \ldots, x_n\}$ or the countably infinite set $X = \{x_1, x_2, x_3, \ldots\}$. Then variables may be optionally combined with non-nullary operation symbols from the set $\{f_i\mid i\in I\}$ for a fixed index set $I$ to form new terms. This approach of operation-symbol combination can literally take on any already constructed terms, not just variables. The sequence $\tau = (n_i)_{i\in I}$ of arities of operation symbols is called the {type}. The formal definition of the $n$-ary terms of type $\tau$ is as follows:

$({\rm{i}})$ Every element of $X_n = \{x_1, \ldots, x_n\}$ is an $n$-ary term.

$({\rm{ii}})$ If $t_1, \ldots, t_{n_i}$ are $n$-ary terms and $f_i$ is an $n_i$-ary operation symbol, then the composition $f_i(t_1, \ldots, t_{n_i})$ is an $n$-ary term.

By $W_\tau (X_n)$ and $W_\tau (X)$, we denote the set of all $n$-ary terms of type $\tau$ and the set of all terms of type $\tau$, respectively. Note that $W_\tau (X_n)\subseteq W_\tau (X_m)$ whenever $m\geq n$. The applications of terms can be found in both algebraic and theoretical ways. Algebraically, terms are formal languages whose pairs stand for properties of algebras. With the selected properties, one can generate a variety of algebras satisfying those properties. Theoretically, terms are broadly utilized in linguistics and computer science. For more details on the applications of terms, we refer to ^[1,7,8,12] for algebraic aspects and to ^[1,8,9] for theoretical aspects. Moreover, readers may look into ^{[4,10,11,13,17,18]} for recent trends of term studies.

Acting as a base set, the set of terms $W_\tau (X_n)$ or $W_\tau (X)$ induces algebras of terms with various forms of fundamental operations on the said set of terms, one of which is a superposition of terms. A superposition is an operation of terms acting as a variable replacement by other terms. There are many forms of superpositions of terms, each of which is defined on a different base set of terms. For terms which are generated from a finite set of variables $X_m$ and $X_n$, the superposition $S^n_m: W_{\tau} (X_n)\times (W_{\tau} (X_m))^n\rightarrow W_{\tau} (X_m)$ is inductively defined as follows: for each $t\in W_{\tau} (X_n)$ and $t_1, \ldots, t_n\in W_{\tau} (X_m)$,

$({\rm{i}})$ $S^n_m (t, t_1, \ldots, t_n) : = t_i$ if $t = x_i\in X_n$;

$({\rm{ii}})$ $S^n_m (t, t_1, \ldots, t_n) : = f_i (S^n_m (s_1, t_1, \ldots, t_n), \ldots, S^n_m (s_{n_i}, t_1, \ldots, t_n))$ if $t = f_i (s_1, \ldots, s_{n_i})$.

There are also other forms of superpositions such as $S^n_g$ defined on $W_\tau (X)$ (see ^[6]) and $S^n$, the particular case of $S^n_m$ where $n = m$, defined on $W_{\tau_n} (X_n)$ where $\tau_n$ is a sequence of arities containing only many $n$ (see ^[12]). Some superpositions are partial operations due to some restrictions of their corresponding base sets of terms such as those of linear terms, $k$-terms, fixed-variable, and fixed-length terms (see ^[3,13,17,18] for more information). Besides, the superpositions we discussed until now share one essential property called superassociative law (SASS):

where $m, n, p$ are positive integers, $y_1, \ldots, y_p, z_1, \ldots, z_n$ and $z$ are terms (of an appropriate arity), and $S^p_m, S^n_m,$ and $S^p_n$ are superpositions. Note that those partial superpositions only consider the superassociative law as a weak identity.

At the period of time superpositions of terms have been studied throughout, Shtrakov ^[16] defined an inductive composition which is an operation of terms performing similarly to a superposition but with more choices of subterms which also cover variables to be substituted. The set $sub(t)$ of subterms of $t\in W_\tau (X_n)$ is inductively defined as follows:

$({\rm{i}})$ $sub(t) : = t$ if $t\in X_n$;

$({\rm{ii}})$ $sub(t) : = \{t\} \cup sub(t_1) \cup \ldots \cup sub(t_{n_i})$ if $t = f_i (t_1, \ldots, t_{n_i})$.

For each $r, s, t\in W_\tau (X_n)$, the inductive composition $t(r\leftarrow s)$ gives out the term in $W_\tau (X_n)$ which is inductively defined (see e.g., ^[15,16]) by

$({\rm{i}})$ $t(r\leftarrow s) : = t$ if $r\not\in sub(t)$;

$({\rm{ii}})$ $t(r\leftarrow s) : = s$ if $t = r$;

$({\rm{iii}})$ $t(r\leftarrow s) : = f_i (t_1(r\leftarrow s), \ldots, t_{n_i} (r\leftarrow s))$ if $t = f_i (t_1, \ldots, t_{n_i})$, $r\in sub(t)$, and $t\neq r$.

Once superassociative operations are obtained, algebraic structures called clones can then be constructed. Clones are multi-based algebras which satisfy the superassociative law (SASS) and the following two identities:

$({\rm{C2}})$ $S^n_m (e_i, z_1, \ldots, z_n) \approx z_i$;

$({\rm{C3}})$ $S^n_n (z, e_1, \ldots, e_n) \approx z$.

Here, $m, n\in \mathbb{N}^+ : = \{1, 2, 3, \ldots\}; i\in \{1, \ldots, n\}$; $z, z_1, \ldots, z_n$ are terms; $e_1, \ldots, e_n$ are nullary operation symbols; $S^n_m$ and $S^n_n$ are operation symbols. The term clone of type $\tau$

is a basic example of clones.

There are other terminologies for single-based clone-like algebras of type $(n+1)$ and $(n+1, 0, \ldots, 0)$. The former type induces an algebra called a Menger algebra of rank $n$ which satisfies (SASS), and the latter one induces a unary Menger algebra of rank $n$, an algebra with $n$ nullary operations which satisfies all of (SASS), (C2), and (C3).

Clones, Menger algebras, and unary Menger algebras of terms have been investigated for a long time in many kinds of terms and superpositions such as full terms (see ^[5]), generalized superpositions (see ^[2]), linear terms (see ^[3]), fixed-variable terms (see ^[17]), $k$-terms (see ^[13]), and fixed-length terms (see ^[18]). More background on clones and Menger algebras can be found in ^[7,12,14].

One may notice that an inductive composition defined by Shtrakov in ^[16] provides one subterm replacement at a time while a superposition replaces many variables in a term at once. This is a motivation of this paper to define another operation which inherits the good traits from an inductive composition and a superposition; more precisely, the operation will deal with subterm replacement and replace many subterms at once. We study its properties as well as clones relating to it. The freeness property of such clones is examined.

2.   Inductive superpositions of terms

In this section, we give the definition of inductive superpositions induced from a fixed sequence of fixed terms of $W_\tau (X_n)$ and provide several properties of such superpositions to obtain clones or clone-like algebras concerning them.

Definition 2.1. Let $m, n\in \mathbb{N}^+$ where $m\geq n$ and $r_1, \ldots r_n\in W_{\tau} (X_n)$ be $n$-ary fixed terms of type $\tau$ such that $r_i\not\in sub(r_j)$ whenever $i\neq j$. A mapping

called an $(r_1, \ldots, r_n)$-inductive superposition is defined for any $t\in W_{\tau} (X_n)$ and $t_1, \ldots, t_n \in W_{\tau} (X_m)$ by

(i) $S^n_{(m; r_1, \ldots, r_n)} (t, t_1, \ldots, t_n) : = t$ if $sub(t)\cap \{r_1, \ldots, r_n\} = \emptyset$;

(ii) $S^n_{(m; r_1, \ldots, r_n)} (t, t_1, \ldots, t_n) : = t_i$ if $t = r_i\in \{r_1, \ldots, r_n\}$;

(iii) $S^n_{(m; r_1, \ldots, r_n)} (t, t_1, \ldots, t_n) : = f_i (S^n_{(m; r_1, \ldots, r_n)} (s_1, t_1, \ldots, t_n), \ldots, S^n_{(m; r_1, \ldots, r_n)} (s_{n_i}, t_1, \ldots, t_n))$

if $t = f_i (s_1, \ldots, s_{n_i})\not\in \{r_1, \ldots, r_n\}$ and $sub(t)\cap \{r_1, \ldots, r_n\}\neq \emptyset$.

Remark 2.1. From the above definition of inductive superpositions, we notice that:

(i) as an initial term, a variable $x\in X_n$ is always fallen into either (i) or (ii) since $sub(x) = \{x\}$;

(ii) the condition $r_i\not\in sub(r_j)$ whenever $i\neq j$ implies that all $r$'s are distinct.

For convenience, we denote by $R$ the sequence $(r_1, \ldots, r_n)$. So, we may write $S^n_{(m; R)}$ instead of $S^n_{(m; r_1, \ldots, r_n)}$. The following example shows a calculation of an inductive superposition.

Example 2.1. Let $t = f(f(x_1, f(x_2, x_3)), x_1), r_1 = f(x_1, f(x_2, x_3)), r_2 = f(x_3, x_1)$, and $r_3 = f(x_1, x_1)$, each of which is in $W_{(2)} (X_3)$ where $f$ is a binary operation symbol and let $R = (r_1, r_2, r_3)$. Then we have

The relation $m\geq n$ in the previous definition is crucial. Lack of such condition can lead to the following invalidation.

Example 2.2. Let $t = x_4\in W_{(2)} (X_4)$ while $r_1 = f(x_1, x_1), r_2 = f(x_2, x_2), r_3 = f(x_2, x_1)$, and $r_4 = f(x_1, x_2)$ belong to $W_{(2)} (X_2)$ with a binary operation symbol $f$. Setting $R = (r_1, r_2, r_3, r_4)$, we see that $n = 4$ and $m = 2$ which implies $m\ngeq n$. Then $S^n_{(m; R)} (t, r_1, r_2, r_3, r_4) = x_4 \not\in W_{(2)} (X_m)$ since $sub(t)\cap \{r_1, r_2, r_3, r_4\} = \emptyset$.

From this point on, we set $R$ to be a sequence of fixed terms, each of which is not a subterm of the others unless state otherwise. In this paper, we sometimes treat the sequence $R$ of fixed terms as if it is a set of terms so that we can apply set operations such as an intersection and a subtraction to $R$. For example, a sequence $R = (r_1, r_2, r_3)$ may be treated as the set $\{r_1, r_2, r_3\}$.

Moving to the special case of $S^n_{(m; R)}$ where $n = m$, we denote such superposition by $S^n_R$. Once we have a superposition, it is natural to ask for a corresponding clone. The superposition $S^n_R$ as well as the sequence of terms $R$ can be used to form an algebra $(W_\tau (X_n), S^n_R, R)$ on $W_\tau (X_n)$. Unfortunately, this algebra does not satisfy the superassociativity (SASS) in general. The following example illustrates this matter.

Example 2.3. Let $\tau = (2, 1)$ with a binary operation symbol $f$ and $g$ a unary one, and $R = (r_1, r_2, r_3)$ where $r_1 = g(x_1), r_2 = f(g(x_2), x_3), r_3 = f(x_2, x_3)$. Consider $W_\tau (X_3)$. We have

while

These show that $S^3_R$ does not satisfy the clone axiom (SASS) on $W_\tau (X_3)$.

As $(W_\tau (X_n), S^n_R, R)$ is not clone-like, our hope may bend to a base set restriction so that $S^n_R$ is superassociative on that restricted base set. For a sequence $R$ of fixed terms of $W_{\tau} (X_n)$, we denote $W_{\tau} ^R (X_n): = W_{\tau} (X_n)\setminus \bigcup_{r\in R} (sub(r)\setminus \{r\})$. This set seems to have our desired property. To prove the property, we need the following lemma.

Lemma 2.1. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_{\tau} (X_n)$ and $t, s_1, \ldots, s_n\in W_{\tau} (X_n)$. If $sub(t)\cap R = \{r_{n_1}, \ldots, r_{n_k}\}$ for some subsequence $(n_1, \ldots, n_k)$ of $(1, \ldots, n)$, then $sub(s_j)\subseteq sub(S^n_R (t, s_1, \ldots, s_n))$ for all $j\in \{n_1, \ldots, n_k\}$. The inclusion is proper if and only if $t\not\in R$.

Proof. Assume that $sub(t)\cap R = \{r_{n_1}, \ldots, r_{n_k}\}$. We prove by induction on the structure of $t$. If $t = r_l\in R$ for some $l\in \{1, \ldots, n\}$, then $sub(t)\cap R = \{r_l\}$ and $S^n_R (t, s_1, \ldots, s_n) = s_l$. Hence, $sub(s_l)\subseteq sub(S^n_R (t, s_1, \ldots, s_n))$. For $t = f_i (t_1, \ldots, t_{n_i})\not\in R$, we have that for each $j\in \{n_1, \ldots, n_k\}$, there is $t'_j\in \{t_1, \ldots, t_{n_i}\}$ such that $r_j\in sub(t'_j)$. Assume inductively that $sub(s_j)\subseteq sub(S^n_R (t'_j, s_1, \ldots, s_n))$ for each $j\in \{n_1, \ldots, n_k\}$. As $S^n_R (t, s_1, \ldots, s_n) = f_i (S^n_R (t_1, s_1, \ldots, s_n), \ldots, S^n_R (t_{n_i}, s_1, \ldots, s_n))$, we see that $sub(S^n_R (t, s_1, \ldots, s_n)) = \{S^n_R (t, s_1, \ldots, s_n)\} \cup \bigcup_{m = 1} ^{n_i} sub(S^n_R (t_m, s_1, \ldots, s_n))$. It follows that

The proof is then complete.

The essential properties of $W^R _{\tau} (X_n)$ are described in the next lemma.

Lemma 2.2. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_{\tau} (X_n)$ and $t, s_1, \ldots, s_n\in W^R_{\tau} (X_n)$. Then

(i) $S^n_R (t, s_1, \ldots, s_n)\in W^R_{\tau} (X_n)$;

(ii) $S^n_R (t, s_1, \ldots, s_n)\not\in R$ whenever $t\not\in R$;

(iii) $S^n_R (t, s_1, \ldots, s_n) = r_j$ if and only if $t = r_k$ and $s_k = r_j$ for some $j, k\in \{1, \ldots n\}$.

Proof. (ⅰ) If $sub(t)\cap R = \emptyset$, then $S^n_R (t, s_1, \ldots, s_n) = t\in W^R_{\tau} (X_n)$. If $t = r_i\in R$ for some $i\in \{1, \ldots, n\}$, then $S^n_R (t, s_1, \ldots, s_n) = s_i\in W^R_{\tau} (X_n)$. For $t = f_i (t_1, \ldots, t_{n_i})\not\in R$, $sub(t)\cap R\neq \emptyset$, suppose that $S^n_R (t, s_1, \ldots, s_n)\not\in W^R_{\tau} (X_n)$ Let $r_k\in sub(t)$ for some $r_k\in R$. Since $S^n_R (t, s_1, \ldots, s_n)\not\in W^R_{\tau} (X_n)$, we have that $S^n_R (t, s_1, \ldots, s_n)\in \bigcup_{r\in R} (sub(r)\setminus \{r\})$, i.e., $S^n_R (t, s_1, \ldots, s_n)\in sub(r)\setminus \{r\}$ for some $r\in R$. By Lemma 2.1, there follows $s_k\in sub(s_k)\subsetneq sub(S^n_R (t, s_1, \ldots, s_n))\subseteq sub(r)\setminus \{r\}$ which is a contradiction to $s_k\in W^R_{\tau} (X_n)$. Therefore, $S^n_R (t, s_1, \ldots, s_n)\in W^R_{\tau} (X_n)$.

(ⅱ) Assume that $t\not\in R$. If $sub(t)\cap R = \emptyset$, then $S^n_R (t, s_1, \ldots, s_n) = t\not\in R$. For $t = f_i (t_1, \ldots, t_{n_i})\not\in R$, and $sub(t)\cap R\neq \emptyset$, we suppose that $S^n_R (t, s_1, \ldots, s_n)\in R$. Let $sub(t)\cap R = \{r_{n_1}, \ldots, r_{n_k}\}$. By Lemma 2.1, we have that $sub(s_j)\subsetneq sub(S^n_R (t, s_1, \ldots, s_n))$ for each $j\in \{n_1, \ldots, n_k\}$. This means that $s_j$ is a proper subterm of a term in $R$ which contradicts $s_j\in W^R_{\tau} (X_n)$. Therefore, $S^n_R (t, s_1, \ldots, s_n)\not\in R$.

(ⅲ) Assume that $S^n_R (t, s_1, \ldots, s_n) = r_j$ for some $j\in \{1, \ldots n\}$. By (ii), $t\in R$. Then $t = r_k$ for some $k\in \{1, \ldots n\}$. Hence, $r_j = S^n_R (t, s_1, \ldots, s_n) = S^n_R (r_k, s_1, \ldots, s_n) = s_k$. The converse is obvious.

Apparently, the converse of Lemma 2.2(ⅱ) does not hold. Moreover, the base set $W^R_{\tau} (X_n)$ has the following property.

Lemma 2.3. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_\tau (X_n)$ and $t, s_1, \ldots, s_n\in W^r_\tau (X_n)$ such that $sub(t)\cap R = \{r_{n_1}, \ldots, r_{n_k}\}$. The following two conditions are equivalent:

(i) $sub(S^n_R (t, s_1, \ldots, s_n))\cap R = \emptyset$;

(ii) $sub(s_j)\cap R = \emptyset$ for all $j\in \{n_1, \ldots, n_k\}$.

Proof. If $t = r_j$ for some $j\in \{1, \ldots, n\}$, then $sub(t)\cap R = \{r_j\}$ and $S^n_R (t, s_1, \ldots, s_n) = s_j$. It follows that $sub(S^n_R (t, s_1, \ldots, s_n))\cap R = \emptyset$ if and only if $sub(s_j)\cap R = \emptyset$. Next, we consider the case $t = f_i (t_1, \ldots, t_{n_i})\not\in R$ and $sub(t)\cap R\neq \emptyset$. By Lemma 2.2 (ⅱ), we have that $S^n_R (t, s_1, \ldots, s_n)\not\in R$. To prove one direction, we assume that $sub(S^n_R (t, s_1, \ldots, s_n))\cap R = \emptyset$. By Lemma 2.1, we have that $sub(s_j)\subseteq sub(S^n_R (t, s_1, \ldots, s_n))$ for each $j\in \{n_1, \ldots, n_k\}$, and hence for each $j\in \{n_1, \ldots, n_k\}$, $sub(s_j)\cap R\subseteq sub(S^n_R (t, s_1, \ldots, s_n))\cap R = \emptyset$. Therefore, $sub(s_j)\cap R = \emptyset$. On the other hand, assume that $sub(s_j)\cap R = \emptyset$ for all $j\in \{n_1, \ldots, n_k\}$. Since $S^n_R (t, s_1, \ldots, s_n) = f_i (S^n_R (t_1, s_1, \ldots, s_n), \ldots, S^n_R (t_{n_i}, s_1, \ldots, s_n))$, it follows that $sub(S^n_R (t, s_1, \ldots, s_n)) = \{S^n_R (t, s_1, \ldots, s_n)\}\cup \bigcup_{l = 1}^{n_i} sub(S^n_R (t_l, s_1, \ldots, s_n))$. Let $l\in \{1, \ldots, n_i\}$. If $t_l\in \bigcup_{r\in R}$ $(sub(r)\setminus \{r\})$, then $S^n_R (t_l, s_1, \ldots, s_n) = t_l$. Thus, $sub(S^n_R (t_l, s_1, \ldots, s_n))\cap R = sub(t_l)\cap R = \emptyset$. If $t_l = r_{l'}\in R$, then $S^n_R (t_l, s_1, \ldots, s_n) = s_{l'}$. Since $r_{l'} = t_l\in sub(t)$, we get $r_{l'}\in sub(t)\cap R$. The assumption then gives $sub(S^n_R (t_{l}, s_1, \ldots, s_n))\cap R = sub(s_{l'})\cap R = \emptyset$. If $t_l\in W^R_\tau (X_n)\setminus R$, then Lemma 2.2(ⅱ) yields $S^n_R (t_l, s_1, \ldots, s_n)\not\in R$. Then we consider in two cases. The first one is $sub(t_l)\cap R = \emptyset$. This implies that $sub(S^n_R (t_l, s_1, \ldots, s_n))\cap R = sub(t_l)\cap R = \emptyset$. Another one goes to $sub(t_l)\cap R\neq\emptyset$. It follows that $\emptyset\neq sub(t_l)\cap R\subseteq sub(t)\cap R = \{r_{n_1}, \ldots, r_{n_k}\}$. For a term $u\in W^R_\tau (X_n)$, let $I_{u} = \{m\in \{1, \ldots, n\}\mid r_m\in sub(u)\cap R\}$. Then $I_{t_l}\subseteq I_t$. The assumption $sub(s_j)\cap R = \emptyset$ for all $j\in \{n_1, \ldots, n_k\} = I_t$ also provides that $sub(s_j)\cap R = \emptyset$ for all $j\in I_{t_l}$. Using induction hypothesis, we obtain $sub(S^n_R (t_l, s_1, \ldots, s_n))\cap R = \emptyset$. Altogether, we finally obtain

The proof is eventually finished.

The next lemma emphasizes that an initial term $t\in W^R_\tau (X_n)$ will only be dominated by some certain terms of an inductive superposition.

Lemma 2.4. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_\tau (X_n)$, $t, s_1, \ldots, s_n\in W^R_\tau (X_n)$ and $sub(t)\cap R = \{r_{n_1}, \ldots, r_{n_k}\}$. Then

for any $u_1, \ldots, u_{n_1-1}, u_{n_1+1}, \ldots, u_{n_k-1}, u_{n_k+1}, \ldots, u_n\in W^R_\tau (X_n)$.

Proof. We prove by induction on the structure of $t$. If $t = r_j\in R$, then $sub(t)\cap R = \{r_j\}$ and $S^n_R (t, s_1, \ldots, s_n) = s_j = S^n_R (t, u_1, \ldots, u_{j-1}, s_j, u_{j+1}, \ldots, u_n)$ for any $u_1, \ldots, u_{j-1}, u_{j+1}, \ldots, u_n\in W^R_\tau (X_n)$. For $t = f_i (t_1, \ldots, t_{n_i})\not\in R$, we have that $sub(t_j)\cap R\subseteq sub(t)\cap R = \{r_{n_1}, \ldots, r_{n_k}\}$ for each $j\in \{1, \ldots, n_i\}$. Let $L$ be the largest subset of $\{t_1, \ldots, t_{n_i}\}$ such that $sub(t_l)\cap R\neq \emptyset$ for all $t_l\in L$. Since $t\not\in R$ and $sub(t)\cap R\neq \emptyset$, $L\neq \emptyset$. For each $t_l\in L$, suppose that $sub(t_l)\cap R = \{r_{l_1}, \ldots, r_{l_{k_l}}\}\subseteq \{r_{n_1}, \ldots, r_{n_k}\}$. Inductively, we assume that for each $t_l\in L$, $S^n_R (t_l, s_1, \ldots, s_n) = S^n_R (t_l, u_1, \ldots, u_{l_1-1}, s_{l_1}, u_{l_1+1}, \ldots, u_{l_{k_l}-1}, s_{l_{k_l}}, u_{l_{k_l}+1}, \ldots, u_n)$ for any $u_1, \ldots, u_{l_1-1}, u_{l_1+1}, \ldots, u_{l_{k_l}-1}, u_{l_{k_l}+1}, \ldots, u_n\in W^R_\tau (X_n)$. We can set each $u_a$ where $a\in \{n_1, \ldots, n_k\} \setminus \{l_1, \ldots, l_{k_l}\}$ to be $s_a$. In other words, for each $t_l\in L$, we have

Moreover, for each $v\in \{t_1, \ldots, t_{n_i}\}\setminus L$, $sub(v)\cap R = \emptyset$ and thus

Therefore,

The proof is then complete.

The superposition $S^n_R$ as well as the sequence $R$ of fixed terms in $W_\tau (X_n)$ can be used to form an algebra on $W^R_\tau (X_n)$, namely, $n$-ary $R$-inductive clone of type $\tau$ denoted by $n\mbox{-clone}_R \tau$. This algebra is defined by

This algebra turns out to be a unitary Menger algebra of rank $n$, an algebra of type $(n+1, 0, \ldots, 0)$ with $n$ nullary operations which satisfies the three clone axioms: (SASS), (C2) and (C3).

Theorem 2.1. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_\tau (X_n)$. The $n\mathit{\mbox{-clone}}_R \tau$ satisfies the three clone axioms: $(SASS), (C2)$ and $(C3)$.

Proof. First, we prove (SASS) by induction on the structure of the initial term. Let $t, s_1, \ldots, s_n, u_1, \ldots, u_n\in W^R_\tau (X_n)$. If $sub(t)\cap R = \emptyset$, then

If $t = r_j$ for some $j\in \{1, \ldots, n\}$, then

For $t = f_i (t_1, \ldots, t_{n_i})\not\in R$ and $sub(t)\cap R\neq \emptyset$, we inductively assume that

for each $k\in \{1, \ldots, n_i\}$. Let $sub(t)\cap R = \{r_{n_1}, \ldots, r_{n_k}\}$. The term $S^n_R (S^n_R (t, s_1, \ldots, s_n), u_1, \ldots, u_n)$ must be considered in 2 cases:

Case 1. $sub(S^n_R (t, s_1, \ldots, s_n))\cap R = \emptyset$.

By Lemma 2.3, we have that $sub(s_j)\cap R = \emptyset$ for each $j\in \{n_1, \ldots, n_k\}$. There follows $S^n_R (s_j, u_1, \ldots, u_n) = s_j$ for each $j\in \{n_1, \ldots, n_k\}$. Therefore,

The last equation concerning $s_l$ for each $l\in \{1, \ldots, n_i\}\setminus \{n_1, \ldots, n_k\}$ is valid due to Lemma 2.4.

Case 2. $sub(S^n_R (t, s_1, \ldots, s_n))\cap R\neq \emptyset$.

By Lemma 2.2(ⅱ), $S^n_R (t, s_1, \ldots, s_n)\not\in R$. As a consequence, we obtain

These ensure the (SASS) satisfaction of $n\mathit{\mbox{-clone}}_R \tau$. For (C2), it is directly obtained from the definition of $S^n_R$. To prove (C3), we can simply do so by induction on the structure of the initial term.

3.   Properties of the clone $n\mbox{-clone}_R \tau_n$

From the previous section, we have shown that $n\mbox{-clone}_R \tau$ is a clone (in fact, a unitary Menger algebra of rank $n$). It's natural to ask for a generating set of a clone which is very essential in studying the freeness property of that clone. In this section, we consider a clone $n\mbox{-clone}_R \tau_n = (W^R_{\tau_n} (X_n), S^n_R, R)$ of a specific type $\tau_n: = (n_i)_{i\in I}$ where $n_i = n$ for all $i\in I$. We define $sub(R): = \bigcup_{r\in R} sub(r)$ and $F^R_{\tau_n}: = \{f_i (u_1, \ldots, u_n)\mid i\in I \phantom{a} \text{and} \phantom{a} u_j\in \{r_j\}\cup (sub(R)\setminus R) \phantom{a} \text{for each} \phantom{a} 1\leq j\leq n\}$.

Lemma 3.1. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_{\tau_n} (X_n)$. Then $G^R_{\tau_n}: = (F^R_{\tau_n} \cup X_n)\cap (W^R_{\tau_n} (X_n)\setminus R)$ is a generating system of $n\mathit{\mbox{-clone}}_R \tau_n$.

Proof. We show by induction on the complexity of a term $t\in W^R_{\tau_n} (X_n)$ that $t$ can be generated from $G^R_{\tau_n}$. All elements in $R$ belong to the type of $n\mathit{\mbox{-clone}}_R \tau_n$ so they are generated. Next, consider $t\not\in R$. If $t\in X_n$, then $t\in G^R_{\tau_n}$ and so it is generated. For $t = f_i (t_1, \ldots, t_{n})$, it is obviously generated if it belongs to $G^R_{\tau_n}$, so we assume that $t\not\in G^R_{\tau_n}$. Then there is $k\in \{1, \ldots, n\}$ such that $t_k\not\in \{r_k\}\cup (sub(R)\setminus R)$. Let $K = \{k_1, \ldots, k_m\}\subseteq \{1, \ldots, n\}$ be the set of all indices such that $t_{k'}\not\in \{r_{k'}\}\cup (sub(R)\setminus R)$ for any $k'\in K$. This means that $t_{k_1}, \ldots, t_{k_m}\in W^R_{\tau_n} (X_n)$. Inductively assume that $t_{k_1}, \ldots, t_{k_m}$ are all generated. Note that for each $l\in \{1, \ldots, n\}\setminus K$, $t_l\in \{r_l\}\cup (sub(R)\setminus R)$, i.e., $t_l = r_l$ or $t_l\in sub(R)\setminus R$. The latter provides $S^n_R (t_l, s_1, \ldots, s_n) = t_l$ for any $s_1, \ldots, s_n\in W^R_{\tau_n} (X_n)$ while the former gives $S^n_R (t_l, s_1, \ldots, s_{l-1}, r_l, s_{l+1}, s_n) = S^n_R (t_l, r_1, \ldots, r_n) = t_l$ for any $s_1, \ldots, s_{l-1}, s_{l+1}, \ldots, s_n\in W^R_{\tau_n} (X_n)$ due to Lemma 2.4 and $(C3)$ satisfaction. Let $T = (r_1, \ldots, r_{k_1-1}, t_{k_1}, r_{k_1+1}, \ldots, r_{k_m-1}, t_{k_m}, r_{k_m+1}, \ldots, r_n)$ be a sequence. For a shorter expression, we denote $S^n_R (u, r_1, \ldots, r_{k_1-1}, t_{k_1}, r_{k_1+1}, \ldots, r_{k_m-1}, t_{k_m}, r_{k_m+1}, \ldots, r_n)$ by simply $S^n_R (u, T)$ for any $u\in W_{\tau_n} (X_n)$. Consequently,

Hence, $t$ is generated.

We remark from the previous lemma that when we consider $R = X_n$, the generating system $G^R_{\tau_n}$ of $n\mbox{-clone}_R \tau_n$ becomes $\{f_i (x_1, \ldots, x_n)\mid i\in I\}$ which coincides with the result discovered in ^[12].

Once we obtain a generator of a clone, the freeness property of that clone can then be examined. A clone is free with respect to itself if there is a generating system such that each mapping from this generating system to the corresponding clone can be extended to an endomorphism of that clone. Undoubtedly, if $R = X_n$, then the clone $n\mbox{-clone}_R \tau_n$ is actually $(W_{\tau_n} (X_n), S^n, x_1, \ldots, x_n)$ and from the results mentioned in ^[12], it is free with respect to itself. Unfortunately, not every setting of $R$ makes $n\mbox{-clone}_R \tau_n$ satisfy such freeness as shown in the following example.

Example 3.1. Let $n = 3$, $\tau_3 = (3, 3)$ with ternary operation symbols $f$ and $g$, $R = (f(x_1, x_1, x_1), f(x_2, x_2, x_2), f(x_1, x_2, x_1))$. Consider $x_3\in W^R _{\tau_3} (X_3)$. It is not difficult to see that $x_3$ cannot be generated unless it is in a generating system. Let $G$ be a generating system of this $3-clone_R \tau_3$ and $\varphi: G\rightarrow W^R _{\tau_3} (X_3)$ be a mapping with $\overline{\varphi}$ as its extension on $W^R _{\tau_3} (X_3)$ and $\varphi(x_3) = \overline{\varphi}(x_3) = f(x_1, x_1, x_1)$. If $G$ is a singleton set of $x_3$, then $\langle G\rangle_{3-clone_R \tau_3} = \{x_3, r_1, r_2, r_3\} \neq W^R _{\tau_3} (X_3)$, a contradiction. So, the cardinality of $G$ must be greater than $1$. We also have that for $s_1, s_2, s_3\in W^R _{\tau_3} (X_3)$,

while

This implies that $\overline{\varphi} (S^n_R (x_3, s_1, s_2, s_3)) = S^n_R (\overline{\varphi}(x_3), \overline{\varphi}(s_1), \overline{\varphi}(s_2), \overline{\varphi}(s_3))$ if and only if $\overline{\varphi}$ designates each term of $W^R_{\tau_3} (X_3)$ the term $f(x_1, x_1, x_1)$ in which case the mapping $\varphi$ is not independent due to the cardinality of $G$ being greater than $1$. Therefore, this $3-clone_R \tau_3$ is not free with respect to itself.

Our hope is bended to finding the condition of $R$ which makes $n\mbox{-clone}_R \tau_n$ satisfy freeness property. Referring to the above example, we see that if there is a variable in a generating system, a mapping from the generating system to $W^R_{\tau_n} (X_n)$ cannot be selected freely or else its extension will not satisfy homomorphism. This leads to the following lemma whose proof is similar to the reasoning from Example 3.1.

Lemma 3.2. If the clone $n\mathit{\mbox{-clone}}_R {\tau_n}$ is free with respect to itself, then $X_n\subseteq sub(R)$.

We have to find all possible minimal generators of the clone in order to investigate the incident where the clone is free with respect to itself. To do so, we first define the $R$-equivalence of terms: let $s, t\in W_{\tau} (X_n)$ be $n$-ary terms of type $\tau$ and $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_\tau (X_n)$. A term $t$ is said to be $R$-equivalent to $s$, in which case we denote by $t\sim_R s$, if $s$ can be obtained from $t$ by interchanging each $r\in sub(t)\cap R$ via a bijection $\alpha: sub(t)\cap R \rightarrow sub(s)\cap R$ whenever $sub(t)\cap R\neq \emptyset$, and $s = t$ otherwise.

Example 3.2. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_\tau (X_n)$ and $g(x_1)\not\in R$. Consider terms from $W_{(2, 1, 3)} (X_5)$ where $f, g$, and $h$ are binary, unary, and ternary operation symbols, respectively.

(1) $r_1\sim_R r_2$ with a bijection $\alpha: \{r_1\}\rightarrow \{r_2\}$ defined by $\alpha(r_1) = r_2$;

(2) $f(r_1, r_2)\sim_R f(r_2, r_1)$ via a bijection $\alpha: \{r_1, r_2\}\rightarrow \{r_2, r_1\}$ defined by $\alpha(r_1) = r_2$ and $\alpha(r_2) = r_1$;

(3) $h(r_1, g(x_1), r_3)\sim_R h(r_3, g(x_1), r_2)$ via a bijection $\alpha: \{r_1, r_3\}\rightarrow \{r_3, r_2\}$ defined by $\alpha(r_1) = r_3$ and $\alpha(r_3) = r_2$.

The following lemma characterizes $R$-equivalent terms in which at least one $r\in R$ is included.

Lemma 3.3. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_\tau (X_n)$ and $s, t\in W_{\tau} (X_n)$ such that $sub(t)\cap R\neq \emptyset$ and $t\sim_R s$ which relates to a bijection $\alpha: sub(t)\cap R \rightarrow sub(s)\cap R$.

(i) If $t\in R$, then $s\in R$. More precisely, $s = \alpha (t)\in R$.

(ii) If $t = f_i (t_1, \ldots, t_{n_i})\not\in R$ and $sub(t)\cap R\neq \emptyset$, then $s = f_i (s_1, \ldots, s_{n_i})$ and $t_j\sim_R s_j$ for all $j\in \{1, \ldots, n_i\}$ with the additional condition of the case $sub(t_j)\cap R\neq \emptyset$ that the bijection $\alpha_j: sub(t_j)\cap R \rightarrow sub(s_j)\cap R$ relating to the equivalence must be a restriction of $\alpha$.

Proof. (ⅰ) This is directly obtained from the definition of $\sim_R$.

(ⅱ) Assume that $t = f_i (t_1, \ldots, t_{n_i})\not\in R$ and $sub(t)\cap R\neq \emptyset$. Let $A = \{a\in \{1, \ldots, n_i\}\mid sub(t_a)\cap R\neq \emptyset \}$. Then $sub(t_{a'})\cap R = \emptyset$ for all $a'\in \{1, \ldots, n_i\}\setminus A$. Since $s$ can be obtained from $t$ by interchanging each $r\in sub(t)\cap R$, any operation symbol of $t$ which is not a subterm of any $r\in sub(t)\cap R$ stays unchanged and thus $s = f_i (s_1, \ldots, s_{n_i})$ for some $s_1, \ldots, s_{n_i}\in W_\tau (X_n)$. Again, by the definition of $\sim_R$, we obtain $t_{a'} = s_{a'}$ for all $a'\in \{1, \ldots, n_i\}\setminus A$ which also means that $t_{a'} \sim_R s_{a'}$. Consider each $t_a$ where $a\in A$. If there is $j\in A$ such that $t_j \not\sim_R s_j$, then $s_j$ cannot be obtained from $t_j$ by simply swapping each $r\in sub(t_j)\cap R$ through any bijection $\alpha_j: sub(t_j)\cap R \rightarrow sub(s_j)\cap R$. Acting as a subterm of $t$ and $s$, respectively, this unpleasant behavior of $t_j$ and $s_j$ leads to the same behavior for $t$ and $s$, contrary to $t\sim_R s$. Thus, $t_j \sim_R s_j$ for all $j\in A$. Altogether, we obtain $t_j \sim_R s_j$ for all $j\in \{1, \ldots, n_i\}$. Additionally, for each $t_a$ where $a\in A$, the index of satisfying $sub(t_a)\cap R\neq \emptyset$, we let $\alpha_a: sub(t_a)\cap R \rightarrow sub(s_a)\cap R$ be a bijection corresponding to $t_a\sim_R s_a$. It is crucial to note that $\vert sub(t_a)\cap R\vert = \vert sub(s_a)\cap R\vert$. Therefore, $\alpha\vert_{sub(t_a)\cap R}: sub(t_a)\cap R \rightarrow sub(s_a)\cap R$ is also a bijection. A simple calculation provides $\alpha_a = \alpha\vert_{sub(t_a)\cap R}$ because otherwise we would get different $s$. The proof is then complete.

A common question for any relation is to classify whether it is an equivalent relation or not. The $R$-equivalence, $\sim_R$, appears to be an equivalent one.

Lemma 3.4. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_\tau (X_n)$. Then $\sim_R$ is an equivalent relation on $W_\tau (X_n)$.

Proof. Let $s, t, u\in W_\tau (X_n)$. Reflexivity is obvious. To show symmetry, we assume that $t\sim_R s$. It is easy to see that $s\sim_R t$ when $sub(t)\cap R = \emptyset$. Additionally assume that $sub(t)\cap R\neq \emptyset$. Let $\alpha: sub(t)\cap R\rightarrow sub(s)\cap R$ be a bijection correponding to $t\sim_R s$. Note that $\alpha^{-1}: sub(s)\cap R\rightarrow sub(t)\cap R$ is also a bijection and hence $s\sim_R t$. To prove transitivity, we assume that $t\sim_R s$ and $s\sim_R u$. Then $t\sim_R u$ is directly obtained if one of $s, t$, or $u$ does not have any $r\in R$ as its subterms. Suppose more that $sub(t)\cap R$ and $sub(s)\cap R$ are nonempty. Let $\alpha: sub(t)\cap R\rightarrow sub(s)\cap R$ and $\beta: sub(s)\cap R\rightarrow sub(u)\cap R$ be bijections correponding to $t\sim_R s$ and $s\sim_R u$, respectively. Thus, the mapping $\beta\circ\alpha: sub(t)\cap R\rightarrow sub(u)\cap R$ is bijective. Therefore, $t\sim_R u$. Consequently, $\sim_R$ is an equivalent relation on $W_\tau (X_n)$.

For a sequence of fixed terms $R = (r_1, \ldots, r_n)$ in $W_\tau (X_n)$, we denote by $[t]_{\sim_R}$ an equivalent class of $t\in W_\tau (X_n)$ relating to $\sim_R$. The next lemma describes a behaviour of terms within the same equivalent class based on $\sim_R$.

Lemma 3.5. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_\tau (X_n)$, $s, t\in W_\tau (X_n)$ with $sub(t)\cap R = \{r_{n_1}, \ldots, r_{n_k}\}$, and $t\sim_R s$ $($i.e., $t$ and $s$ are in the same equivalent class of $\sim_R)$ corresponding to a bijection $\alpha: sub(t)\cap R\rightarrow sub(s)\cap R$. Then $S^n_R (t, r_1, \ldots, r_{n_1-1}, \alpha (r_{n_1}), r_{n_1+1}, \ldots, r_{n_k-1}, \alpha (r_{n_k}), r_{n_k+1}, \ldots, r_n) = s$.

Proof. We prove by induction on the structure of $t$. If $t = r_j\in R$, then Lemma 3.3(ⅰ) yields $s = \alpha (r_j) = r_k\in R$. So, $S^n_R (t, r_1, \ldots, r_{j-1}, \alpha (r_j), r_{j+1}, \ldots, r_n) = S^n_R (r_j, r_1, \ldots, r_{j-1}, r_k, r_{j+1}, \ldots, r_n) = r_k = s$. For $t = f_i (t_1, \ldots, t_{n_i})\not\in R$ and $sub(t)\cap R\neq \emptyset$, we have by Lemma 3.3(ⅱ) that $s = f_i (s_1, \ldots, s_{n_i})$ and $t_j\sim_R s_j$ for all $j\in \{1, \ldots, n_i\}$ and if $sub(t_j)\cap R\neq \emptyset$, then the equivalence relates to $\alpha_j : = \alpha\mid_{sub(t_j)\cap R} : sub(t_j)\cap R \rightarrow sub(s_j)\cap R$. Inductively assume that for each $m\in \{1, \ldots, n_i\}$, if $sub(t_m)\cap R = \{r_{m_1}, \ldots, r_{m_a}\}$ and $t_m\sim_R s_m$, then $S^n_R (t_m, r_1, \ldots, r_{m_1-1}, \alpha (r_{m_1}), r_{m_1+1}, \ldots, r_{m_a-1}, \alpha (r_{m_a}), r_{m_a+1}, \ldots, r_m) = s_m$. Let $J = \{j\in \{1, \ldots, n_i\} \mid sub(t_j)\cap R\neq \emptyset \}$. By induction hypothesis and Lemma 2.4, we obtain $s_j = S^n_R (t_j, r_1, \ldots, r_{n_1-1}, \alpha (r_{n_1}), r_{n_1+1}, \ldots, r_{n_k-1}, \alpha (r_{n_k}), r_{n_k+1}, \ldots, r_n)$ for all $j\in J$. For each $l\in \{1, \ldots, n_i\}\setminus J$, we see that $sub(t_l)\cap R = \emptyset$ and by the definition of $\sim_R$, we get $t_l = s_l$. Hence, $S^n_R (t_l, r_1, \ldots, r_{n_1-1}, \alpha (r_{n_1}), r_{n_1+1}, \ldots, r_{n_k-1}, \alpha (r_{n_k}), r_{n_k+1}, \ldots, r_n) = t_l = s_l$. These imply that $S^n_R (t_k, r_1, \ldots, r_{n_1-1}, \alpha (r_{n_1}), r_{n_1+1}, \ldots, r_{n_k-1}, \alpha (r_{n_k}), r_{n_k+1}, \ldots, r_n) = s_k$ for all $k\in \{1, \ldots, n_i\}$. Therefore,

Note that the superposition of the form in the previous lemma is also valid for a term $t$ with $sub(t)\cap R = \emptyset$. Such form of a superposition in the above lemma leads to an essential result.

Corollary 3.1. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_{\tau_n} (X_n)$ and $s, t\in W^R_{\tau_n} (X_n)$ such that $t\sim_R s$. Then $\langle t\rangle_{n-clone_R \tau_n} = \langle s\rangle_{n-clone_R \tau_n}$.

Scoping out the generating system $G^R_{\tau_n}$ of $n\mbox{-clone}_R \tau_n$, we have a characterization of terms in the same $\sim_R$-equivalent class.

Lemma 3.6. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_{\tau_n} (X_n), u\in W^R_{\tau_n} (X_n)$, and $t\in G^R_{\tau_n}$. Then $t\sim_R u$ if and only if $t = S^n_R (u, u_1, \ldots, u_n)$ for some $u_1, \ldots, u_n\in W^R_{\tau_n} (X_n)\setminus \{t\}$.

Proof. One direction is immediately obtained from Lemma 3.5. On the other hand, assume that $t = S^n_R (u, u_1, \ldots, u_n)$ for some $u_1, \ldots, u_n\in W^R_{\tau_n} (X_n)\setminus \{t\}$. We consider 3 cases.

Case 1. $t\in X_n\cap (W^R_{\tau_n} (X_n)\setminus R)$.

If $sub(u)\cap R\neq \emptyset$, then Lemma 2.1 provides

for some $l\in \{1, \ldots, n\}$. This implies that $u_l = t$, a contradiction. Therefore, $sub(u)\cap R = \emptyset$ and hence $t = S^n_R (u, u_1, \ldots, u_n) = u$. This means that $t\sim_R u$.

Case 2. $t = f_i (t_1, \ldots, t_n)$ and $t_j\in sub(R)\setminus R$ for all $j\in \{1, \ldots, n\}$.

If $u = r_k\in R$, then $t = S^n_R (u, u_1, \ldots, u_n) = u_k$, a contradiction. For $u = f_i (s_1, \ldots, s_n)\not\in R$ and $sub(u)\cap R\neq \emptyset$, we let $K = \{k\in \{1, \ldots, n\} \mid sub(s_k)\cap R\neq \emptyset\}$. Then $K\neq \emptyset$ and $f_i (t_1, \ldots, t_n) = t = S^n_R (u, u_1, \ldots, u_n) = f_i (S^n_R (s_1, u_1, \ldots, u_n), \ldots, S^n_R (s_n, u_1, \ldots, u_n))$. So, $S^n_R (s_j, u_1, \ldots, u_n) = t_j$ for all $j\in \{1, \ldots, n\}$. Now for each $k\in K$, $S^n_R (s_k, u_1, \ldots, u_n) = t_k$ and $sub(s_k)\cap R\neq \emptyset$. By Lemma 2.1, we obtain $u_l\in sub(u_l)\subseteq sub(S^n_R (s_k, u_1, \ldots, u_n)) = sub(t_k)$ for some $l\in \{1, \ldots, n\}$ which means that $u_l\in sub(R)\setminus R$, a contradiction to $u_l\in W^R_{\tau_n} (X_n)$. Consequently, $sub(u)\cap R = \emptyset$ and thus $t = S^n_R (u, u_1, \ldots, u_n) = u$, i.e., $t\sim_R u$.

Case 3. $t = f_i (t_1, \ldots, t_n)$ and $t_j\not\in sub(R)\setminus R$ for some $j\in \{1, \ldots, n\}$.

Let $M = \{m\in \{1, \ldots, n\} \mid t_m\not\in sub(R)\setminus R\} = \{m\in \{1, \ldots, n\} \mid t_m = r_m\}$. Then $M\neq \emptyset$ which implies that $sub(t)\cap R\neq \emptyset$. We consider the possibility of $u$. If $u = r_k\in R$, then $t = S^n_R (u, u_1, \ldots, u_n) = u_k$, a contradiction. If $sub(u)\cap R = \emptyset$, then $t = S^n_R (u, u_1, \ldots, u_n) = u$ which contradicts to $sub(t)\cap R\neq\emptyset$. Therefore, $u = f_i (s_1, \ldots, s_n)\not\in R$ and $sub(u)\cap R\neq \emptyset$. This implies that $f_i (t_1, \ldots, t_n) = t = S^n_R (u, u_1, \ldots, u_n) = f_i (S^n_R (s_1, u_1, \ldots, u_n), \ldots, S^n_R (s_n, u_1, \ldots, u_n))$. For each $m'\in \{1, \ldots, n\}\setminus M$, $S^n_R (s_{m'}, u_1, \ldots, u_n) = t_{m'}\in sub(R)\setminus R$. If $sub(s_{m'})\cap R\neq \emptyset$, then by Lemma 2.1, there is $l\in \{1, \ldots, n\}$ such that $sub(u_l)\subseteq sub(t_{m'})$ which means that $u_l\in sub(R)\setminus R$, contradicting $u_l\in W^R_{\tau_n} (X_n)$. Hence, $sub(s_{m'})\cap R = \emptyset$ and thus $s_{m'} = S^n_R (s_{m'}, u_1, \ldots, u_n) = t_{m'}$. For each $m\in M$, we have that $S^n_R (s_m, u_1, \ldots, u_n) = t_m = r_m$. By Lemma 2.2(ⅲ), $s_m = r_{p_m}$ and $u_{p_m} = r_m$ for some $p_m \in \{1, \ldots, n\}$. Let $P = \{p\in \{1, \ldots, n\} \mid r_p = s_m \phantom{a} \mathit{\text{for some}} \phantom{a} m\in M\}$. We show that $\vert P\vert = \vert M\vert$, suppose not. Then $\vert P\vert < \vert M\vert$ or $\vert M\vert < \vert P\vert$. The latter is impossible since otherwise there will be $m\in M$ such that $r_p = s_m = r_{p'}$ for some distinct $p, p'\in P$ by pigeonhole principle. The former implies, by pigeonhole principle, that there are distinct $m, \tilde{m}\in M$ and $p\in P$ such that $s_m = r_p$ and $s_{\tilde{m}} = r_p$. Then Lemma 2.2(ⅲ) yields $r_m = u_p = r_{\tilde{m}}$ which is impossible. Therefore, $\vert P\vert = \vert M\vert$. This means that there is a bijection $\beta: M\rightarrow P$ or more accurately, a bijection $\alpha: sub(t)\cap R \rightarrow sub(u)\cap R$. So far we have the term $u = f_i (s_1, \ldots, s_n)$ where $s_{m'} = t_{m'}$ and $s_m = r_{p_m}$ for each $m'\in \{1, \ldots, n\}\setminus M$ and $m\in M$ and for some $p_m\in P$. It follows that the term $u$ can be obtained by swapping each $r\in sub(t)\cap R$ via a bijection $\alpha: sub(t)\cap R \rightarrow sub(u)\cap R$. So, $t\sim_R u$.

The proof is finally complete.

Lemma 3.6 provides a robust method how each term in the generating system $G^R_{\tau_n}$ of $n\mbox{-clone}_R \tau_n$ is generated. Such term can only be formed by using a term within the same $\sim_R$-class. Again, that term can only be generated by some term from the same $\sim_R$-class. This will be an endless process unless we include terms from that $\sim_R$-class in a generating set. Ideally, only one term from each $\sim_R$-class is needed if we want a minimal one. This discussion leads to the following corollary.

Corollary 3.2. The generating system $G^R_{\tau_n}$ of $n\mathit{\mbox{-clone}}_R \tau_n$ is minimal and the other minimal generating systems of the clone are collections of terms selecting from $\sim_R$-classs of terms in $G^R_{\tau_n}$, one from each class.

Extending the finding from Lemma 3.2, we now identify conditions which are equivalent to the self-freeness of $n\mbox{-clone}_R \tau_n$.

Theorem 3.1. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_{\tau_n} (X_n)$ and $\mathcal{G}$ be the collection of all minimal generating systems of $n\mathit{\mbox{-clone}}_R \tau_n$. Then the following statements are equivalent.

(i) The clone $n\mathit{\mbox{-clone}}_R \tau_n$ is free with respect to itself.

(ii) $R = (x_{\alpha (1)}, \ldots, x_{\alpha (n)})$ for some permutation $\alpha$ on $\{1, \ldots, n\}$ or $\tau_n = (1)$. (iii) There exists $G\in \mathcal{G}$ such that $X_n\cap G = \emptyset$ and $f_i (t_1, \ldots, t_n)\not\in G$ in which $t_j\in sub(R)\setminus R$ for some $j\in \{1, \ldots, n\}$.

Proof. (ⅰ) $\Rightarrow$ (ⅲ): Let $A$ be a generator of $n\mathit{\mbox{-clone}}_R \tau_n$ and $G\in \mathcal{G}$ such that $G\subseteq A$. Assume that $X_n\cap G\neq \emptyset$. By Lemma 3.1 and Corollary 3.2, $\vert G\vert \geq 1$. Let $t\in X_n\cap G, s_1, \ldots, s_n\in W^R_{\tau_n} (X_n)$, and $\varphi: G\rightarrow W^R_{\tau_n} (X_n)$ be a mapping. It follows by Lemma 3.1 and Corollary 3.2 that $t\in X_n\cap (W^R_{\tau_n} (X_n)\setminus R)$. In order for an extension $\overline{\varphi}$ of $\varphi$ to be an endomorphism of $n\mathit{\mbox{-clone}}_R \tau_n$, the following expression must be satisfied:

Note that $\varphi (t)$ can be any element from $W^R_{\tau_n} (X_n)$. For $\varphi (t) = r_1\in R$, we have

Since $s_1$ is arbitrary and $\vert G\vert \geq 1$, $\varphi$ must be an identity mapping of $G$ and it cannot be defined freely. Thus, any extension $\psi: A\rightarrow W^R_{\tau_n} (X_n)$ of $\varphi$ cannot be defined freely either. Therefore, $n\mathit{\mbox{-clone}}_R \tau_n$ is not free with respect to itself. Next, assume that $s = f_i (t_1, \ldots, t_n)\in G$ in which $t_j\in sub(R)\setminus R$ for some $j\in \{1, \ldots, n\}$. This implies that $\vert G \vert \geq 1$ by Lemma 3.1 and Corollary 3.2. Let $J = \{j\in \{1, \ldots, n\}\mid t_j\in sub(R)\setminus R\} = \{j_1, \ldots, j_m\}$. If $J = \{1, \ldots, n\}$, then $sub(s)\cap R = \emptyset$. To be a homomorphism, $\overline{\varphi}$ needs to satisfy

Consider $\varphi (s) = r_1\in R$ and we can imply that $n\mathit{\mbox{-clone}}_R \tau_n$ is not free with respect to itself by similar reasoning of the previous case. In the case of $J\neq\{1, \ldots, n\}$, we have by Lemma 3.1 and Corollary 3.2 that $t_{j'} = r_{\alpha (j')}$ for some injective mapping $\alpha: \{1, \ldots, n\}\setminus J \rightarrow \{1, \ldots, n\}$ for all $j'\in \{1, \ldots, n\}\setminus J$. The homomorphism requires

For $\varphi (s) = r_k$ for some $k\in \{1, \ldots, n\} \setminus \alpha (\{1, \ldots, n\}\setminus J)$, we see that

Since the leftmost term is not dominated by the term $s_k$, $\overline{\varphi} (s_k)$ gets mapped to a fixed element for any $s_k\in W^R_{\tau_n} (X_n)$. With similar reasoning from the first case, we conclude that $n\mathit{\mbox{-clone}}_R {\tau_n}$ is not free with respect to itself.

(ⅲ) $\Rightarrow$ (ⅱ): Suppose that $R\neq (x_{\alpha (1)}, \ldots, x_{\alpha (n)})$ for any permutation $\alpha$ on $\{1, \ldots, n\}$ and $\tau_n \neq (1)$. Let $G\in \mathcal{G}$. To show that there exists $f_i (t_1, \ldots, t_n) \in G$ in which $t_j\in sub(R)\setminus R$ for some $j\in \{1, \ldots, n\}$. By assumption, there is $r\in R$ such that $r = f_i (u_1, \ldots, u_n)$ for some $u_1, \ldots, u_n\in W_{\tau_n} (X_n)$. It follows that $u_1, \ldots, u_n\in sub(R)\setminus R$. If $n\geq 2$, then for a fixed operation symbol $f$,

So, $\{f(v_1, \ldots, v_n) \mid v_j\in sub(R)\setminus R \phantom{a} \ {\text{for some}}\ \phantom{a} j\in \{1, \ldots, n\} \}\cap G\neq \emptyset$. For the case $n = 1$ with two or more operation symbols, let $g$ be a unary operation symbol besides $f$. As $n = 1$, we have that $R = (f(u_1))$ or $R = (g(u_1))$ for some $u_1\in W_{\tau_1} (X_1)$. This implies that $u_1\in sub(R)\setminus R$. By Lemma 3.1 and Corollary 3.2, we get $g(u_1)\in G$ if $R = (f(u_1))$ and $f(u_1)\in G$ if $R = (g(u_1))$.

(ⅱ) $\Rightarrow$ (ⅰ): Assume that $R = (x_{\alpha (1)}, \ldots, x_{\alpha (n)})$ for some permutation $\alpha$ on $\{1, \ldots, n\}$. Lemma 3.1 provides $G^R_{\tau_n} = F^R_{\tau_n} = \{f_i (r_1, \ldots, r_n) \mid i\in I\}$. We extend $\varphi: G^R_{\tau_n} \rightarrow W^R_{\tau_n} (X_n)$ to $\overline{\varphi} : n\mathit{\mbox{-clone}}_R {\tau_n} \rightarrow n\mathit{\mbox{-clone}}_R {\tau_n}$ by defining

(1) $\overline{\varphi} (t) = t$ if $t\in R$;

(2) $\overline{\varphi} (t) = S^n_R (\varphi (f_i (r_1, \ldots, r_n)), \overline{\varphi} (t_1), \ldots, \overline{\varphi} (t_n))$ if $t = f_i (t_1, \ldots, t_n)$.

Note that the condition for the second case is actually $t = f_i (t_1, \ldots, t_n)\not\in R$ and $sub(t)\cap R\neq \emptyset$. Let $t, s_1, \ldots, s_n\in W^R_{\tau_n} (X_n)$. We prove by induction on the structure of $t$ that $\overline{\varphi}$ is an endomorphism of $n\mathit{\mbox{-clone}}_R {\tau_n}$. If $t = r_k\in R$, then

For $t = f_i (t_1, \ldots, t_n)\not\in R$ and $sub(t)\cap R\neq \emptyset$, we inductively assume that $\overline{\varphi} (S^n_R (t_j, s_1, \ldots, s_n)) = S^n_R (\overline{\varphi} (t_j), \overline{\varphi} (s_1), \ldots, \overline{\varphi} (s_n))$ for all $j\in \{1, \ldots, n\}$. Since $R$ is a sequence of all variables, $sub(S^n_R (t_j, s_1, \ldots, s_n))\cap R\neq \emptyset$ for any $j\in \{1, \ldots, n\}$. It follows that

These depict the homomorphism of $\overline{\varphi}$. Next, assume that $\tau_n = (1)$ with $f$ as the unary operation symbol. It is easy to identify that $G^R_{\tau_n} = \{f(r_1)\}$ and $W^R_{\tau_n} (X_n) = \{r_1, f(r_1), f(f(r_1)), f(f(f(r_1))), \ldots\}$. Note that $sub(u)\cap R\neq \emptyset$ for all $u\in W^R_{\tau_n} (X_n)$. We extend $\varphi: G^R_{\tau_n}\rightarrow W^R_{\tau_n} (X_n)$ to $\overline{\varphi}: n\mathit{\mbox{-clone}}_R {\tau_n}\rightarrow n\mathit{\mbox{-clone}}_R {\tau_n}$ by defining $\overline{\varphi} (r_1) = r_1$ and $\overline{\varphi} (t) = S^n_R (\varphi (f (r_1)), \overline{\varphi} (t_1))$ if $t = f (t_1)$. Let $t, s_1\in W^R_{\tau_n} (X_n)$. We show that $\overline{\varphi} (S^n_R (t, s_1)) = S^n_R (\overline{\varphi} (t), \overline{\varphi} (s_1))$. This is immediate when $t = r_1$, so only the case $t = f(t_1)\not\in R$ remains. Inductively assume that $\overline{\varphi} (S^n_R (t_1, s_1)) = S^n_R (\overline{\varphi} (t_1), \overline{\varphi} (s_1))$. We then obtain

Consequently, $n\mathit{\mbox{-clone}}_R {\tau_n}$ is free with respect to itself.

The condition for the clone $n\mbox{-clone}_R {\tau_n}$ to be free with respect to itself is eventually obtained. It provides that not every form of mapping $\varphi$ from a minimal generator $M$ to $W^R_{\tau_n} (X_n)$ can be extended to an endomorphism of the clone. The final theorem here gives a sufficient condition for such mapping to be extendable as an endomorphism of the clone.

Theorem 3.2. Let $R = (r_1, \ldots, r_n)$ be a sequence of fixed terms in $W_{\tau_n} (X_n)$. Then a mapping $\varphi: G^R_{\tau_n}\rightarrow W^R_{\tau_n} (X_n)$ can be extended to an endomorphism on $n\mathit{\mbox{-clone}}_R \tau_n$ if for each $t\in G^R_{\tau_n}$, $sub(\varphi (t))\cap R \subseteq sub(t)\cap R$.

Proof. Assume that $sub(\varphi (t))\cap R \subseteq sub(t)\cap R$ for each $t\in G^R_{\tau_n}$. Define $\overline{\varphi}: W^R_{\tau_n} (X_n)\rightarrow W^R_{\tau_n} (X_n)$ in the following way: for each $t\in W^R _{\tau_n} (X_n)$,

$({\rm{i}})$ $\overline{\varphi} (t) = t$ if $t\in R$.

$({\rm{ii}})$ $\overline{\varphi} (t) = \varphi (t)$ if $t\in X_n\setminus R$.

$({\rm{iii}})$ $\overline{\varphi} (f_i (t_1, \ldots, t_n)) = S^n_R (\varphi (f_i (r_1, \ldots, r_n)), \overline{\varphi} (t_1), \ldots, \overline{\varphi} (t_n))$ if $t_j\in W^R_{\tau_n} (X_n)$ for all $j\in \{1, \ldots, n\}$.

$({\rm{iv}})$ $\overline{\varphi} (f_i (t_1, \ldots, t_n)) = S^n_R (\varphi (f_i (r_1, \ldots, r_{k_1-1}, t_{k_1}, r_{k_1+1}, \ldots, r_{k_m-1}, t_{k_m}, r_{k_m+1}, \ldots, r_n)), \overline{\varphi} (t_1), \ldots, \overline{\varphi} (t_{k_1-1}), u_{k_1}, \overline{\varphi} (t_{k_1+1}), \ldots, \overline{\varphi} (t_{k_m-1}), u_{k_m}, \overline{\varphi} (t_{k_m+1}), \ldots, \overline{\varphi} (t_n))$ for some $u_{k_1}, \ldots, u_{k_m}\in W^R_{\tau_n} (X_n)$ such that $sub(u_l)\cap R = \emptyset$ for all $l\in \{k_1, \ldots, k_m\}$ if $t_{k_1}, \ldots, t_{k_m}\in sub(R)\setminus R$.

We first show that $\overline{\varphi}$ is an extension of $\varphi$ to $W^R_{\tau_n} (X_n)$. This is clear for $t\in X_n\setminus R$. Let $t = f_i (t_1, \ldots, t_n)\in G^R_{\tau_n}$. If $t_j = r_j$ for all $j\in \{1, \ldots, n\}$, then by (iii) and (C3), we see that $\overline{\varphi} (t) = \overline{\varphi} (f_i (r_1, \ldots, r_n)) = S^n_R (\varphi (f_i (r_1, \ldots, r_n)), \overline{\varphi} (r_1), \ldots, \overline{\varphi} (r_n)) = S^n_R (\varphi (f_i (r_1, \ldots, r_n)), r_1, \ldots, r_n) = \varphi (f_i (r_1, \ldots, r_n)) = \varphi (t)$. Next, for the case of $t_j\neq r_j$ for some $j\in \{1, \ldots, n\}$, we set $K = \{k_1, \ldots, k_m\} \subseteq \{1, \ldots, n\}$ to be the set of all indices such that $t_k\in sub(R)\setminus R$ for all $k\in K$. So, $t_p = r_p$ for all $p\in \{1, \ldots, n\}\setminus K$ and $sub(t)\cap R = \{r_p\mid p\in \{1, \ldots, n\}\setminus K\}$. It follows from the assumption that $sub(\varphi(t))\cap R \subseteq \{r_p\mid p\in \{1, \ldots, n\}\setminus K\}$. Then (ⅳ), (C3), and Lemma 2.4 give out

where $u_{k_1}, \ldots, u_{k_m}\in W^R_{\tau_n} (X_n)$ such that $sub(u_l)\cap R = \emptyset$ for all $l\in \{k_1, \ldots, k_m\}$. These represent the required extension. Only an endomorphism of $\overline{\varphi}$ is left to be proved. Let $t, s_1, \ldots, s_n\in W^R_{\tau_n} (X_n)$. We show that $\overline{\varphi} (S^n_R (t, s_1, \ldots, s_n)) = S^n_R (\overline{\varphi} (t), \overline{\varphi} (s_1), \ldots, \overline{\varphi} (s_n))$. If $t = r_j\in R$ for some $j\in \{1, \ldots, n\}$, then

If $t\in X_n\setminus R$, then $t\in G^R_{\tau_n}$ and by assumption, we get $sub(\varphi (t))\cap R \subseteq sub(t)\cap R = \{t\}\cap R = \emptyset$, and thus $sub(\varphi (t))\cap R = \emptyset$. Therefore,

Next, we consider the case $t = f_i (t_1, \ldots, t_n)\not\in R$ and $sub(t)\cap R = \emptyset$. Hence, $sub(t_j)\cap R = \emptyset$ for all $j\in \{1, \ldots, n\}$. We first show that $sub(\overline{\varphi} (t))\cap R = \emptyset$. If $t_j\in X_n$ for each $j\in \{1, \ldots, n\}$, then $t_j\in G^R_{\tau_n}$ or $t_j\in sub(R)\setminus R$. The former implies that $sub(\overline{\varphi} (t_j))\cap R = \emptyset$ due to the assumption at the beginning. Furthermore, there are two possible forms of $\overline{\varphi} (t)$, each of which corresponds to (ⅲ) or (ⅳ). Thanks to Lemma 2.3, we obtain, regardless of the form of $\overline{\varphi} (t)$, that $sub(\overline{\varphi} (t))\cap R = \emptyset$. For the case of $t_j = f_{i_j} (t_{1_j}, \ldots, t_{n_j})$ for some $j\in \{1, \ldots, n\}$, let $T$ be the set of all terms among $t_1, \ldots, t_n$ which are not a variable. It follows that $T\neq\emptyset$. Since $t\not\in R$ and $sub(t)\cap R = \emptyset$, we have that $u\not\in R$ and $sub(u)\cap R = \emptyset$ for any $u\in T$. Assume inductively that $sub(\overline{\varphi} (u))\cap R = \emptyset$. Using similar reasoning from the previous case, we eventually obtain $sub(\overline{\varphi} (t))\cap R = \emptyset$. Now, we have shown that $sub(\overline{\varphi} (t))\cap R = \emptyset$. Thus, we have that $S^n_R (\overline{\varphi} (t), \overline{\varphi} (s_1), \ldots, \overline{\varphi} (s_n)) = \overline{\varphi} (t) = \overline{\varphi} (S^n_R (t, s_1, \ldots, s_n))$.

Only the case $t = f_i (t_1, \ldots, t_n)\not\in R$ and $sub(t)\cap R\neq\emptyset$ remains. Inductively assume that $\overline{\varphi} (S^n_R (t_j, s_1, \ldots, s_n)) = S^n_R (\overline{\varphi} (t_j), \overline{\varphi} (s_1), \ldots, \overline{\varphi} (s_n))$ for each $j\in \{1, \ldots, n\}$ with $t_j\in W^R_{\tau_n} (X_n)$. If $t_j\in W^R_{\tau_n} (X_n)$ for all $j\in \{1, \ldots, n\}$, we then have

If some of $t_1, \ldots, t_n$ belong to $sub(R)\setminus R$, let $K = \{k_1, \ldots, k_m\}\subseteq \{1, \ldots, n\}$ be the set of all indices such that $t_k\in sub(R)\setminus R$ for all $k\in K$. Hence, $S^n_R (t_k, s_1, \ldots, s_n) = t_k$ for each $k\in K$; moreover, $t_p\in W^R_{\tau_n} (X_n)$ for each $p\in \{1, \ldots, n\}\setminus K$, and hence $S^n_R (t_p, s_1, \ldots, s_n)\in W^R_{\tau_n} (X_n)$.

Note that for each term $u\in W_{\tau_n} (X_n)$ with $sub(u)\cap R = \emptyset$, $u = S^n_R (u, \overline{\varphi} (s_1), \ldots, \overline{\varphi} (s_n))$. Then

where $u_{k_1}, \ldots, u_{k_m}\in W^R_{\tau_n} (X_n)$ such that $sub(u_l)\cap R = \emptyset$ for all $l\in \{k_1, \ldots, k_m\}$. Consequently, $\overline{\varphi}$ is an endomorphism.

Although this final theorem only considers the minimal generating system $G^R_{\tau_n}$, other minimal ones can be substituted for $G^R_{\tau_n}$ since each term of any minimal generating system is $R$-equivalent to the corresponding term from $G^R_{\tau_n}$ due to Corollary 3.2. However, the way we define an extension $\overline{\varphi}$ will be slightly different from that of $G^R_{\tau_n}$.

It is crucial to remark that the converse of the previous theorem does not hold. A simple incident occurs where $sub(R)\setminus R\neq \emptyset$, ensuring the existence of $t\in G^R_{\tau_n}$ such that $sub(t)\cap R = \emptyset$, and $\varphi: G^R_{\tau_n}\rightarrow W^R_{\tau_n} (X_n)$ maps each element in the generating set $G^R_{\tau_n}$ to a fixed term $r\in R$. Then we can simply extend the mapping to a constant mapping of $W^R_{\tau_n} (X_n)$ which makes it an endomorphism; however, $sub(\varphi (t))\cap R = \{r\} \nsubseteq \emptyset = sub(t)\cap R$.

4.   Conclusions

The main discoveries from this paper regard the properties of an inductive superposition, a superposition performing the subterm replacement instead of the usual variable replacement. Acting as an $(n+1)$-ary operation, an inductive superposition induces a unitary Menger algebra of rank $n$ whose form generalizes that of ^[12]. By using the concept of $R$-equivalent class, we managed to classify all possible minimal generating systems of the clone $n\mbox{-clone}_R {\tau_n}$ and found out that the clone is not free with respect to itself for some sequences of fixed terms. Fortunately, we were able to seek out all possible conditions for the clone to be self-free. Lastly, a sufficient condition for a mapping to be extendable to an endomorphism of the clone was given. The future research may possibly be conducted toward the use of an inductive superposition in place of a usual variable-replacing superposition such as in the context of a hypersubstitution and of a superposition of tree languages.

Acknowledgments

This research was supported by the Fundamental Fund of Khon Kaen University.

Conflict of interest

All authors declare no conflicts of interest in this paper.