An algebraic theory of clones

Abstract

We introduce the notion of clone algebra ($\mathsf {CA}$), intended to found a one-sorted, purely algebraic theory of clones. $\mathsf {CA}$s are defined by identities and thus form a variety in the sense of universal algebra. The most natural $\mathsf {CA}$s, the ones the axioms are intended to characterise, are algebras of functions, called functional clone algebras ($\mathsf {FCA}$). The universe of a $\mathsf {FCA}$, called $\omega$-clone, is a set of infinitary operations on a given set, containing the projections and closed under finitary compositions. The main result of this paper is the general representation theorem, where it is shown that every $\mathsf {CA}$ is isomorphic to a $\mathsf {FCA}$ and that the variety $\mathsf {CA}$ is generated by the class of finite-dimensional $\mathsf {CA}$s. This implies that every $\omega$-clone is algebraically generated by a suitable family of clones by using direct products, subalgebras and homomorphic images. We conclude the paper with two applications. In the first one, we use clone algebras to give an answer to a classical question about the lattices of equational theories. The second application is to the study of the category of all varieties of algebras.

1 Introduction

Clones are sets of finitary operations on a given set that contain all the projections and are closed under composition. They play an important role in universal algebra due to the fact that the set of all term operations of an algebra always forms a clone. Moreover, important properties, like whether a given subset forms a subalgebra, or whether a given map is a homomorphism, do not depend on the specific fundamental operations of the considered algebra, but rather on the clone of its term operations. Hence, comparing clones of algebras is much more suitable than comparing their signatures, in order to classify them according to essentially different behaviours (see [21, 22]). Some attempts have been made to encode clones into algebras. A particularly important one led to the concept of abstract clones [4, 22], which are many-sorted algebras axiomatising composition of finitary functions and projections. Every abstract clone has a concrete representation as an isomorphic clone of finitary operations. Modulo a caveat about nullary operations, we remark that abstract clones may be recasted as a reformulation of the concept of Lawvere’s algebraic theories [9]. The latter constitutes a common category theoretic mean to capture equational theories independently of their presentation (i.e. of the chosen similarity type). Another attempt to encode clones into algebras is due to Neumann [15] and led to the concept of abstract $\aleph _0$-clones, which are infinitary algebras axiomatising all projections and one infinitary operation of composition. Every abstract $\aleph _0$-clone has a concrete representation as an isomorphic $\aleph _0$-clone of algebraic operations of rank $\aleph _0$ of a variety defined by infinitary operations.

Some work at the frontier of theoretical computer science and universal algebra provides tools for giving an alternative algebraic account of clones. The algebraic treatment of the if-then-else construct of computer science originated with Dicker’s axiomatisation of Boolean algebras in the language with the if-then-else as primitive [5]. Accordingly, this construct was treated in [11, 19] as a proper algebraic operation $q_2$ of arity three on algebras whose type contains, besides the ternary term $q_2$, two constants 0 and 1. This approach was generalised in [2, 20] to algebras having n designated elements ${\mathsf {e}}_1,\dots , {\mathsf {e}}_n$ and a $(n + 1)$-ary operation $q_n$ (a sort of “generalised if-then-else”) satisfying the identities $q_n({\mathsf {e}}_i,x_1,\dots ,x_n)=x_i$. Such algebras, called Church algebras of dimension n in [20], will be termed here n-Church algebras.

In the framework of n-Church algebras, the constants ${\mathsf {e}}_i$ and the $(n+1)$-ary operation $q_n$ represent the generalised truth-values and the generalised conditional operation, respectively. More generally, these constants and operation allow to express neatly other fundamental algebraic concepts as one-sorted, purely algebraic theories. These include in particular: (i) variables and term-for-variable substitution in free algebras on one side, and (ii) projections and functional composition in clones on the other.

Building up on this observation, we introduce in this paper an algebraic theory of clones. Indeed, the variety of clone algebras ($\mathsf {CA}$) introduced here constitutes a purely one-sorted algebraic theory of clones in the same spirit as Boolean algebras constitute an algebraic theory of classical propositional logic. Clone algebras of a given similarity type $\tau$ ($\mathsf {CA}_\tau$s) are defined by universally quantified equations and thus form a variety in the universal algebraic sense. The operators of type $\tau$ are taken as fundamental operations in $\mathsf {CA}_\tau$s. A crucial feature of our approach is connected with the role played by variables in free algebras and by projections in clones. In clone algebras these are abstracted out, and take the form of a system of fundamental elements (nullary operations) ${\mathsf {e}}_1,{\mathsf {e}}_2,\dots ,{\mathsf {e}}_n,\dots$ of the algebra. One important consequence of the abstraction of variables and projections is the abstraction of term-for-variable substitution and functional composition in $\mathsf {CA}_\tau$s, obtained by introducing an $(n+1)$-ary operator $q_n$ for every $n\ge 0$. Roughly speaking, $q_n(a,b_1,\dots ,b_n)$ represents the substitution of $b_i$ for ${\mathsf {e}}_i$ into a for $1\le i\le n$ (or the composition of a with $b_1,\dots ,b_n$).

The most natural $\mathsf {CA}$s, the ones the axioms are intended to characterise, are algebras of functions, called functional clone algebras. The elements of a functional clone algebra are infinitary operations from $A^{\mathbb {N}}$ into A, for a given set A. In this framework $q_n(f,g_1,\dots ,g_n)$ represents the n-ary composition of f with $g_1,\dots ,g_n$, acting on the first n coordinates:

$$\begin{aligned} q_n(f,g_1,\dots ,g_n)(s)= f(g_1(s),\dots ,g_n(s),s_{n+1},s_{n+2},\dots ),\ \hbox { for every}\ s\in A^{\mathbb {N}} \end{aligned}$$

and the nullary operators are the projections $p_i$ defined by $p_i(s)=s_i$ for every $s\in A^{\mathbb {N}}$. Hence, the universe of a functional clone algebra is a set of infinitary operations containing the projection $p_i$ and closed under finitary compositions, called hereafter $\omega$-clone. We show that there exists a bijective correspondence between clones (of finitary operations) and a suitable subclass of functional clone algebras, called block algebras. Given a clone C, the corresponding block algebra is obtained by extending the operations of the clone by countably many dummy arguments. If $f\in C$ has arity k, then the top expansion of f is an infinitary operation $f^\top :A^{\mathbb {N}}\rightarrow A$:

$$\begin{aligned} f^\top (s_1,\dots ,s_k,s_{k+1},\dots )=f(s_1,\dots ,s_k), \end{aligned}$$

for every $(s_1,\dots ,s_k,s_{k+1}\dots )\in A^{\mathbb {N}}$. By collecting all these top expansions in a set $C^\top =\{f^\top : f\in C\}$, we get a functional clone algebra, called block algebra. In the first representation theorem of the paper we show that the “concrete” notion of block algebra coincides, up to isomorphism, with the abstract notion of finite-dimensional clone algebra, where a clone algebra is finite-dimensional if each of its elements can be assigned a finite dimension, abstracting the notion of arity to infinitary functions.

The axiomatisation of functional clone algebras is a central issue in the algebraic approach to clones. We say that a clone algebra is functionally representable if it is isomorphic to a functional clone algebra. The main result of this paper is the general representation theorem, where it is shown that every $\mathsf {CA}$ is functionally representable. In another result of the paper we prove that the variety of clone algebras is generated by the class of block algebras. This implies that every $\omega$-clone is algebraically generated by a suitable family of clones by using direct products, subalgebras and homomorphic images.

We conclude the paper with two applications. The first one is to the lattice of equational theories problem stated by Birkhoff [1] and Maltsev [10]: Find an algebraic characterisation of those lattices which are isomorphic to a lattice of equational theories. This problem is still open, but work on it has led to many results described in [14, Section 4]. The problem of characterising the lattices of equational theories as the congruence lattices of a class of algebras was tackled by Newrly [16] and Nurakunov [17]. In this paper we propose an alternative answer to the lattice of equational theories problem. We prove that a lattice is isomorphic to a lattice of equational theories if and only if it is isomorphic to the lattice of all congruences of a finite-dimensional clone algebra. Unlike in Newrly’s and Nurakunov’s approaches, we are able to provide the equational axiomatisation of the variety whose congruence lattices are exactly the lattices of equational theories, up to isomorphisms.

The second application is to the study of the category $\mathcal {VAR}$ of all varieties. We show that a clone algebra ${\mathbf {C}}$ of type $\tau$ is minimal (i.e., it is generated by the constants ${\mathsf {e}}_i$) if and only if the $\tau$-reduct ${\mathbf {C}}_\tau$ of ${\mathbf {C}}$ is the free algebra over a countable set of generators in the variety generated by ${\mathbf {C}}_\tau$. We introduce the category $\mathcal {CA}$ of all clone algebras (of arbitrary similarity type) with pure homomorphisms (i.e., preserving only the nullary operators ${\mathsf {e}}_i$ and the operators $q_n$) as arrows and show that $\mathcal {CA}$ is equivalent to the full subcategory $\mathcal {MCA}$ of minimal clone algebras. After showing that $\mathcal {MCA}$ is isomorphic to $\mathcal {VAR}$ as a category, we directly use $\mathcal {MCA}$ to show a generalisation of the theorem on independent varieties presented by Grätzer et al. in [7].

2 Preliminaries

The notation and terminology in this paper are pretty standard. For concepts, notations and results not covered hereafter, the reader is referred to [3, 13] for universal algebra and to [8, 21, 22] for the theory of clones.

In this paper ${\mathbb {N}}=\{1,2,\dots \}$ denotes the set of positive natural numbers.

By an operation on a set A we will always mean a finitary operation (i.e., a function $f:A^n\rightarrow A$ for some $n\ge 0$). By an infinitary operation on A we mean a function from $A^{\mathbb {N}}$ into A. As a matter of notation, operations will be denoted by the letters $f,g,h,\dots$ and infinitary operations by the greek letters $\varphi ,\psi ,\chi ,\dots$.

We denote by ${\mathcal {O}}_A$ the set of all operations on a set A, and by ${\mathcal {O}}_A^{({\mathbb {N}})}$ the set of all infinitary operations on A. If $F\subseteq {\mathcal {O}}_A$, then $F^{(n)}= \{f:A^n\rightarrow A\ |\ f\in F\}$.

In the following we fix a countable infinite set $I=\{v_1, v_2,\dots , v_n,\dots \}$ of variables that we assume totally ordered: $v_1< v_2<\dots< v_n<\cdots$.

2.1 Algebras

If $\tau$ is an algebraic type, then we denote by $T_\tau (I)$ the set of $\tau$-terms over the countable infinite set I of variables. If t is a $\tau$-term, then we write $t=t(v_1,\dots ,v_n)$ if t can be built up starting from variables $v_1,\dots ,v_n$.

If ${\mathcal {V}}$ is a variety, then we denote by ${\mathbf {F}}_{\mathcal {V}}$ its free algebra over the countable infinite set I of generators. Moreover, $Eq({\mathcal {V}})$ denotes the set of identities true in every member of ${\mathcal {V}}$.

Closure of a class of similar algebras under homomorphic images, direct products, subalgebras and isomorphic images is denoted by ${\mathbb {H}}$, ${\mathbb {P}}$, ${\mathbb {S}}$ and ${\mathbb {I}}$ respectively. We denote by ${\mathbb {P}}_U$ the closure under ultraproducts. $\mathrm {Var}(K)$ denotes the variety generated by a class K of $\tau$-algebras.

We write $\theta (a,b)$ for the smallest congruence such that $( a,b) \in \theta$.

$L({\mathcal {V}})$ will denote the lattice of all subvarieties of a variety ${\mathcal {V}}$. We recall that the join ${\mathcal {V}}_1\vee {\mathcal {V}}_2$ of two subvarieties ${\mathcal {V}}_1,{\mathcal {V}}_2\subseteq {\mathcal {V}}$ is axiomatised by $Eq({\mathcal {V}}_1)\cap Eq({\mathcal {V}}_2)$, while the meet ${\mathcal {V}}_1\cap {\mathcal {V}}_2$ by the equational theory generated by the union $Eq({\mathcal {V}}_1)\cup Eq({\mathcal {V}}_2)$. If ${\mathcal {V}}_1,\dots ,{\mathcal {V}}_n$ are subvarieties of ${\mathcal {V}}$, then ${\mathcal {V}}_1,\dots ,{\mathcal {V}}_n$ are said to be independent if there exists a term $t(v_1,\dots ,v_n)$ of type $\tau$ such that ${\mathcal {V}}_i\models t(v_1,\dots ,v_n)=v_i$ ($i=1,\dots ,n$). Moreover, the product of ${\mathcal {V}}_1,\dots ,{\mathcal {V}}_n$ is defined as ${\mathcal {V}}_1\times \dots \times {\mathcal {V}}_n ={\mathbb {I}}\,\{{\mathbf {A}}_1\times \dots \times {\mathbf {A}}_n :{\mathbf {A}}_i \in {\mathcal {V}}_i\}$.

The reader can consult [13] for the basic ingredients of factorisation, namely tuples of complementary factor congruences and decomposition operators.

We recall from [2, 19] the notion of an n-Church algebra. Algebras of type $\tau$, equipped with at least n nullary term operations ${\mathsf {e}}_1,\dots ,{\mathsf {e}}_n$ and a term operation $q_n$ of arity $n+1$ satisfying $q_n({\mathsf {e}}_i,x_1,\dots ,x_n)=x_i$ for each $i\in \{1,\dots ,n\}$ are called n-Church algebras ($n\mathrm {CH}$, for short).

In [23], Vaggione introduced the notion of central element to study algebras whose complementary factor congruences can be replaced by certain elements of their universes.

Proposition 2.1

[11, 20] If $\mathbf {A}$ is an $n\mathrm {CH}$ of type $\tau$ and $c\in A$, then the following conditions are equivalent:

• (1) the sequence of principal congruences $\theta (c,{\mathsf {e}}_{1}),\dots ,\theta (c,{\mathsf {e}}_{n})$ is an n-tuple of complementary factor congruences of $\mathbf {A}$;

• (2) The element c satisfies the following identities:

• D1. $q_n(c,{\mathsf {e}}_{1},\dots ,{\mathsf {e}}_{n})=c$

• D2. $q_n(c,x,\dots ,x) =x$

• D3. $q_n(c, q_n(c, x_{11},\dots ,x_{1n}),\dots ,q_n(c,x_{n1},\dots ,x_{nn}))= q_n(c,x_{11},\dots ,x_{nn})$

• D4. $q_n(c,-,\dots ,-)$ is an algebra homomorphism from $\mathbf {A}^n$ onto $\mathbf {A}$.

An element c of an $n\mathrm {CH}$ is called n-central if it satisfies one of the equivalent conditions of Proposition 2.1. Thus, c is n-central if and only if the function $f_{c}$, defined by $f_{c}(a_{1},\dots ,a_{n})=q_n(c,a_{1},\dots ,a_{n})$ for all $a_1,\dots ,a_n\in A$, is an n-ary decomposition operator on $\mathbf {A}$ such that $f_{c}({\mathsf {e}}_{1},\dots ,{\mathsf {e}}_{n})=c$. Every n-central element $c\in A$ induces a decomposition of $\mathbf {A}$ as a direct product of the algebras $\mathbf {A}/\theta (c,{\mathsf {e}}_{i})$, for $i\le n$, and every decomposition of $\mathbf {A}$ is (up to isomorphism) determined by a central element.

2.2 Clones of operations

In this section we recall notations and terminology on clones we will use in the following.

The composition of $f\in {\mathcal {O}}_A^{(n)}$ with $g_1,\dots ,g_n\in {\mathcal {O}}_A^{(k)}$ is the operation $f(g_1,\dots ,g_n)_k\in {\mathcal {O}}_A^{(k)}$ defined as follows, for all ${\mathbf {a}}\in A^k$:

$$\begin{aligned} f(g_1,\dots ,g_n)_k({\mathbf {a}})= f(g_1({\mathbf {a}}),\dots , g_n({\mathbf {a}})). \end{aligned}$$

If $f\in {\mathcal {O}}_A^{(0)}$ then $f()_k\in {\mathcal {O}}_A^{(k)}$ and $f()_k({\mathbf {a}})= f$ for all ${\mathbf {a}}\in A^k$. When there is no danger of confusion, we write $f(g_1,\dots ,g_n)$ for $f(g_1,\dots ,g_n)_k$.

A clone on a set A is a subset F of ${\mathcal {O}}_A$ containing all projections $p^{(n)}_i:A^n\rightarrow A$ ($n\ge i$) and closed under composition. A clone on a $\tau$-algebra ${\mathbf {A}}$ is a clone on A containing the operations $\sigma ^{\mathbf {A}}$ ($\sigma \in \tau$) of ${\mathbf {A}}$.

The classical approach to clones, as evidenced by the standard monograph [21], considers clones only containing operations that are at least unary. However, the full generality of some results in this paper requires clones allowing nullary operators.

2.2.1 Abstract clones

We recall from [22] and [6, p. 239] that an abstract clone is a many-sorted algebra composed of disjoint sets $B_n$ ($n\ge 0$), elements $\pi _i^{(n)}\in B_n$ ($n\ge 1$) for all $i\le n$, and a family of operations $C^n_k: B_n\times (B_k)^n \rightarrow B_k$ for all k and n such that

• (1) $C^n_k(C^m_n(x,y_1,\dots ,y_m),{\mathbf {z}})= C^m_n(x,C^n_k(y_1,{\mathbf {z}}),\dots ,C^n_k(y_m,{\mathbf {z}}))$, where x is a variable of sort m, $y_1,\dots ,y_m$ of sort n and ${\mathbf {z}}$ of sort k;

• (2) $C^n_n(x,\pi _1^{(n)},\dots ,\pi _n^{(n)})=x$, where x is a variable of sort n;

• (3) $C^n_k(\pi _i^{(n)},y_1,\dots ,y_n)=y_i$, where $y_1,\dots ,y_n$ are variables of sort k.

Any clone on a set determines an abstract clone, and every abstract clone has a concrete representation as an isomorphic clone of finitary operations (see [6, Section 3]). The connection between abstract clones and clone algebras is explained in Theorem 3.20 below.

2.2.2 Neumann’s abstract $\aleph _0$-clones [15, 22]

The idea here is to regard an n-ary operation f as an infinitary operation that only depends on the first n arguments. The corresponding abstract definition is as follows. An abstract $\aleph _0$-clone is an infinitary algebra $(A,{\mathsf {e}}_i,q_\infty )$, where the ${\mathsf {e}}_i$ ($1\le i<\omega$) are nullary operators and $q_\infty$ is an infinitary operation satisfying the following axioms:

• N1. $q_\infty ({\mathsf {e}}_i,x_1,\dots ,x_n,\dots )=x_i$;

• N2. $q_\infty (x,{\mathsf {e}}_1,\dots ,{\mathsf {e}}_n,\dots )=x$;

• N3. $q_\infty (q_\infty (x,{\mathbf {y}}),{\mathbf {z}})= q_\infty (x,q_\infty (y_1,{\mathbf {z}}),\dots ,q_\infty (y_n,{\mathbf {z}}),\dots )$, where ${\mathbf {y}}$ and ${\mathbf {z}}$ are countable infinite sequences of variables.

A functional $\aleph _0$-clone with value domain A is an algebra $(F,{\mathsf {e}}_i^{\mathbb {N}},q_\infty ^{\mathbb {N}})$, where $F\subseteq {\mathcal {O}}_A^{({\mathbb {N}})}$, ${\mathsf {e}}_i^{\mathbb {N}}(s)=s_i$, and for every $\varphi ,\psi _i\in F$ and every $s\in A^{\mathbb {N}}$, $q_\infty ^{\mathbb {N}}(\varphi ,\psi _1,\dots ,\psi _n,\dots )(s)=\varphi (\psi _1(s),\dots ,\psi _n(s),\dots )$.

Neumann shows in [15] that every abstract $\aleph _0$-clone is isomorphic to a functional $\aleph _0$-clone and that there is a faithful functor from the category of clones to the category of abstract $\aleph _0$-clones, but this functor is not onto.

The connection between Neumann’s abstract $\aleph _0$-clones and clone algebras is explained in Section 4.3.

3 Clone algebras

We have described in Section 2.2 two attempts to encode clones into algebras using many-sorted algebras in the first approach, and infinitary algebras in the second one. In this section we introduce the variety of clone algebras as a more canonical algebraic account of clones using standard one-sorted algebras. In our approach we replace Neumann’s infinitary operator of composition by a countable infinite set of finitary operators of composition.

The algebraic type of clone algebras contains a countable infinite family of nullary operators ${\mathsf {e}}_i$ and, for each $n\ge 0$, an operator $q_n$ of arity $n+1$. The algebraic type of clone $\tau$-algebras is $\tau \cup \{ q_n: n\ge 0\} \cup \{ {\mathsf {e}}_i : i\ge 1\}$.

In the remaining part of this paper when we write $q_n(x,{\mathbf {y}})$ it will be implicitly stated that ${\mathbf {y}}=y_1,\dots ,y_n$ is a sequence of length n.

Definition 3.1

A clone $\tau$-algebra is an algebra ${\mathbf {C}} = ({\mathbf {C}}_\tau , q^{\mathbf {C}}_n,{\mathsf {e}}^{\mathbf {C}}_i)_{n\ge 0,i\ge 1}$ satisfying the following conditions:

• C1. ${\mathbf {C}}_\tau = (C,\sigma ^{\mathbf {C}})_{\sigma \in \tau }$ is a $\tau$-algebra;

• C2. $q_n({\mathsf {e}}_i,x_1,\dots ,x_n)=x_i$ $(1\le i\le n)$;

• C3. $q_n({\mathsf {e}}_j,x_1,\dots ,x_n)={\mathsf {e}}_j$ $(j>n)$;

• C4. $q_n(x,{\mathsf {e}}_1,\dots ,{\mathsf {e}}_n)=x$ $(n\ge 0)$;

• C5. $q_k(x, y_1,\dots ,y_k)= q_n(x,y_1,\dots ,y_k,{\mathsf {e}}_{k+1},\dots ,{\mathsf {e}}_n)$ ($n> k$);

• C6. $q_n(q_n(x,y_1,\dots ,y_n), {\mathbf {z}})=q_n(x,q_n(y_1,{\mathbf {z}}),\dots ,q_n(y_n,{\mathbf {z}}))$;

• C7. $q_n(\sigma (x_1,\dots ,x_k),{\mathbf {y}}) = \sigma (q_n(x_1,{\mathbf {y}}),\dots ,q_n(x_k,{\mathbf {y}}))$ for every $\sigma \in \tau$ of arity k and every $n\ge 0$.

If $\tau$ is empty, an algebra satisfying (C2)–(C6) is called a pure clone algebra.

In the following, when there is no danger of confusion, we will write ${\mathbf {C}} = ({\mathbf {C}}_\tau , q^{\mathbf {C}}_n,{\mathsf {e}}^{\mathbf {C}}_i)$ for ${\mathbf {C}} = ({\mathbf {C}}_\tau , q^{\mathbf {C}}_n,{\mathsf {e}}^{\mathbf {C}}_i)_{n\ge 0,i\ge 1}$.

If ${\mathbf {C}}$ is a clone $\tau$-algebra, then ${\mathbf {C}}_0=( C, q^{\mathbf {C}}_n,{\mathsf {e}}^{\mathbf {C}}_i)$ is the pure reduct of ${\mathbf {C}}$.

The class of clone $\tau$-algebras is denoted by $\mathsf {CA}_\tau$ and the class of all clone algebras of any type by $\mathsf {CA}$. $\mathsf {CA}_0$ denotes the class of all pure clone algebras. We also use $\mathsf {CA}_\tau$ as shorthand for the phrase “clone $\tau$-algebra”, and similarly for $\mathsf {CA}$.

We start the study of clone algebras with some simple lemmas. Their easy proofs are left to the reader.

Lemma 3.2

The following identities follow from (C2)–(C6):

• (1) $q_k(q_n(x,{\mathbf {y}}),{\mathbf {z}}) = q_k(x,q_k(y_1,{\mathbf {z}}),\dots ,q_k(y_n,{\mathbf {z}}),z_{n+1},\dots ,z_k)$ ($n<k$).

• (2) $q_k(q_n(x,{\mathbf {y}}),{\mathbf {z}}) = q_n(x,q_k(y_1,{\mathbf {z}}),\dots ,q_k(y_n,{\mathbf {z}}))$ ($n\ge k$).

Lemma 3.3

Let ${\mathbf {C}}$ be a clone $\tau$-algebra and ${\mathbf {b}}= b_1,\dots ,b_n\in C$. Then the map $s_{\mathbf {b}}:C\rightarrow C$, defined by $s_{\mathbf {b}}(a)=q_n(a,{\mathbf {b}})\quad \hbox { for every}\ a\in C$, is an endomorphism of the $\tau$-algebra ${\mathbf {C}}_\tau$, satisfying $s_{\mathbf {b}}({\mathsf {e}}_i)=b_i$ for $1\le i\le n$, and $s_{\mathbf {b}}({\mathsf {e}}_i)={\mathsf {e}}_i$ for $i > n$.

In the remaining part of this section we define the notions of independence and dimension in clone algebras.

Definition 3.4

An element a of a clone algebra ${\mathbf {C}}$ is independent of ${\mathsf {e}}_{n}$ if $q_{n}(a,{\mathsf {e}}_1,\dots ,{\mathsf {e}}_{n-1},{\mathsf {e}}_{n+1})=a$. If a is not independent of ${\mathsf {e}}_{n}$, then we say that a is dependent on ${\mathsf {e}}_{n}$.

Lemma 3.5

Let ${\mathbf {C}}$ be a clone algebra and ${\mathbf {b}}=b_1,\dots , b_{n-1}\in C$. If $k \ge n$ and $a\in C$ is independent of ${\mathsf {e}}_n,{\mathsf {e}}_{n+1}\dots ,{\mathsf {e}}_k$, then

$$\begin{aligned} q_k(a,{\mathbf {b}},b_n,\dots ,b_k)=q_{n-1}(a,{\mathbf {b}}),\quad \hbox { for all}\ b_n,\dots ,b_k\in C. \end{aligned}$$

Let a be an element of a clone algebra ${\mathbf {C}}$. We define

$$\begin{aligned} \Gamma (a)= \{i:\ a \text{ is } \text{ dependent } \text{ on } {\mathsf {e}}_i \};\quad \gamma (a)={\left\{ \begin{array}{ll} \omega &{}{}\text{ if } \Gamma (a) \text{ is } \text{ infinite }\\ 0&{}{}\text{ if } \Gamma (a) \text{ is } \text{ empty }\\ \mathrm {max}\,\Gamma (a) &{}{}\text{ otherwise }\\ \end{array}\right. } \end{aligned}$$

An element $a\in C$ is said to be: (i) k-dimensional if $\gamma (a)=k$; (ii) finite-dimensional if it is k-dimensional for some $k<\omega$; (iii) zero-dimensional if $\gamma (a)=0$. If a is zero-dimensional, then $q_n^{\mathbf {C}}(a,b_1,\dots ,b_n)=a$ for all n and $b_1,\dots ,b_n\in C$.

We denote by $\mathrm {Fi}\,{\mathbf {C}}$ the set of all finite-dimensional elements of a clone algebra ${\mathbf {C}}$. The set $\mathrm {Fi}\,{\mathbf {C}}$ is a subalgebra of ${\mathbf {C}}$, because $\sigma ({\mathbf {b}})$ ($\sigma \in \tau$) and $q_n(a,{\mathbf {b}})$ have dimension $\le k$ if $a,{\mathbf {b}}$ have dimension $\le k$.

We say that ${\mathbf {C}}$ is finite-dimensional if $C=\mathrm {Fi}\,{\mathbf {C}}$.

3.1 Functional clone algebras

The most natural $\mathsf {CA}$s, the ones the axioms are intended to characterise, are algebras of functions, called functional clone algebras. The elements of a functional clone algebra are infinitary functions from $A^{\mathbb {N}}$ into A, for a given set A. In this framework $q_n(\varphi ,\psi _1,\dots ,\psi _n)$ represents the n-ary composition of $\varphi$ with $\psi _1,\dots ,\psi _n$, acting on the first n coordinates, and the nullary operators are the projections.

Let A be a set and ${\mathcal {O}}_A^{({\mathbb {N}})}$ be the set of all infinitary operations from $A^{\mathbb {N}}$ into A. If $r\in A^{\mathbb {N}}$ and $a_1,\dots ,a_n\in A$ then $r[a_1,\dots ,a_n]\in A^{\mathbb {N}}$ is defined by

$$\begin{aligned} r[a_1,\dots ,a_n](i)={\left\{ \begin{array}{ll}a_i&{}\quad \hbox {if}\quad i\le n \hbox {}\\ r_i&{}\quad \text {if}\quad i > n\end{array}\right. } \end{aligned}$$

Moreover, we write r[a/n] for $r[r_1,\dots ,r_{n-1},a]$.

Definition 3.6

Let ${\mathbf {A}}$ be a $\tau$-algebra. The algebra ${{\mathbf {O}}}_{\mathbf {A}}^{({\mathbb {N}})}=({\mathcal {O}}_A^{({\mathbb {N}})},\sigma ^{\mathbb {N}}, q^{\mathbb {N}}_n,{\mathsf {e}}^{\mathbb {N}}_i)$, where, for every $s\in A^{\mathbb {N}}$ and $\varphi ,\psi _1,\dots ,\psi _n\in {\mathcal {O}}_A^{({\mathbb {N}})}$,

• ${\mathsf {e}}_i^{\mathbb {N}}(s)=s_i$;

• $q^{\mathbb {N}}_n(\varphi ,\psi _1,\dots ,\psi _n)(s)=\varphi (s[\psi _1(s),\dots , \psi _n(s)])$;

• $\sigma ^{\mathbb {N}}(\psi _1,\dots ,\psi _n)(s)=\sigma ^{\mathbf {A}}(\psi _1(s),\dots , \psi _n(s))$ for every $\sigma \in \tau$ of arity n;

is called the full functional clone $\tau$-algebra with value domain ${\mathbf {A}}$. A subalgebra of ${{\mathbf {O}}}_{\mathbf {A}}^{({\mathbb {N}})}$ is called a functional clone algebra with value domain ${\mathbf {A}}$.

The universe of a functional clone algebra will be called $\omega$-clone.

From the definition, we easily get:

Lemma 3.7

The algebra ${{\mathbf {O}}}_{\mathbf {A}}^{({\mathbb {N}})}$ is a clone $\tau$-algebra.

The class of functional clone algebras is denoted by $\mathsf {FCA}$. $\mathsf {FCA}_\tau$ is the class of $\mathsf {FCA}$s whose value domain is a $\tau$-algebra.

The algebraic and functional notions of independence are equivalent.

Lemma 3.8

An infinitary operation $\varphi \in {\mathcal {O}}_A^{({\mathbb {N}})}$ is independent of ${\mathsf {e}}_n$ iff, for all $s,u\in A^{\mathbb {N}}$, $u_i=s_i$ for all $i\ne n$ implies $\varphi (u) = \varphi (s)$.

Proof

Let ${\mathbf {e}}={\mathsf {e}}_1,\dots ,{\mathsf {e}}_{n-1}$ and $s,u\in A^{\mathbb {N}}$ such that $u_i=s_i$ for all $i\ne n$.

($\Rightarrow$) If $\varphi =q^{\mathbb {N}}_n(\varphi ,{\mathbf {e}},{\mathsf {e}}_{n+1})$ then $\varphi (u)= q^{\mathbb {N}}_n(\varphi ,{\mathbf {e}},{\mathsf {e}}_{n+1})(u)= \varphi (u[u_{n+1}/n])= \varphi (s[s_{n+1}/n])=q^{\mathbb {N}}_n(\varphi ,{\mathbf {e}},{\mathsf {e}}_{n+1})(s)=\varphi (s)$, because $u_i=s_i$ for all $i\ne n$.

($\Leftarrow$) $q^{\mathbb {N}}_n(\varphi ,{\mathbf {e}},{\mathsf {e}}_{n+1})(s)=\varphi (s[s_{n+1}/n]) = \varphi (s)$ for every s. $\square$

From Lemma 3.8 it follows that there exist zero-dimensional infinitary operations that are not constant. For example, if $2=\{0,1\}$, then the function $\psi :2^{\mathbb {N}}\rightarrow 2$, defined by $\psi (s)=0$ if and only if $|\{i:s_i= 0\}|$ is finite, is zero-dimensional.

3.2 Clones of operations and block algebras

In this section we introduce an equivalence relation $\approx _{{\mathcal {O}}_A}$ over the set ${\mathcal {O}}_A$ of operations of a given set A: two operations are equivalent if the one having greater arity extends the other one by a bunch of dummy arguments. Each block (equivalence class) of $\approx _{{\mathcal {O}}_A}$ determines a unique infinitary operation that we call the top extension of the block. The set of all these top extensions is an $\omega$-clone and it is exactly the functional clone algebra associated with ${\mathcal {O}}_A$, called the full block algebra on A. We prove that the lattice of clones on a set A is isomorphic to the lattice of subalgebras of the full block algebra on A.

Definition 3.9

[15, Section 2]. The top extension $f^\top \in {\mathcal {O}}^{({\mathbb {N}})}_A$ of an operation $f\in {\mathcal {O}}_A$ of arity n is defined as follows:

$$\begin{aligned} f^\top (s)=f(s_1,\dots ,s_n),\quad \hbox { for all}\ s\in A^{\mathbb {N}}. \end{aligned}$$

We say that $f,g\in {\mathcal {O}}_A$ are similar, and we write $f\approx _{{\mathcal {O}}_A} g$, if $f^\top =g^\top$.

We denote by ${\mathcal {B}}_A$ the set of all blocks (i.e., equivalence classes) of the relation $\approx _{{\mathcal {O}}_A}$. If $f\in {\mathcal {O}}_A$ then $\langle f\rangle$ denotes the unique block containing f.

If B is a block, then $B \cap {\mathcal {O}}^{(n)}_A$ is either empty or a singleton. If $B \cap {\mathcal {O}}^{(n)}_A\ne \emptyset$, then $B \cap {\mathcal {O}}^{(k)}_A\ne \emptyset$ for every $k\ge n$.

Definition 3.10

We say that a block B has arity k and generator f if $f\in B$ has arity k and every other $g\in B$ has arity greater than k.

Note that, if $f:A^k\rightarrow A$ is the generator of a block B, then there exist $a_1,\dots ,a_{k-1},b,c\in A$ such that $f(a_1,\dots ,a_{k-1},b)\ne f(a_1,\dots ,a_{k-1},c)$.

If B is a block of arity k, then we denote by $B^{(n)}$ ($n\ge k$) the unique function in $B\cap {\mathcal {O}}^{(n)}_A$. Therefore, $B = \{B^{(n)} : n\ge k\}$ and $B^{(k)}$ is the generator of the block B.

Example 3.11

Let $\mathrm {Clo}{\mathbf {A}}$ be the clone of the term operations of a $\tau$-algebra ${\mathbf {A}}$. Then, $B\subseteq \mathrm {Clo}{\mathbf {A}}$ is a block if and only if there exists a $\tau$-term t such that B is equal to the set $T_t^{\mathbf {A}}$ of all term operations defined by t on ${\mathbf {A}}$.

The top extension $B^\top$ of a block B is defined as $B^\top =f^\top$ for some (and then all) $f\in B$. Then the map $B\mapsto B^\top$ embeds the set ${\mathcal {B}}_A$ of blocks into ${\mathcal {O}}^{({\mathbb {N}})}_A$. Its image $\{B^\top : B\in {\mathcal {B}}_A\}$ will be denoted by ${\mathcal {B}}_A^\top$.

It is not difficult to show that a block $B\in {\mathcal {B}}_A$ has arity k iff $B^\top$ has dimension k in the full $\mathsf {FCA}$ ${\mathbf {O}}^{({\mathbb {N}})}_A$.

Lemma 3.12

${\mathcal {B}}_A^\top$ is a finite-dimensional subalgebra of the full $\mathsf {FCA}$ ${\mathbf {O}}^{({\mathbb {N}})}_A$.

Proof

First ${\mathsf {e}}_i^{\mathbb {N}} = P_i^\top$, where $P_i$ is the block generated by $p^{(i)}_i$. If $B,G_1,\dots ,G_n$ are blocks and $k\ge n$ is greater than the arities of $B,G_1,\dots ,G_n$, then $q_n^{\mathbb {N}}(B^\top ,G_1^\top ,\dots ,G_n^\top )=(B^{(k)}(G_1^{(k)},\dots , G_n^{(k)},P_{n+1}^{(k)},\dots ,P_{k}^{(k)})_k)^\top$. $\square$

The $\mathsf {FCA}$ ${\mathcal {B}}_A^\top$ will be called the full block algebra on A. A subalgebra of the full block algebra ${\mathcal {B}}_A^\top$ is called a block algebra on A. A block algebra on a $\tau$-algebra ${\mathbf {A}}$ is a block algebra on A containing $(\sigma ^{\mathbf {A}})^\top$ for every $\sigma \in \tau$.

Lemma 3.13

Every clone is a union of blocks.

Proof

Let F be a clone on A, $f\in F$ be an n-ary operation and $g:A^k\rightarrow A$ be the generator of the block $\langle f\rangle$. Then $g=f(p^{(k)}_1,\dots ,p^{(k)}_k, p^{(k)}_k,\dots ,p^{(k)}_k)_k\in F$ and $\langle f\rangle ^{(m)}=g(p^{(m)}_1,\dots ,p^{(m)}_k)_m\in F$ for all $m\ge k$. $\square$

If $F\subseteq {\mathcal {O}}_A$, then we define $F^\top =\{f^\top : f\in F\}$.

Proposition 3.14

Let $F\subseteq {\mathcal {O}}_A$. Then the following conditions are equivalent:

• (1) F is a clone on A;

• (2) $F^\top$ is the universe of a block algebra on A.

The map $F\mapsto F^\top$ determines an isomorphism from the lattice of all clones on A onto the lattice of all subalgebras of the full block algebra ${\mathcal {B}}_A^\top$.

Proof

(1) $\Rightarrow$ (2) First we have $(p^n_i)^\top ={\mathsf {e}}_i^{\mathbb {N}}$. Let $f,g_1,\dots ,g_n\in F$. We now check that $q_n^{\mathbb {N}}(f^\top ,g_1^\top ,\dots ,g_n^\top )\in F^\top$. Let $k\ge n$ be greater than the arities of $f,g_1,\dots ,g_n$. Then $q_n^{\mathbb {N}}(f^\top ,g_1^\top ,\dots ,g_n^\top )$ is the top expansion of the operation $h=\langle f\rangle ^{(k)}(\langle g_1\rangle ^{(k)},\dots , \langle g_n\rangle ^{(k)},P^{(k)}_{n+1},\dots ,P_k^{(k)})_k$. We have that $h\in F$, because F contains the blocks $\langle f\rangle$, $\langle g_i\rangle$ and $P_i$.

(2) $\Rightarrow$ (1) If $f\in F^{(n)}$ and $g_1,\dots ,g_n\in F^{(k)}$, then $f( g_1,\dots , g_n)_k^\top = q_n^{\mathbb {N}}(f^\top ,g_1^\top ,\dots ,g_n^\top )\in F^\top .$

The remaining part of the proposition is an easy consequence of the equivalence between (1) and (2). $\square$

3.3 The representation of finite-dimensional clone algebras

In this section we show that every finite-dimensional clone algebra is isomorphic to a block algebra. This result is not trivial, because, for example, there exist finite dimensional $\mathsf {FCA}$s that contain zero-dimensional infinitary operations that are not top extensions of any finitary operation.

We start the section by defining the set of representable operations of a clone algebra.

Definition 3.15

Let ${\mathbf {C}}$ be a clone algebra and $f:C^k\rightarrow C$ be a function. We say that f is ${\mathbf {C}}$-representable if $f({\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_k^{\mathbf {C}})$ has dimension $\le k$ and

$$\begin{aligned} f({\mathbf {a}})=q_k^{\mathbf {C}}(f({\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_k^{\mathbf {C}}),{\mathbf {a}}),\quad \hbox { for all}\ {\mathbf {a}}\in C^k. \end{aligned}$$

We denote by $R_{\mathbf {C}}$ the set of all ${\mathbf {C}}$-representable functions and by $R_{\mathbf {C}}^{(k)}$ the set of all ${\mathbf {C}}$-representable functions of arity k.

In the following lemma it is shown that a function is ${\mathbf {C}}$-representable if and only if it satisfies an analogue of identity (C7) in Definition 3.1.

Lemma 3.16

Let ${\mathbf {C}}$ be a clone $\tau$-algebra and $f:C^k\rightarrow C$ be a function. Then the following conditions are equivalent:

• (1) f is ${\mathbf {C}}$-representable;

• (2) $q_n(f({\mathbf {a}}),{\mathbf {c}}) = f(q_n(a_1,{\mathbf {c}}),\dots , q_n(a_k,{\mathbf {c}}))$ for every $n\ge 0$, ${\mathbf {a}}\in C^k$ and ${\mathbf {c}}\in C^n$.

In particular, by (C7) every basic operation $\sigma ^{\mathbf {C}}$ ($\sigma \in \tau$) is ${\mathbf {C}}$-representable.

Proof

By Lemma 3.2 applied to $q_n(f({\mathbf {a}}),{\mathbf {c}})= q_n(q_k(f({\mathsf {e}}_1,\dots ,{\mathsf {e}}_k),{\mathbf {a}}),{\mathbf {c}}$). $\square$

Let ${\mathbf {C}}$ be a clone algebra. For every $a\in C$ of finite dimension, we consider the set $R(a)=\bigcup _{n\in \omega } \{f\in R_{\mathbf {C}}^{(n)}: a=f({\mathsf {e}}_1,\dots ,{\mathsf {e}}_n)\}$ of the ${\mathbf {C}}$-representable functions determined by a.

Proposition 3.17

Let ${\mathbf {C}}$ be a clone algebra and a, b be finite-dimensional elements of C. Then the following conditions hold:

• (1) For every $f\in R_{\mathbf {C}}^{(n)}$ and $g\in R_{\mathbf {C}}^{(k)}$,

  $$\begin{aligned} f\approx _{{\mathcal {O}}_C} g\ \text {iff}\ f({\mathsf {e}}_1,\dots ,{\mathsf {e}}_n)=g({\mathsf {e}}_1,\dots ,{\mathsf {e}}_k). \end{aligned}$$

• (2) R(a) is a block.

• (3) $R(a)\cap R(b) \ne \emptyset \Rightarrow a=b$.

• (4) $R_{\mathbf {C}}=\bigcup _{a\in \mathrm {Fi}\,C} R(a)$ is a clone on ${\mathbf {C}}$.

• (5) The block R(a) has arity k iff a has dimension k in ${\mathbf {C}}$.

Proof

(1) ($\Rightarrow$) If $n\le k$, then $f({\mathsf {e}}_1,\dots ,{\mathsf {e}}_n)=g({\mathsf {e}}_1,\dots ,{\mathsf {e}}_n,{\mathbf {b}})$ for every ${\mathbf {b}}$. In particular for ${\mathbf {b}}={\mathsf {e}}_{n+1},\dots ,{\mathsf {e}}_k$ we get the conclusion. ($\Leftarrow$) It is trivial by the hypothesis.

(2) By (1).

(3) If $f\in R(a)\cap R(b)$ has arity n, then $a=f({\mathsf {e}}_1,\dots ,{\mathsf {e}}_n)=b$.

(4) $p^{(n)}_i$ is ${\mathbf {C}}$-representable: $a_i=p^{(n)}_i({\mathbf {a}})=q_n(p^{(n)}_i({\mathsf {e}}_1,\dots ,{\mathsf {e}}_n),{\mathbf {a}})$. If f of arity n and $g_1,\dots ,g_n$ of arity k are ${\mathbf {C}}$-representable, then the function $h=f(g_1,\dots ,g_n)_k$ is also ${\mathbf {C}}$-representable. Let ${\mathbf {e}}={\mathsf {e}}_1,\dots ,{\mathsf {e}}_k$ and ${\mathbf {a}}=a_1,\dots ,a_k$. Then we have: $q_k(h({\mathbf {e}}),{\mathbf {a}}) = q_k(f(g_1({\mathbf {e}}),\dots ,g_n({\mathbf {e}})),{\mathbf {a}})=_{\mathrm {Lem.}~3.16}f(q_k(g_1({\mathbf {e}}),{\mathbf {a}}),\dots ,q_k(g_n({\mathbf {e}}),{\mathbf {a}}))=f(g_1({\mathbf {a}}),\dots ,g_n({\mathbf {a}})) = h({\mathbf {a}})$.

(5) If the block R(a) has arity k, then by Definition 3.15a has dimension $\le k$. We have to show that a has indeed dimension k. If $f\in R(a)$ is the generator of arity k, then $a=f({\mathsf {e}}_1,\dots ,{\mathsf {e}}_k)$. Then, a is independent of ${\mathsf {e}}_k$ iff, for every c and ${\mathbf {b}}=b_1,\dots ,b_{k-1}\in C$, $f(\mathbf {b },c)=q_{k}(a,{\mathbf {b}},c){=_{{Lem.~3.5}}}\ q_{k-1}(a,{\mathbf {b}})$ iff, for every c, d and ${\mathbf {b}}=b_1,\dots ,b_{k-1}\in C$, $f({\mathbf {b}},c)=f({\mathbf {b}},d)$ iff f is not a generator. Contradiction.$\square$

Theorem 3.18

Let ${\mathbf {C}}$ be a finite-dimensional clone $\tau$-algebra. The function F mapping $a\in C \mapsto \ R(a)^\top$ is an isomorphism from ${\mathbf {C}}$ onto the block algebra $(R_{\mathbf {C}})^\top$ on ${\mathbf {C}}$.

Proof

F is trivially bijective and ${\mathsf {e}}_i^{\mathbf {C}}\mapsto R({\mathsf {e}}_i^{\mathbf {C}})^\top ={\mathsf {e}}_i^{\mathbb {N}}$. The map F preserves the operators $q_n$: $R(q_n^{\mathbf {C}}(a,{\mathbf {b}}))^\top = q_n^{\mathbb {N}}(R(a)^\top ,R(b_1)^\top ,\dots ,R(b_n)^\top )$. Let $k\ge n$ be greater than the dimensions of $a,b_1,\dots ,b_n$ and $q_n^{\mathbf {C}}(a,{\mathbf {b}})$. Let $s\in C^{\mathbb {N}}$, ${\mathbf {s}}=s_1,\dots ,s_k$, $A=R(a)$ and $B_i=R(b_i)$.

$$\begin{aligned} q_n^{\mathbb {N}}(A^\top ,B_1^\top ,\dots ,B_n^\top )(s)&= A^\top (s[B_1^\top (s),\dots ,B_n^\top (s)])\\&= A^{(k)}(B_1^\top (s),\dots ,B_n^\top (s),s_{n+1},\dots ,s_k)\\&= A^{(k)}(B_1^{(k)}({\mathbf {s}}),\dots ,B_n^{(k)}({\mathbf {s}}),s_{n+1},\dots ,s_k)\\&= q_k^{\mathbf {C}}(a,q_k^{\mathbf {C}}(b_1,{\mathbf {s}}),\dots ,q_k^{\mathbf {C}}(b_n,{\mathbf {s}}),s_{n+1},\dots ,s_k)\\&= q_k^{\mathbf {C}} (q_n^{\mathbf {C}} (a,{\mathbf {b}}),{\mathbf {s}})\\&= R(q_n^{\mathbf {C}}(a,{\mathbf {b}}))^\top (s) \end{aligned}$$

$(R_{\mathbf {C}})^\top$ is closed under $\sigma ^{\mathbb {N}}$ ($\sigma \in \tau$) because $\sigma ^{\mathbf {C}}$ is ${\mathbf {C}}$-representable. $\square$

We denote by $\mathsf {BLK}$ the class of all block algebras and by $\mathsf {FiCA}$ the class of all finite-dimensional clone algebras.

Theorem 3.19

$\mathsf {FiCA}_\tau = {\mathbb {I}}\, \mathsf {BLK}_\tau$.

Proof

By Theorem 3.18$\mathsf {FiCA}_\tau \subseteq {\mathbb {I}}\, \mathsf {BLK}_\tau$. The inequality $\mathsf {BLK}_\tau \subseteq \mathsf {FiCA}_\tau$ is trivial, because every block algebra is finite-dimensional. $\square$

Theorem 3.18 allows us to compare abstract clones (defined in Section 2.2.1) and clone algebras.

Theorem 3.20

The category of abstract clones and many-sorted homomorphisms is equivalent to the category of finite-dimensional pure clone algebras and (one-sorted) homomorphisms.

Proof

An abstract clone ${\mathcal {A}}$ has a concrete representation as an isomorphic clone $C({\mathcal {A}})$ of finitary operations (see [6, Section 3]). The top expansion $C({\mathcal {A}})^\top$ of this clone is a block algebra that is finite-dimensional by construction. For the converse, by Theorem 3.18 a finite-dimensional pure clone algebra ${\mathbf {C}}$ is isomorphic to a block algebra that is the top expansion of a suitable clone of operations. Moreover, many-sorted homomorphisms of abstract clones easily correspond to homomorphisms of clone algebras. $\square$

4 The general representation theorem

This section is devoted to the proof of the main representation theorem. Firstly we introduce the class $\mathsf {RCA}$ of point-relativized functional clone algebras, which is instrumental in the proof of the representation theorem. The following diagram provides the outline of the proof that $\mathsf {CA}={\mathbb {I}}\,\mathsf {FCA}$:

$$\begin{aligned} \mathsf {CA}&= {\mathbb {I}}\,\mathsf {RCA} \quad&\text {Lemma}~4.5\\&\subseteq {\mathbb {I}}\,{\mathbb {S}}\,{\mathbb {P}}_U\, \mathsf {FCA} \quad&\text {Lemma}~4.8, \text {Lemma}~4.6 \\&\subseteq {\mathbb {I}}\,{\mathbb {S}}\,{\mathbb {P}}\, \mathsf {FCA} \quad&\text {Lemma}~4.10 \\&\subseteq {\mathbb {I}}\, \mathsf {FCA}\quad&\text {Lemma}~4.9\\&\subseteq \mathsf {CA}\quad&\text {Lemma}~3.7 \end{aligned}$$

In other words, the proof is structured as follows:

• Each clone algebra is isomorphic to a point relativized functional clone algebra.

• Each point relativized functional clone algebra embeds into an ultrapower of a functional clone algebra.

• Each ultrapower of a functional clone algebra is isomorphic to a subdirect product of a family of functional clone algebras.

• Functional clone algebras are closed under subalgebras and direct products.

Moreover, we prove that the variety of clone algebras is generated by its finite-dimensional members (or by the class of block algebras):

$$\begin{aligned} \mathsf {CA} = {\mathbb {H}}\,{\mathbb {S}}\,{\mathbb {P}} (\mathsf {FiCA})= {\mathbb {H}}\,{\mathbb {S}}\,{\mathbb {P}} (\mathsf {BLK}). \end{aligned}$$

Then, the variety of clone algebras is the algebraic counterpart of $\omega$-clones, the class of block algebras is the algebraic counterpart of clones, and the $\omega$-clones are algebraically generated by clones through direct products, subalgebras and homomorphic images.

4.1 Point-relativized functional clone algebras

Let A be a set. We define an equivalence relation on $A^{\mathbb {N}}$ as follows: $r\equiv s\ \text {iff}\ |\{i: r_i\ne s_i\}|<\omega$. Let $A^{\mathbb {N}}_r=\{s\in A^{\mathbb {N}} : s\equiv r\}$ be the equivalence class of r and ${\mathcal {O}}_{A,r}^{({\mathbb {N}})}$ be the set of all functions from $A^{\mathbb {N}}_r$ to A.

Definition 4.1

Let ${\mathbf {A}}$ be a $\tau$-algebra and $r\in A^{\mathbb {N}}$. The algebra ${\mathbf {O}}_{{\mathbf {A}},r}^{({\mathbb {N}})}=({\mathcal {O}}_{A,r}^{({\mathbb {N}})},\sigma ^r, q^r_{n},{\mathsf {e}}_{i}^r)$, where, for every $s\in A^{\mathbb {N}}_r$ and $\varphi ,\psi _1,\dots ,\psi _n\in {\mathcal {O}}_{A,r}^{({\mathbb {N}})}$,

• ${\mathsf {e}}_i^r(s)=s_i$;

• $q^r_n(\varphi ,\psi _1,\dots ,\psi _n)(s)=\varphi (s[\psi _1(s),\dots , \psi _n(s)])$;

• $\sigma ^r(\psi _1,\dots ,\psi _n)(s)=\sigma ^{\mathbf {A}}(\psi _1(s),\dots , \psi _n(s))$ for every $\sigma \in \tau$ of arity n,

is called the full point-relativized functional clone algebra with value domain ${\mathbf {A}}$ and thread r.

Notice that, if $r\equiv s$, then ${\mathbf {O}}_{A,r}^{({\mathbb {N}})}={\mathbf {O}}_{A,s}^{({\mathbb {N}})}$.

Lemma 4.2

The algebra ${\mathbf {O}}_{{\mathbf {A}},r}^{({\mathbb {N}})}$ is a clone $\tau$-algebra.

A subalgebra of ${\mathbf {O}}_{{\mathbf {A}},r}^{({\mathbb {N}})}$ is called a point-relativized functional clone algebra with value domain ${\mathbf {A}}$ and thread r. The class of point-relativized functional clone algebras is denoted by $\mathsf {RCA}$. $\mathsf {RCA}_\tau$ is the class of $\mathsf {RCA}$s whose value domain is a $\tau$-algebra.

An analogue of Lemma 3.8, relating the algebraic and functional notions of independence, holds for $\mathsf {RCA}$s.

If $B\in {\mathcal {B}}_A$ is a block, then the r-relativized top extension $B^\top _r:A^{\mathbb {N}}_r \rightarrow A$ of B is defined by $B^\top _r(s)=B^{(n)}(s_1,\dots ,s_n)$, for every $s\in A^{\mathbb {N}}_r$ and n greater than the arity of B.

The following lemma, which is true in ${\mathcal {O}}_{ A,r}^{({\mathbb {N}})}$ and false in ${\mathcal {O}}_{ A}^{({\mathbb {N}})}$, explains the difference between $\mathsf {RCA}$s and $\mathsf {FCA}$s.

Lemma 4.3

Let $\varphi \in {\mathcal {O}}_{ A,r}^{({\mathbb {N}})}$. Then the following conditions are equivalent:

• (1) $\varphi =B^\top _r$ for some block B;

• (2) $\varphi$ is finite-dimensional in the clone algebra ${\mathbf {O}}_{ A,r}^{({\mathbb {N}})}$.

Proof

(1) $\Rightarrow$ (2) If B has arity k then, for every $s\in A^{\mathbb {N}}_r$, we have $\varphi (s)= B^\top _r(s)=B^{(k)}(s_1,\dots ,s_k)=B^\top _r(r[s_1,\dots ,s_k]) =\varphi (r[s_1,\dots ,s_k])$. Then $\varphi$ is independent of ${\mathsf {e}}_n$ for every $n> k$.

(2) $\Rightarrow$ (1) If n is the dimension of $\varphi$, then, for every $s\in A^{\mathbb {N}}_r$, we have that $\varphi (s)= \varphi (r[s_1,\dots ,s_n])$. If $f:A^n\rightarrow A$ is defined by $f(a_1,\dots ,a_n)=\varphi (r[a_1,\dots ,a_n])$, then $\varphi =f^\top _r$. $\square$

The following counterexample shows that Lemma 4.3 is false in ${\mathcal {O}}_A^{({\mathbb {N}})}$. Let $\psi :A^{\mathbb {N}}\rightarrow A$ be a zero-dimensional element of ${\mathcal {O}}_A^{({\mathbb {N}})}$ such that $\psi (s)\ne \psi (u)$ for some $s,u\in A^{\mathbb {N}}$. Then $\psi \ne f^\top$ for every operation $f \in {\mathcal {O}}_A$.

4.2 The main theorem

We recall that $\mathsf {CA}$ is the class of all clone algebras, $\mathsf {RCA}$ is the class of all point-relativized functional clone algebras, $\mathsf {FCA}$ is the class of all functional clone algebras, $\mathsf {FiCA}$ is the class of all finite-dimensional clone algebras, and $\mathsf {BLK}$ is the class of all block algebras.

Theorem 4.4

$\mathsf {CA} = {\mathbb {I}}\, \mathsf {RCA}={\mathbb {I}}\, \mathsf {FCA}=\mathbb {HSP}(\mathsf {FiCA})=\mathbb {HSP}(\mathsf {BLK})$.

The proof of the main theorem is divided into lemmas.

Lemma 4.5

$\mathsf {CA}_\tau = {\mathbb {I}}\, \mathsf {RCA}_\tau$.

Proof

Let ${\mathbf {C}}=({\mathbf {C}}_\tau ,q^{\mathbf {C}}_n,{\mathsf {e}}^{\mathbf {C}}_i)$ be a clone $\tau$-algebra. Let ${\mathbf {O}}_{ {\mathbf {C}}_\tau ,\epsilon }^{({\mathbb {N}})}$ be the full $\mathsf {RCA}$ with value domain ${\mathbf {C}}_\tau$ and thread $\epsilon$, where $\epsilon _i={\mathsf {e}}^{\mathbf {C}}_i$ for every i. We define a map $F:C\rightarrow {\mathcal {O}}_{C,\epsilon }^{({\mathbb {N}})}$ as follows. Let $s\in C^{\mathbb {N}}_\epsilon$ such that $s= \epsilon [s_1,\dots ,s_k]$ and $s_k\ne {\mathsf {e}}_k^{\mathbf {C}}$. Then we define

$$\begin{aligned} F(c)(s)=q_k^{\mathbf {C}}(c, s_1,\dots ,s_k). \end{aligned}$$

Notice that, for every $n\ge k$,

$$\begin{aligned} F(c)(s)=_{(C5)}q_n^{\mathbf {C}}(c, s_1,\dots ,s_k,{\mathsf {e}}_{k+1}^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}}). \end{aligned}$$

(4.1)

F is injective because $F(c)(\epsilon )=q_0^{\mathbf {C}}(c)=c$ for every $c\in C$. We prove that F embeds ${\mathbf {C}}$ into ${\mathbf {O}}_{{\mathbf {C}}_\tau ,\epsilon }^{({\mathbb {N}})}$. Let ${\mathbf {s}}=s_1,\dots ,s_k$. If $n\ge k$ then we have:

$$\begin{aligned} F(q^{\mathbf {C}}_n(b,{\mathbf {c}}))(s)&= q_k^{\mathbf {C}}(q^{\mathbf {C}}_n(b,{\mathbf {c}}), {\mathbf {s}}) \quad&\hbox { Def.}\ F\\&= q_n^{\mathbf {C}}(b,q_k^{\mathbf {C}}(c_1,{\mathbf {s}}),\dots ,q_k^{\mathbf {C}}(c_n,{\mathbf {s}}))\quad&\text {by Lemma}~3.2 \\&= q_n^{\mathbf {C}}(b,F(c_1)(s),\dots ,F(c_n)(s))\quad&\hbox { Def.}\ F\\&= F(b)(\epsilon [F(c_1)(s),\dots ,F(c_n)(s)]) \quad&\text {Def. } F\text { and }(4.1)\\&= F(b)(s[F(c_1)(s),\dots ,F(c_n)(s)]) \quad&\hbox { by}\ n\ge k\\&= q^\epsilon _n(F(b),F(c_1),\dots ,F(c_n))(s).\quad&\end{aligned}$$

The proof in the case $n< k$ is similar. It is easy to show that F preserves ${\mathsf {e}}_i^{\mathbf {C}}$ and the operators $\sigma ^{\mathbf {C}}$ ($\sigma \in \tau$). $\square$

By the n-reduct of a clone $\tau$-algebra ${\mathbf {C}}$ we mean the algebra

$$\begin{aligned} \mathrm {Rd}_n {\mathbf {C}}:=({\mathbf {C}}_\tau ,q^{\mathbf {C}}_0,\dots ,q^{\mathbf {C}}_n,{\mathsf {e}}^{\mathbf {C}}_1,\dots ,{\mathsf {e}}^{\mathbf {C}}_n). \end{aligned}$$

Lemma 4.6

Let ${\mathbf {A}}$ be a $\tau$-algebra and ${\mathbf {D}}$ be a $\mathsf {RCA}_\tau$ with value domain ${\mathbf {A}}$ and thread r. For every $n\ge 0$ the map $F_{r,n}: D \rightarrow {\mathcal {B}}_{A}^\top$, defined by

$$\begin{aligned} F_{r,n}(\varphi )(s)=\varphi (r[s_1,\dots ,s_n])\qquad \text{ for } \text{ every } \varphi \in D \text{ and } s\in A^{\mathbb {N}}, \end{aligned}$$

is a homomorphism of $\mathrm {Rd}_n {\mathbf {D}}$ into the n-reduct $\mathrm {Rd}_n {\mathcal {B}}_{{\mathbf {A}}}^\top$ of the full block algebra ${\mathcal {B}}_{{\mathbf {A}}}^\top$.

Proof

Let $F= F_{r,n}$ in this proof. Let $k\le n$, $s\in A^{\mathbb {N}}$ and $u=r[s_1,\dots ,s_n]$.

$$\begin{aligned} F(q^r_k(\varphi ,\psi _1,\dots ,\psi _k))(s)&= q^r_k(\varphi ,\psi _1,\dots ,\psi _k)(u)\\&= \varphi (u[\psi _1(u),\dots ,\psi _k(u)]) \\&= \varphi (r[\psi _1(u),\dots ,\psi _k(u),s_{k+1},\dots ,s_n])\\&=F(\varphi )(s[\psi _1(u),\dots ,\psi _k(u),s_{k+1},\dots ,s_n])\\&=F(\varphi )(s[F(\psi _1)(s),\dots ,F(\psi _k)(s),s_{k+1},\dots ,s_n]) \\&=F(\varphi )(s[F(\psi _1)(s),\dots ,F(\psi _k)(s)]) \\&= q_k^{\mathbb {N}} (F(\varphi ),F(\psi _1),\dots ,F(\psi _k))(s) \end{aligned}$$

The proof in the case $\sigma \in \tau$ is similar. Notice that the image of the homomorphism F is within the full block algebra ${\mathcal {B}}_{{\mathbf {A}}}^\top$, because $F(\varphi )=f^\top$, where $f(a_1,\dots ,a_n)= \varphi (r[a_1,\dots ,a_n])$ for every $a_1,\dots ,a_n\in A$. $\square$

Lemma 4.7

$\mathsf {CA}_\tau =\mathbb {HSP}(\mathsf {FiCA}_\tau )$.

Proof

Let $t(v_1,\dots ,v_k)=u(v_1,\dots ,v_k)$ be an identity (in the language of clone $\tau$-algebras) satisfied by every finite-dimensional clone $\tau$-algebra. We now show that the identity $t=u$ holds in every clone $\tau$-algebra. Since $\mathsf {CA}_\tau ={\mathbb {I}}\,\mathsf {RCA}_\tau$, it is sufficient to prove that the identity $t=u$ holds in the full $\mathsf {RCA}_\tau$ ${\mathbf {O}}_{ {\mathbf {A}},r}^{({\mathbb {N}})}$ with value domain ${\mathbf {A}}$ and thread r. If $t^r$ and $u^r$ are the interpretations of t and u in ${\mathbf {O}}_{ {\mathbf {A}},r}^{({\mathbb {N}})}$, we have to show that $t^r(\varphi _1,\dots , \varphi _k)(s)=u^r(\varphi _1,\dots , \varphi _k)(s)$ for all $\varphi _1,\dots ,\varphi _k\in {\mathcal {O}}_{ A,r}^{({\mathbb {N}})}$ and all $s \in A^{\mathbb {N}}_r$. Let $n>k$ be such that $q_m$ and ${\mathsf {e}}_m$ do not occur in t, u for every $m> n$. Since ${\mathbf {O}}_{ {\mathbf {A}},r}^{({\mathbb {N}})}$ satisfies the equation $t=u$ iff the n-reduct $\mathrm {Rd}_n\, {\mathbf {O}}_{ {\mathbf {A}},r}^{({\mathbb {N}})}$ satisfies it, then we can use the function $F_{s,n}$ defined in Lemma 4.6. Let $t^{\mathbb {N}}$ and $u^{\mathbb {N}}$ be the interpretations of t and u in the full block algebra ${\mathcal {B}}_{{\mathbf {A}}}^\top$. Recall that ${\mathcal {B}}_{{\mathbf {A}}}^\top$ is finite-dimensional.

$$\begin{aligned} t^r(\varphi _1,\dots , \varphi _k)(s)&= t^r(\varphi _1,\dots , \varphi _k)(s[s_1,\dots ,s_n]) \quad&\\&= F_{s,n}(t^r(\varphi _1,\dots , \varphi _k))(s) \quad&\hbox { Def.}\ F_{s,n} \\&= t^{\mathbb {N}}(F_{s,n}(\varphi _1),\dots , F_{s,n}(\varphi _k))(s)\quad&F_{s,n}\text { is a homomorphism} \\&= u^{\mathbb {N}}(F_{s,n}(\varphi _1),\dots , F_{s,n}(\varphi _k))(s)\quad&{\mathcal {B}}_{{\mathbf {A}}}^\top \text {is finite-dimensional} \\&= F_{s,n}(u^r(\varphi _1,\dots , \varphi _k))(s)\quad&\\&= u^r(\varphi _1,\dots , \varphi _k)(s).\quad&\end{aligned}$$

$\square$

By Theorem 3.19 we also derive $\mathsf {CA}_\tau =\mathbb {HSP}(\mathsf {BLK}_\tau )$.

Lemma 4.8

Every $\mathsf {RCA}_\tau$ can be embedded into an ultrapower of a $\mathsf {FCA}_\tau$.

Proof

Let U be a nonprincipal ultrafilter on $\omega$ that contains the set $\{j: j\ge i\}$ for every $i\in \omega$. U does not contain finite sets. Let ${\mathbf {O}}_{ {\mathbf {A}},r}^{({\mathbb {N}})}$ be the full $\mathsf {RCA}_\tau$ with value domain ${\mathbf {A}}$ and thread r. Let $F_{r, n}$ be the function defined in Lemma 4.6. We prove that the map h, defined by $h(\varphi )=\langle F_{r, n}(\varphi ): n\in \omega \rangle /U$, where $\varphi \in {\mathcal {O}}_{A,r}^{({\mathbb {N}})}$, is an embedding of the full $\mathsf {RCA}$ ${\mathbf {O}}_{ {\mathbf {A}},r}^{({\mathbb {N}})}$ into the ultrapower $({\mathbf {O}}_{ {\mathbf {A}}}^{({\mathbb {N}})})^\omega /U$ of the full $\mathsf {FCA}$ ${\mathbf {O}}_{ {\mathbf {A}}}^{({\mathbb {N}})}$ with value domain ${\mathbf {A}}$.

We prove that h is injective. If $h(\varphi )=h(\psi )$ then $\{ n: F_{r, n}(\varphi )=F_{r, n}(\psi )\}\in U$. Then, for every $i\in \omega$, by the hypothesis on U we have:

$$\begin{aligned} \{j: j\ge i\}\cap \{ n: F_{r, n}(\varphi )=F_{r, n}(\psi )\}\ \text {is an infinite set}. \end{aligned}$$

Then there exists an increasing sequence $k_1< k_2<\dots< k_j <\dots$ of natural numbers such that $k_j\in \{j: j\ge i\}\cap \{ n: F_{r, n}(\varphi )=F_{r, n}(\psi )\}$ and $k_j> k_{j-1}$. Let $s=r[s_1,\dots ,s_m]\in A^{\mathbb {N}}_r$. Let $k_n>m$. Then $s=r[s_1,\dots ,s_m] = r[s_1,\dots ,s_m,r_{m+1},\dots ,r_{k_n}]$ and we have:

$$\begin{aligned} \varphi (s)&= \varphi (r[s_1,\dots ,s_m,r_{m+1},\dots ,r_{k_n}]) \quad&\\&= F_{r, k_n}(\varphi )(s) \quad&\hbox { Def.}\ F_{r, k_n}\\&= F_{r, k_n}(\psi )(s)\quad&\hbox { }\ k_n\in \{ n: F_{r, n}(\varphi )=F_{r, n}(\psi )\}\\&= \psi (r[s_1,\dots ,s_m,r_{m+1},\dots ,r_{k_n}])\quad&\\&= \psi (s).\quad&\end{aligned}$$

By the arbitrariness of s it follows that $\varphi =\psi$. We now prove that h is a homomorphism. Let ${\bar{\psi }} =\psi _0,\psi _1\dots ,\psi _k$ and $F_{r, n}({\bar{\psi }})=F_{r, n}(\psi _0),\dots ,F_{r, n}(\psi _k)$. Then, $h(q^r_k({\bar{\psi }})) = \langle F_{r, n}(q^r_k({\bar{\psi }})): n\in \omega \rangle /U = \langle q^{\mathbb {N}}_k(F_{r, n}({\bar{\psi }})): n\in \omega \rangle /U$, because by Lemma 4.6$\{n:F_{r, n}(q^r_k({\bar{\psi }}))=q^{\mathbb {N}}_k(F_{r, n}({\bar{\psi }})) \}$ $\supseteq \{n: n\ge k\}\in U$. Let ${\mathbf {B}}={\mathbf {O}}_{ {\mathbf {A}}}^{({\mathbb {N}})}$ and $h({\bar{\psi }})= h(\psi _0),\dots ,h(\psi _k)$. Then,

$$\begin{aligned} q^{{\mathbf {B}}^\omega /U}_k(h({\bar{\psi }}))&= q^{{\mathbf {B}}^\omega /U}_k (\langle F_{r, n}(\psi _0): n\in \omega \rangle /U,\dots , \langle F_{r, n}(\psi _k): n\in \omega \rangle /U)\\&= \langle q^{\mathbb {N}}_k(F_{r, n}({\bar{\psi }})): n\in \omega \rangle /U. \end{aligned}$$

Moreover, $h({\mathsf {e}}_i^r)=\langle F_{r, n}({\mathsf {e}}_i^r): n\in \omega \rangle /U = \langle {\mathsf {e}}_i^{\mathbb {N}}: n\in \omega \rangle /U$ because $\{n:F_{r, n}({\mathsf {e}}_i^r)={\mathsf {e}}_i^{\mathbb {N}} \}\supseteq \{n: n\ge i\}\in U$. A similar computation works for $\sigma \in \tau$. $\square$

Lemma 4.9

The class ${\mathbb {I}}\,\mathsf {FCA}_\tau$ is closed under subalgebras and products.

Proof

The class of $\mathsf {FCA}_\tau$’s is trivially closed under subalgebras. It is also closed under products, because $\prod _{i\in H} {\mathbf {B}}_i$, where ${\mathbf {B}}_i$ is a $\mathsf {FCA}_\tau$ with value domain ${\mathbf {A}}_i$, can be embedded into the full $\mathsf {FCA}_\tau$ with value domain $\prod _{i\in H}{\mathbf {A}}_i$: the sequence $\langle \varphi _i: A_i^{\mathbb {N}} \rightarrow A_i\in B_i\ |\ i\in H\rangle$ maps to $\varphi : (\prod _{i\in H} A_i)^{\mathbb {N}} \rightarrow \prod _{i\in H} A_i$ defined by $\varphi (r)= \langle \varphi _i(\langle r_j(i):j\in {\mathbb {N}}\rangle )\ |\ i\in H\rangle$. $\square$

Lemma 4.10

Ultrapowers of $\mathsf {FCA}_\tau$s are isomorphic to $\mathsf {FCA}_\tau$s.

Proof

Let ${\mathbf {B}}$ be a $\mathsf {FCA}$ with value domain ${\mathbf {A}}$, K be a set and U be any ultrafilter on K. By Lemma 4.9 we get the conclusion if the ultrapower ${\mathbf {B}}^K/U$ is isomorphic to a subdirect product of $\mathsf {FCA}$s.

A choice function is a function $ch: A^K/U\rightarrow A^K$ such that $ch(w/U)\in w/U$ for every $w\in A^K$ (see [18, Section 6]). Any choice function ch induces a function $ch^+ : (A^K/U)^{\mathbb {N}} \rightarrow (A^{\mathbb {N}})^K$, defined by $ch^+(r)_k = \langle ch(r_i)_k: i\in {\mathbb {N}} \rangle$, for every $r\in (A^K/U)^{\mathbb {N}}$ and $k\in K$. We use the choice function ch to define a function $h_{ch}: B^K/U\rightarrow {\mathcal {O}}_{A^K/U}^{({\mathbb {N}})}$ as follows: $h_{ch}(u/U)(r)=\langle u_k(ch^+(r)_k): k\in K\rangle /U$, for every $u\in B^K$, $r\in (A^K/U)^{\mathbb {N}}$. The map $h_{ch}$ is a homomorphism from the ultrapower ${\mathbf {B}}^K/U$ into the full $\mathsf {FCA}$ ${\mathbf {O}}_{{\mathbf {A}}^K/U}^{({\mathbb {N}})}$ with value domain ${\mathbf {A}}^K/U$. Let ${\mathbf {C}}:= {\mathbf {B}}^K/U$, ${\mathbf {D}}:={\mathbf {O}}_{{\mathbf {A}}^K/U}^{({\mathbb {N}})}$, $r\in (A^K/U)^{\mathbb {N}}$ and $s_k:= ch^+(r)_k\in A^{\mathbb {N}}$ ($k\in K$).

$$\begin{aligned} h_{ch}({\mathsf {e}}_i^{\mathbf {C}})(r)&= h_{ch}(\langle {\mathsf {e}}_i^{\mathbf {B}}:k\in K\rangle /U)(r)\quad&\\ {}&=h_{ch}(\langle {\mathsf {e}}_i^{\mathbb {N}}:k\in K\rangle /U)(r)\quad&\ {\mathbf {B}}\in \mathsf {FCA}\\ {}&=\langle {\mathsf {e}}_i^{\mathbb {N}}(ch^+(r)_k): k\in K\rangle /U\quad&\text{ Def. }\ h_{ch}\\ {}&=\langle ch(r_i)_k: k\in K\rangle /U \quad&\text{ Def. } ch^+ \text{ and } {\mathsf {e}}_i^{\mathbb {N}}\\ {}&= ch(r_i)/U= r_i\quad&\ ch(r_i)\in r_i \end{aligned}$$

Without loss of generality, we prove that $h_{ch}$ preserves $q_2^{\mathbf {C}}$.

$$\begin{aligned}&h_{ch}(q_2^{\mathbf {C}}(u/U,w^1/U,w^2/U))(r)\quad&\\&= h_{ch}( \langle q_2^{\mathbf {B}}(u_k,w^1_k,w^2_k): k\in K\rangle /U)(r) \quad&\hbox { Def.}\ q_2^{\mathbf {C}}\\&= \langle q_2^{\mathbf {B}}(u_k,w^1_k,w^2_k)(s_k): k\in K\rangle /U \quad&\hbox { Def.}\ h_{ch}\\&= \langle q_2^{\mathbb {N}}(u_k,w^1_k,w^2_k)(s_k): k\in K\rangle /U\quad&\text {Lemma}~3.7 \\&= \langle u_k(s_k[w^1_k(s_k),w^2_k(s_k)]): k\in K\rangle /U\quad&\hbox { Def.}\ q_2^{\mathbb {N}}\\&= \langle u_k(ch^+(r)_k[w^1_k(s_k),w^2_k(s_k)]): k\in K\rangle /U\quad&\hbox { Def.}\ s_k\\&= \langle u_k( \langle ch(r_i)_k: i\in {\mathbb {N}} \rangle [w^1_k(s_k),w^2_k(s_k)]): k\in K\rangle /U\quad&\hbox { Def.}\ ch^+\\&= \langle u_k(w^1_k(s_k),w^2_k(s_k), ch(r_3)_k,ch(r_4)_k,\dots ): k\in K\rangle /U\quad&\end{aligned}$$

Let $t=r[\langle w^1_j(s_j): j\in K\rangle /U, \langle w^2_j(s_j): j\in K\rangle /U]$.

$$\begin{aligned}&q_2^{\mathbf {D}}(h_{ch}(u/U),h_{ch}(w^1/U),h_{ch}(w^2/U))(r)\quad&\\&=q_2^{\mathbb {N}}(h_{ch}(u/U),h_{ch}(w^1/U),h_{ch}(w^2/U))(r)\quad&\text {Lem.}~3.7\\&= h_{ch}(u/U)(r[h_{ch}(w^1/U)(r),h_{ch}(w^2/U)(r)]) \quad&\hbox { Def.}\ q_2^{\mathbb {N}}\\&=h_{ch}(u/U)(r[\langle w^1_j(s_j): j\in K\rangle /U, \langle w^2_j(s_j): j\in K\rangle /U])\quad&\hbox { Def.}\ h_{ch}\\&= \langle u_k(ch^+(t)_k): k\in K\rangle /U\quad&\hbox { Def.}\ h_{ch} \\&= \langle u_k(\langle ch(t_i)_k : i\in {\mathbb {N}} \rangle ): k\in K\rangle /U\quad&\hbox { Def.}\ ch^+ \\&= \langle u_k( ch(t_1)_k, ch(t_2)_k, ch(t_3)_k,ch(t_4)_k,\dots ): k\in K\rangle /U\quad&\\&= \langle u_k( ch(t_1)_k, ch(t_2)_k, ch(r_3)_k,ch(r_4)_k,\dots ): k\in K\rangle /U\quad&\\&\qquad \qquad \qquad \qquad \qquad \qquad \hbox {because}\quad t_i=r_i \quad \hbox {for}\quad i\ge 3\\&= \langle u_k( ch(\langle w^1_j(s_j): j\in K\rangle /U)_k, ch(\langle w^2_j(s_j): j\in K\rangle /U)_k, \quad&\\&\qquad \qquad \qquad ch(r_3)_k,ch(r_4)_k,\dots ): k\in K\rangle /U\quad&\hbox { Def.}\ t \\&= \langle u_k(w^1_k(s_k),w^2_k(s_k), ch(r_3)_k,ch(r_4)_k,\dots ): k\in K\rangle /U\quad&\end{aligned}$$

because $\{k\in K : ch(\langle w^i_j(s_j): j\in K\rangle /U)_k =w^i_k(s_k) \}\in U$ ($i=1,2$). A similar proof works for $\sigma \in \tau$. Hence a homomorphic image of the ultrapower ${\mathbf {B}}^K/U$ is isomorphic to a $\mathsf {FCA}$.

By [3, Lemma 8.2] we have that the ultrapower ${\mathbf {B}}^K/U$ is isomorphic to a subdirect product of $\mathsf {FCA}$s if the family of maps $h_{ch}$ (indexed by choice functions) satisfies the following property: for all distinct $w/U, u/U\in B^K/U$ there exists a choice function ch for which $h_{ch}(w/U)\ne h_{ch}(u/U)$. We are going to prove this fact.

Let $w = \langle w_i:A^{\mathbb {N}}\rightarrow A:i\in K\rangle$ and $u = \langle u_i:A^{\mathbb {N}}\rightarrow A:i\in K\rangle$. For every $j\in K$, let $\rho _j\in A^{\mathbb {N}}$ such that $w_j(\rho _j)\ne u_j(\rho _j)$ whenever $w_j\ne u_j$. For every $i\in {\mathbb {N}}$, let $r_i\in A^K$ such that $r_i(j)=\rho _j(i)$ for all $j\in K$. Define $s\in (A^K/U)^{\mathbb {N}}$ as $s_i=r_i/U$ and consider any choice function ch such that $ch(s_i)=r_i$. Then we have $h_{ch}(w/U)(s)=\langle w_j(\rho _j): j\in K)\rangle /U$ and $h_{ch}(u/U)(s)=\langle u_j(\rho _j): j\in K)\rangle /U$, but $\{j: w_j(\rho _j)=u_j (\rho _j)\}=\{j: w_j= u_j\} \notin U$, because $w/U\ne u/U$. It follows that $h_{ch}(w/U)(s)\ne h_{ch}(u/U)(s)$ and then $h_{ch}(w/U)\ne h_{ch}(u/U)$. $\square$

Lemma 4.10 concludes the proof of the main representation theorem. We now compare clone algebras and Neumann’s abstract $\aleph _0$-clone.

4.3 Neumann’s abstract $\aleph _0$-clone and clone algebras

We say that the clone algebra ${\mathbf {C}}$ is the clone algebra reduct of the abstract $\aleph _0$-clone ${\mathbf {D}}$ (defined in Section 2.2.2) if $D=C$, ${\mathsf {e}}_i^{\mathbf {D}}={\mathsf {e}}_i^{\mathbf {C}}$ and $q_n^{\mathbf {C}}(x,y_1,\dots ,y_n)=q_\infty ^{\mathbf {D}}(x,y_1,\dots ,y_n,{\mathsf {e}}_{n+1}^{\mathbf {D}},{\mathsf {e}}_{n+2}^{\mathbf {D}},\dots )$. It is obvious that every abstract $\aleph _0$-clone has a clone algebra reduct.

Proposition 4.11

• (1) Every clone algebra can be embedded into the clone algebra reduct of a suitable abstract $\aleph _0$-clone.

• (2) There exists a $\mathsf {FCA}$ with value domain $2=\{0,1\}$ that is not the clone algebra reduct of any functional $\aleph _0$-clone with value domain 2.

• (3) Every finite-dimensional clone algebra is isomorphic to a clone algebra reduct of a suitable abstract $\aleph _0$-clone.

Proof

(1) Let ${\mathbf {C}}$ be a clone algebra. By Theorem 4.4${\mathbf {C}}$ is isomorphic to a subalgebra of a full $\mathsf {FCA}$. Every full $\mathsf {FCA}$, being closed under $q_\infty ^{\mathbb {N}}$, is the clone algebra reduct of a functional $\aleph _0$-clone.

(2) Fix a zero-dimensional infinitary operation $\psi :2^{\mathbb {N}}\rightarrow 2$ such that $\psi (0,0,\dots ,0,\dots )=1$ and $\psi (1,1,\dots ,1,\dots )=0$. Then the set $B=\{\psi \}\cup \{{\mathsf {e}}_i^{\mathbb {N}}\ |\ i\ge 1\}$ is a finite-dimensional subalgebra of the full $\mathsf {FCA}$ ${\mathbf {O}}_2^{({\mathbb {N}})}$, because $\psi$ is zero-dimensional and $q_n^{\mathbb {N}}(\psi ,\varphi _1,\dots ,\varphi _n)(s)=\psi (s[\varphi _1(s),\dots ,\varphi _n(s)]) = \psi (s)$ for every $\varphi _i\in {\mathbf {O}}_2^{({\mathbb {N}})}$ and $s\in 2^{\mathbb {N}}$. B is not the clone algebra reduct of any functional $\aleph _0$-clone with value domain 2. Indeed,

$$\begin{aligned} q_\infty ^{\mathbb {N}}(\psi ,{\mathsf {e}}_1^{\mathbb {N}}, \dots ,{\mathsf {e}}_1^{\mathbb {N}},\dots )(s)= {\left\{ \begin{array}{ll}1&{}\hbox { if}\ s_1=0\\ 0&{}\hbox { if}\ s_1=1\end{array}\right. } \end{aligned}$$

is not zero-dimensional and it is distinct from any projection.

(3) Let ${\mathbf {C}}$ be a finite-dimensional clone algebra. Then we define

$q_\infty ^{\mathbf {C}}(a,b_1,b_2,\dots )=q_n^{\mathbf {C}}(a,b_1,b_2,\dots ,b_n)$, where n is the dimension of a. The axioms of abstract $\aleph _0$-clone for $(C,q_\infty ^{\mathbf {C}},{\mathsf {e}}_i^{\mathbf {C}})$ are easily checked. $\square$

Notice that by applying the construction of point (3) above to the finite dimensional clone algebra of point (2) we get an abstract $\aleph _0$-clone that is not functional.

It is open whether every (not finite-dimensional) clone algebra is isomorphic to a clone algebra reduct of a suitable abstract $\aleph _0$-clone.

5 A characterisation of the lattices of equational theories

In this section we propose an answer to the lattice of equational theories problem described in the introduction. We prove that a lattice is isomorphic to a lattice of equational theories if and only if it is isomorphic to the lattice of all congruences of a finite-dimensional clone algebra. Unlike Newrly’s and Nurakunov’s approaches [16, 17], we have an equational axiomatisation of the variety generated by the class of finite-dimensional clone algebras (see Theorem 4.4).

We say that an endomorphism f of the free algebra $\mathbf {F}_{\mathcal {V}}$ is n-finite if $f(v_i)=v_i$ for every $i>n$. An endomorphism is finite if it is n-finite for some n.

Lemma 5.1

[3, 13]. Let ${\mathcal {V}}$ be a variety and $T=Eq({\mathcal {V}})$. Then the lattice L(T) of all equational theories extending T is isomorphic to the congruence lattice of the algebra $(\mathbf {F}_{\mathcal {V}},f)_{f\in \mathrm {End}}$, which is an expansion of the free algebra $\mathbf {F}_{\mathcal {V}}$ by the set End of all its finite endomorphisms.

The set of all n-finite endomorphisms can be collectively expressed by an $(n+1)$-ary operation $q_n^{\mathbf {F}}$ on $\mathbf {F}_{\mathcal {V}}$ (see [12, Definition 3.2]):

$$\begin{aligned} q_n^{\mathbf {F}}(a,b_1,\dots ,b_n)=s(a),\quad \text {for every}\quad a,b_1,\dots ,b_n\in F_{\mathcal {V}}, \end{aligned}$$

(5.1)

where s is the unique n-finite endomorphism of $\mathbf {F}_{\mathcal {V}}$ which sends the generator $v_i$ to $b_i$ ($1\le i\le n$).

Definition 5.2

Let ${\mathcal {V}}$ be a variety and $\mathbf {F}_{\mathcal {V}}$ be the free ${\mathcal {V}}$-algebra over a countable set I of generators. Then the algebra $\mathbf {Cl}({\mathcal {V}})=(\mathbf {F}_{\mathcal {V}}, q_n^\mathbf {F}, {\mathsf {e}}_i^\mathbf {F})$, where ${\mathsf {e}}_i^\mathbf {F}= v_i\in I$ and $q_n^\mathbf {F}$ is defined in (5.1), is called the clone ${\mathcal {V}}$-algebra.

$\mathrm {Clo}\,\mathbf {F}_{\mathcal {V}}$ denotes the clone of term operations of $\mathbf {F}_{\mathcal {V}}$. By Proposition 3.14$(\mathrm {Clo}\,\mathbf {F}_{\mathcal {V}})^\top$ is a block algebra.

Proposition 5.3

Let ${\mathcal {V}}$ be a variety of $\tau$-algebras axiomatised by the equational theory T. Then we have:

• (1) The clone ${\mathcal {V}}$-algebra $\mathbf {Cl}({\mathcal {V}})$ is a finite-dimensional clone $\tau$-algebra, whose congruence lattice $\mathrm {Con}\,\mathbf {Cl}({\mathcal {V}})$ is isomorphic to the lattice L(T) of equational theories extending T.

• (2) If $w\in F_{\mathcal {V}}$ has dimension $n>0$ in $\mathbf {Cl}({\mathcal {V}})$, then there exists a $\tau$-term $t(v_1,\dots ,v_n)$ belonging to w.

• (3) If $w\in F_{\mathcal {V}}$ has dimension 0 in $\mathbf {Cl}({\mathcal {V}})$, then there exists a $\tau$-term $t(v_1)\in w$ such that ${\mathcal {V}} \models t(v_1)=t(v_2)$.

• (4) The clone ${\mathcal {V}}$-algebra $\mathbf {Cl}({\mathcal {V}})$ is isomorphic to the block algebra $(\mathrm {Clo}\,\mathbf {F}_{\mathcal {V}})^\top$.

Proof

(1) By Lemma 5.1 and the definition of $q_n^\mathbf {F}$.

(2) Let $w\in F_{\mathcal {V}}$ of dimension $n>0$ and let $u\in w$ be an arbitrary term. Let $v_k$ be the last variable occurring in u (i.e., $v_i$ does not occur in u for every $i>k$). If $k \le n$, then u satisfies the required property. Let $k> n$. Since $q_k^\mathbf {F}(w,{\mathsf {e}}_1^\mathbf {F},\dots ,{\mathsf {e}}_n^\mathbf {F},{\mathsf {e}}_{1}^\mathbf {F},\dots , {\mathsf {e}}_1^\mathbf {F})=w$ is the equivalence class of the term $u[v_1/v_{n+1},v_1/v_{n+2}\dots ,v_1/v_k ]$, then this last term belongs to w and satisfies the required property.

(3) Let $w\in F_{\mathcal {V}}$ be zero-dimensional and $u\in w$ be an arbitrary term. If u is ground, then $u=u(v_1)$ and we are done. Otherwise, we follow the reasoning in item (2).

(4) Let ${\mathbf {C}} = \mathbf {Cl}({\mathcal {V}})$ in this proof. From Theorem 3.18 it follows that ${\mathbf {C}}$ is isomorphic to the block algebra $R_{\mathbf {C}}^\top$ generated by the clone $R_{\mathbf {C}}$ of ${\mathbf {C}}$-representable functions. The conclusion follows because a function is representable in the clone ${\mathcal {V}}$-algebra ${\mathbf {C}}$ if and only if it is a term operation of $\mathbf {F}_{\mathcal {V}}$. In other words, $\mathrm {Clo}\,\mathbf {F}_{\mathcal {V}} = R_{\mathbf {C}}$. $\square$

Definition 5.4

Let ${\mathbf {C}}$ be a clone algebra and $R_{\mathbf {C}}$ be the clone of all ${\mathbf {C}}$-representable functions described in Definition 3.15.

• (1) The ${\mathbf {C}}$-type is the algebraic type $\rho _{\mathbf {C}} = \{{\overline{f}}: f \in R_{\mathbf {C}}\}$, where the operation symbol ${\overline{f}}$ has arity k if $f\in R_{\mathbf {C}}$ is a k-ary function.

• (2) The $\rho _{\mathbf {C}}$-algebra ${\mathbf {R}}_{\mathbf {C}}=(C, f)_{f\in R_{\mathbf {C}}}$ is called algebra of ${\mathbf {C}}$-representable functions;

• (3) The algebra $\overline{{\mathbf {R}}}_{\mathbf {C}}=({\mathbf {R}}_{\mathbf {C}},q_n^{\mathbf {C}},{\mathsf {e}}_i^{\mathbf {C}})$ is called the clone $\rho _{\mathbf {C}}$-algebra of ${\mathbf {C}}$-representable functions.

Theorem 5.5

Let ${\mathbf {C}}$ be a finite-dimensional clone algebra and ${\mathcal {V}}=\mathrm {Var}({\mathbf {R}}_{\mathbf {C}})$ be the variety of type $\rho _{\mathbf {C}}$ generated by ${\mathbf {R}}_{\mathbf {C}}$. Then we have:

• (i) ${\mathbf {R}}_{\mathbf {C}}$ is isomorphic to the free $\rho _{\mathbf {C}}$-algebra over a countable set of generators in the variety ${\mathcal {V}}$;

• (ii) $\overline{{\mathbf {R}}}_{\mathbf {C}}$ is isomorphic to the clone ${\mathcal {V}}$-algebra.

Proof

We show that ${\mathbf {R}}_{\mathbf {C}}$ is the free algebra over the set $\{{\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}},\dots \}$ of generators in the variety ${\mathcal {V}}$. Let ${\mathbf {A}}\in {\mathcal {V}}$ and $g: \{{\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}},\dots \}\rightarrow A$ be an arbitrary map. We extend g to a map $g^*: C\rightarrow A$ as follows. Let $b\in C$ of dimension k. By Proposition 3.17 the set $R(b)=\bigcup _{n\in \omega } \{f\in R_{\mathbf {C}}^{(n)}: b=f({\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}})\}$ is a block of arity k. For every $m\ge k$, we denote by $f^{m}_b:C^m\rightarrow C$ the unique function of arity m belonging to R(b). The function $f^{m}_b$ is defined as follows: $f^{m}_b(c_1,\dots ,c_m)=q_m^{\mathbf {C}}(b,c_1,\dots ,c_m)$ for every $c_1,\dots ,c_m\in C$. Since $f^{m}_b$ is ${\mathbf {C}}$-representable, then $\overline{f^{m}_b}\in \rho _{\mathbf {C}}$ for every $m\ge k$. Then we define

$$\begin{aligned} g^*(b)=\overline{f^{k}_b}^{\mathbf {A}}(g({\mathsf {e}}_1^{\mathbf {C}}),\dots ,g({\mathsf {e}}_k^{\mathbf {C}})). \end{aligned}$$

Since ${\mathbf {R}}_{\mathbf {C}}\models f^m_b(x_1,\dots ,x_k,x_{k+1},\dots , x_m)= f^k_b(x_1,\dots ,x_k)$ for every $m\ge k$ and ${\mathbf {A}}\in {\mathcal {V}}$, then we have $g^*(b) =\overline{f^m_b}^{\mathbf {A}} (g({\mathsf {e}}_1^{\mathbf {C}}),\dots ,g({\mathsf {e}}_m^{\mathbf {C}}))$ for every $m\ge k$.

We now show that $g^*:C\rightarrow A$ is a homomorphism of $\rho _{\mathbf {C}}$-algebras, that is, $g^*( h({\mathbf {b}}))={\overline{h}}^{\mathbf {A}}(g^*(b_1),\dots ,g^*(b_n))$, for every ${\overline{h}}\in \rho _{\mathbf {C}}$ of arity n and ${\mathbf {b}}=b_1,\dots ,b_n\in C^n$. As a matter of notation, we define ${\mathbf {e}}^{{\mathbf {C}},k}={\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_k^{\mathbf {C}}$; $h({\mathbf {e}}^{{\mathbf {C}},n})=h({\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}})$ and $g({\mathbf {e}}^{{\mathbf {C}},k})= g({\mathsf {e}}_1^{\mathbf {C}}),\dots ,g({\mathsf {e}}_k^{\mathbf {C}})$. Let $m\ge n$ be a natural number greater than the maximal number among the dimensions of the elements $b_1,\dots ,b_n,h({\mathbf {b}})$. Then we have:

• ${\overline{h}}^{\mathbf {A}}(g^*(b_1),\dots ,g^*(b_n))= {\overline{h}}^{\mathbf {A}}(\overline{f^m_{b_1}}^{\mathbf {A}}(g({\mathbf {e}}^{{\mathbf {C}},m})),\dots ,\overline{f^m_{b_n}}^{\mathbf {A}}(g({\mathbf {e}}^{{\mathbf {C}},m})))$;

• $g^*(h({\mathbf {b}}))=\overline{f^m_{h({\mathbf {b}})}}^{\mathbf {A}}(g({\mathbf {e}}^{{\mathbf {C}},m}))$.

We get that $g^*$ is a homomorphism if the algebra ${\mathbf {A}}$ satisfies the identity

$$\begin{aligned} {\overline{h}}(\overline{f^m_{b_1}} (x_1,\dots ,x_m),\dots ,\overline{f^m_{b_n}} (x_1,\dots ,x_m))= \overline{f^m_{h({\mathbf {b}})}}(x_1,\dots ,x_m). \end{aligned}$$

Since ${\mathbf {A}}\in {\mathcal {V}}$ and ${\mathcal {V}}$ is generated by ${\mathbf {R}}_{\mathbf {C}}$, then it is sufficient to prove that the algebra ${\mathbf {R}}_{\mathbf {C}}$ satisfies the above identity. By putting ${\mathbf {x}}= x_1,\dots ,x_m$ the conclusion follows from Lemma 3.16: $f^m_{h({\mathbf {b}})}({\mathbf {x}})= q_m^{\mathbf {C}}(h({\mathbf {b}}),{\mathbf {x}})=_{Lem.~3.16} h(q_m^{\mathbf {C}}(b_1,{\mathbf {x}}),\dots ,q_m^{\mathbf {C}}(b_n,{\mathbf {x}}))=h(f^m_{b_1}({\mathbf {x}}),\dots ,f^m_{b_n} ({\mathbf {x}}))$. It remains to show that the operation $p(x)=q_n^{\mathbf {C}}(x,{\mathbf {b}})$ is the unique n-finite endomorphism of the free algebra ${\mathbf {R}}_{\mathbf {C}}$ which sends ${\mathsf {e}}_i^{\mathbf {C}}$ to $b_i$ ($1\le i\le n$). This again follows from Lemma 3.16 because $p(h({\mathbf {a}}))=q_n^{\mathbf {C}}(h({\mathbf {a}}),{\mathbf {b}}) = h(q_n^{\mathbf {C}}(a_1,{\mathbf {b}}),\dots ,q_n^{\mathbf {C}}(a_k,{\mathbf {b}}))=h(p(a_1),\dots ,p(a_k))$ for every ${\overline{h}}\in \rho _{\mathbf {C}}$ of arity k. $\square$

The following lemma is fundamental in the study of clone algebras and its applications.

Lemma 5.6

Let ${\mathbf {C}}$ and ${\mathbf {D}}$ be clone algebras of type $\tau$ and $\nu$, respectively.

• (i) An equivalence relation $\theta$ on C is a congruence on ${\mathbf {C}}$ if and only if $\theta$ is a congruence on the pure reduct ${\mathbf {C}}_0$; hence, $\mathrm {Con}\, {\mathbf {C}}=\mathrm {Con}\, {\mathbf {C}}_0$.

• (ii) If ${\mathbf {C}}$ and ${\mathbf {D}}$ have the same pure reduct, then $\mathrm {Con}\, {\mathbf {C}}=\mathrm {Con}\, {\mathbf {D}}$.

Proof

(i) If ${\mathbf {a}}\theta {\mathbf {b}}$ and $\theta$ preserves the operators $q_n$, then by Lemma 3.16$\sigma ^{\mathbf {C}}({\mathbf {a}})=q_k^{\mathbf {C}}(\sigma ^{\mathbf {C}}({\mathbf {e}}),{\mathbf {a}})\ \theta \ q_k^{\mathbf {C}}(\sigma ^{\mathbf {C}}({\mathbf {e}}),{\mathbf {b}})=\sigma ^{\mathbf {C}}({\mathbf {b}})$ for every $\sigma \in \tau$. $\square$

Recalling that every finite-dimensional $\mathsf {CA}$ is isomorphic to a block algebra, the following theorem relates lattices of equational theories and clones.

Theorem 5.7

A lattice is isomorphic to a lattice of equational theories if and only if it is isomorphic to the congruence lattice of a finite-dimensional $\mathsf {CA}$.

Proof

($\Rightarrow$) It follows from Proposition 5.3(1).

($\Leftarrow$) Let ${\mathbf {C}}$ be a finite-dimensional clone algebra and $\overline{{\mathbf {R}}}_{\mathbf {C}}$ be the clone $\rho _{\mathbf {C}}$-algebra of ${\mathbf {C}}$-representable functions. Since ${\mathbf {C}}$ and $\overline{{\mathbf {R}}}_{\mathbf {C}}$ have the same pure reduct, then from Lemma 5.6 it follows that $\mathrm {Con}\,{\mathbf {C}}=\mathrm {Con}\,\overline{{\mathbf {R}}}_{\mathbf {C}}$. The conclusion of the theorem follows from Theorem 5.5(ii) and Proposition 5.3(1), because $\overline{{\mathbf {R}}}_{\mathbf {C}}$ is isomorphic to the clone $\mathrm {Var}({\mathbf {R}}_{\mathbf {C}})$-algebra. $\square$

6 The category of varieties

Important properties of a variety ${\mathcal {V}}$ depend on the pure reduct of the clone ${\mathcal {V}}$-algebra $\mathbf {Cl}({\mathcal {V}})$ associated with its free algebra. However, not every clone $\tau$-algebra is the clone ${\mathcal {V}}$-algebra associated with the free algebra of a variety ${\mathcal {V}}$ of type $\tau$. In this section after characterising central elements in clone algebras, we introduce minimal clone algebras and prove that a clone $\tau$-algebra ${\mathbf {C}}$ is minimal if and only if ${\mathbf {C}}\cong \mathbf {Cl}({\mathcal {V}})$ for some variety ${\mathcal {V}}$ of type $\tau$. We also introduce the category $\mathcal {CA}$ of all clone algebras (of arbitrary similarity types) with pure homomorphisms (i.e., preserving only the nullary operators ${\mathsf {e}}_i$ and the operators $q_n$) as arrows and we show that the category $\mathcal {CA}$ is equivalent both to the full subcategory $\mathcal {MCA}$ of minimal clone algebras and, more to the point, to the variety $\mathsf {CA}_0$ of pure clone algebras. We prove that $\mathcal {MCA}$ is categorically isomorphic to the category $\mathcal {VAR}$ of all varieties, so that we can use the more manageable category $\mathcal {MCA}$ of minimal clone algebras and pure homomorphisms to study the category $\mathcal {VAR}$. We use $\mathcal {MCA}$ and central elements in clone algebras to show a generalisation of the theorem on independent varieties presented by Grätzer et al. in [7].

6.1 Central elements in clone algebras

Every clone algebra is an nCH, for every n (see Section 2.1). Therefore, there exists a bijection between the set of n-central elements of a clone algebra and the set of its n-tuples of complementary factor congruences. In this section we characterise central elements in clone algebras. They will be used in the proof of Theorem 6.13.

Lemma 6.1

Let ${\mathbf {C}}$ be a clone algebra and $c\in C$ be n-central, for some n. Then c is finite-dimensional with $\gamma (c)\le n$, and it is m-central for every $m\ge n$.

Proof

By the way of contradiction, let us suppose that either c is finite-dimensional and $\gamma (c)>n$ or $\gamma (c)=\omega$. In both cases there exists $m>n$ such that c is dependent on ${\mathsf {e}}_m$, meaning that $c\ne q_m(c,{\mathsf {e}}_1,\ldots ,{\mathsf {e}}_{m-1},{\mathsf {e}}_{m+1})$.

Since c is n-central, by (D4) in Proposition 2.1 the equation

$$\begin{aligned}&q_n(c,q_m(g_1,h_1^1,\ldots ,h_m^1),\ldots , q_m(g_n,h_1^n,\ldots ,h_m^n))&\\&\quad = q_m(q_n(c,g_1,\ldots ,g_n),q_n(c,h_1^1,\ldots ,h_1^n),\ldots ,q_n(c,h_m^1,\ldots ,h_m^n))&\end{aligned}$$

holds for all $g_1,\ldots ,g_n,h_1^1,\ldots h^1_m,\ldots , h^n_1,\ldots , h_m^n$ in C. By letting $g_i={\mathsf {e}}_i$ for $1\le i\le n$ , $h_i^j={\mathsf {e}}_i$ for $1\le i\le m-1$ and $1\le j\le n$, and $h_m^j={\mathsf {e}}_{m+1}$ for $1\le j\le n$ in the equation above, and by exploiting again the fact that c is n-central, we get $q_n(c,{\mathsf {e}}_1,\ldots ,{\mathsf {e}}_n)= q_m(c,{\mathsf {e}}_1,\dots ,{\mathsf {e}}_{m-1},{\mathsf {e}}_{m+1})$. The left-hand side of the equation above being equal to c, we get a contradiction using our initial assumption.

Since $\gamma (c)\le n$ then c is independent of ${\mathsf {e}}_{n+1},\ldots ,{\mathsf {e}}_m$ and the equations of m-centrality follow from the corresponding of n-centrality. $\square$

Proposition 6.2

Let ${\mathbf {C}}$ be a clone $\tau$-algebra and $c\in C$. If there exists n such that c is n-central, then, for all m, c is m-central if and only if $m\ge \gamma (c)$.

Proof

By Lemma 6.1 it is enough to show that c is $\gamma (c)$-central. $\square$

Proposition 6.3

Let ${\mathbf {C}}$ be a clone $\tau$-algebra and ${\mathbf {C}}_0$ be its pure reduct.

• (i) An element is n-central in ${\mathbf {C}}$ iff it is n-central in ${\mathbf {C}}_0$.

• (ii) $\mathrm {Ce}({\mathbf {C}})=\{c:$ c is n-central for some $n\}$ is a subalgebra of ${\mathbf {C}}_0$.

Proof

(i) For every $\sigma \in \tau$ of arity k, $\sigma ^{\mathbf {C}}({\mathbf {a}})=q_k^{\mathbf {C}}(\sigma ^{\mathbf {C}}({\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_k^{\mathbf {C}}), {\mathbf {a}})$.

(ii) Let a and ${\mathbf {b}}=b_1,\dots ,b_n$ be elements of $\mathrm {Ce}({\mathbf {C}})$. We show that $q_n(a,{\mathbf {b}})$ is central. By Lemma 6.1$a,b_1,\dots ,b_n$ are finite-dimensional. Let $m\ge n$ be greater than the dimensions of $a,b_1,\dots ,b_n$. Since by (C5) $q_n(a,{\mathbf {b}})= q_m(a,{\mathbf {b}},{\mathsf {e}}_{n+1},\dots ,{\mathsf {e}}_m)$ and by Lemma 6.1$a,b_1,\dots ,b_n, {\mathsf {e}}_{n+1},\dots ,{\mathsf {e}}_m$ are m-central, then we claim that $q_m(a,{\mathbf {b}},{\mathsf {e}}_{n+1},\dots ,{\mathsf {e}}_m)$ is also m-central. This follows because ${\mathbf {C}}$ is an $m\mathrm {CH}$ and the m-central elements of an $m\mathrm {CH}$ are closed under $q_m$ (see [2, Proposition 1]). $\square$

6.2 Minimal clone algebras

In this section we introduce minimal clone algebras and prove that a clone $\tau$-algebra ${\mathbf {C}}$ is minimal if and only if ${\mathbf {C}}$ is isomorphic to the clone ${\mathcal {V}}$-algebra $\mathbf {Cl}({\mathcal {V}})$ for some variety ${\mathcal {V}}$ of type $\tau$.

If ${\mathbf {C}}$ is a clone $\tau$-algebra, then $M({\mathbf {C}})$ denotes the minimal subalgebra of ${\mathbf {C}}$.

Consider the type $\tau ({\mathsf {e}})=\tau \cup \{{\mathsf {e}}_1,\dots ,{\mathsf {e}}_n,\dots \}$. A ground $\tau ({\mathsf {e}})$-term is a term defined by the grammar: $t,t_i::= {\mathsf {e}}_i\ |\ \sigma (t_1,\dots ,t_k)$, where $\sigma \in \tau$.

Lemma 6.4

Let ${\mathbf {C}}$ be a clone $\tau$-algebra. Then, $b\in M({\mathbf {C}})$ if and only if $b=t^{\mathbf {C}}$ for some ground $\tau ({\mathsf {e}})$-term t.

Proof

The set of elements $t^{\mathbf {C}}$, where t is a ground $\tau ({\mathsf {e}})$-term, is closed under $q_n$. The proof is by induction over the complexity of the ground $\tau ({\mathsf {e}})$-term in the first argument of $q_n$. $\square$

From Lemma 6.4 it follows that $M({\mathbf {C}})$ is finite-dimensional.

Definition 6.5

We say that a clone $\tau$-algebra ${\mathbf {C}}$ is minimal if ${\mathbf {C}}= M({\mathbf {C}})$.

We remark that, if $h:{\mathbf {C}}\rightarrow {\mathbf {D}}$ is an onto homomorphism of clone $\tau$-algebras and ${\mathbf {C}}$ is minimal, then ${\mathbf {D}}$ is minimal.

The translation of the ground $\tau ({\mathsf {e}})$-terms into $\tau$-terms in the variables $v_1,v_2,\dots ,v_n,\dots$ is defined by ${\mathsf {e}}_i^*=v_i;\quad \sigma (t_1,\dots ,t_n)^*=\sigma (t_1^*,\dots ,t_n^*)$.

Theorem 6.6

Let ${\mathbf {C}}=({\mathbf {C}}_\tau ,q_n^{\mathbf {C}},{\mathsf {e}}_i^{\mathbf {C}})$ be a minimal clone $\tau$-algebra, $\mathrm {Var}({\mathbf {C}}_\tau )$ be the variety of $\tau$-algebras generated by ${\mathbf {C}}_\tau$, and $\mathrm {Var}({\mathbf {C}})$ be the variety of clone $\tau$-algebras generated by ${\mathbf {C}}$. Then,

• (i) ${\mathbf {C}}_\tau$ is the free algebra over a countable set of generators in $\mathrm {Var}({\mathbf {C}}_\tau )$;

• (ii) ${\mathbf {C}}$ is isomorphic to the clone $\mathrm {Var}({\mathbf {C}}_\tau )$-algebra;

• (iii) ${\mathbf {C}}$ is the free algebra over an empty set of generators in $\mathrm {Var}({\mathbf {C}})$.

Proof

(i) Let ${\mathbf {A}}\in \mathrm {Var}({\mathbf {C}}_\tau )$ and $g: \{{\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}},\dots \}\rightarrow A$ be an arbitrary map. We extend g to a map $g^*: C\rightarrow A$ as follows. Let $b\in C$ of dimension k and let $r\ge k$. Since ${\mathbf {C}}$ is minimal, there exists a ground $\tau ({\mathsf {e}})$-term $t=t({\mathsf {e}}_1,\dots ,{\mathsf {e}}_k)$ such that $t^{\mathbf {C}}=b$. We define

$$\begin{aligned} g^*(b)=(t^*)^{{\mathbf {A}},r}(g({\mathsf {e}}_1^{\mathbf {C}}),\dots ,g({\mathsf {e}}_r^{\mathbf {C}})), \end{aligned}$$

where $t^*=t^*(v_1,\dots ,v_k)$ is a $\tau$-term and $(t^*)^{{\mathbf {A}},r}: A^r\rightarrow A$ ($r\ge k$) is the term operation of arity r defined by $t^*$. The definition of $g^*(b)$ is independent of $r\ge k$. We show that $g^*$ is a homomorphism of $\tau$-algebras, that is, $g^*( \sigma ^{\mathbf {C}}({\mathbf {b}}))=\sigma ^{\mathbf {A}}(g^*(b_1),\dots ,g^*(b_n))$, for every $\sigma \in \tau$ of arity n and ${\mathbf {b}}=b_1,\dots ,b_n\in C^n$. Let $m\ge n$ be a natural number greater than the maximal number among the dimensions of the elements $b_1,\dots ,b_n,\sigma ^{\mathbf {C}}({\mathbf {b}})$. If $b_i=t_i^{{\mathbf {C}}}$ for some ground $\tau ({\mathsf {e}})$-term $t_i$ ($i=1,\dots ,n$), then we have:

$$\begin{aligned}\sigma ^{\mathbf {A}}(g^*(b_1),\dots ,g^*(b_n))&= \sigma ^{\mathbf {A}}((t_1^*)^{{\mathbf {A}},m}(g({\mathsf {e}}_1^{\mathbf {C}}),\dots ),\dots ,(t_n^*)^{{\mathbf {A}},m}(g({\mathsf {e}}_1^{\mathbf {C}}),\dots ))&\\&=(\sigma (t_1,\dots ,t_n)^*)^{{\mathbf {A}},m}(g({\mathsf {e}}_1^{\mathbf {C}}),\dots ,g({\mathsf {e}}_m^{\mathbf {C}}))&\\&=g^*(\sigma ^{\mathbf {C}}({\mathbf {b}})).&\end{aligned}$$

(ii) By Lemma 3.3 the map $x \mapsto q_n^{\mathbf {C}}(x,{\mathbf {b}})$ is the unique endomorphism of the free algebra ${\mathbf {C}}_\tau$ which sends ${\mathsf {e}}_i$ to $b_i$ ($1\le i\le n$).

(iii) Let ${\mathbf {A}}\in \mathrm {Var}({\mathbf {C}})$. Then ${\mathbf {A}}_\tau \in \mathrm {Var}({\mathbf {C}}_\tau )$. By (i) there exists a unique homomorphism f from ${\mathbf {C}}_\tau$ into ${\mathbf {A}}_\tau$ such that $f({\mathsf {e}}_i^{\mathbf {C}})= {\mathsf {e}}_i^{\mathbf {A}}$. Since ${\mathbf {C}}$ is minimal, then f is onto $M({\mathbf {A}})$ and, for every ground $\tau ({\mathsf {e}})$-term t, we have $f(t^{\mathbf {C}})=t^{\mathbf {A}}$. The proof that f preserves $q_n$ is by induction over the complexity of the first argument of $q_n$. $\square$

Corollary 6.7

A clone $\tau$-algebra ${\mathbf {C}}$ is minimal if and only if ${\mathbf {C}}$ is isomorphic to the clone ${\mathcal {V}}$-algebra $\mathbf {Cl}({\mathcal {V}})$ for some variety ${\mathcal {V}}$ of type $\tau$.

Let ${\mathcal {V}}$ be a variety of $\tau$-algebras axiomatised by the equational theory $T=Eq({\mathcal {V}})$ and ${\mathcal {V}}^{cl}$ be the variety of clone $\tau$-algebras satisfying T. Since $\mathbf {Cl}({\mathcal {V}})$ satisfies T, then $\mathrm {Var}(\mathbf {Cl}({\mathcal {V}}))\subseteq {\mathcal {V}}^{cl}$. In the following proposition we show that the inclusion is sometimes strict.

Proposition 6.8

• (i) The clone ${\mathcal {V}}$-algebra $\mathbf {Cl}({\mathcal {V}})$ is the free algebra over an empty set of generators in the variety ${\mathcal {V}}^{cl}$;

• (ii) ${\mathcal {V}}^{cl}$ is not in general generated by $\mathbf {Cl}({\mathcal {V}})$.

Proof

(i) Let ${\mathbf {A}}\in {\mathcal {V}}^{cl}$. Since ${\mathbf {A}}_\tau \in {\mathcal {V}}$, then there exists a unique homomorphism f of $\tau$-algebras from $\mathbf {F}_{\mathcal {V}}$ into ${\mathbf {A}}_\tau$ such that $f({\mathsf {e}}_i^{\mathbf {F}})=f(v_i)= {\mathsf {e}}_i^{\mathbf {A}}$. The proof that f preserves the operators $q_n^{\mathbf {F}}$ is similar to that of Theorem 6.6(ii).

(ii) If ${\mathcal {S}}$ is the class of all sets (i.e., the variety of all algebras in the empty type), then ${\mathcal {S}}^{cl}$ is the variety of all pure clone algebras. We show that $\mathbf {Cl}({\mathcal {S}})$ does not genetate ${\mathcal {S}}^{cl}$. $\mathbf {Cl}({\mathcal {S}})=(I,q_n^{\mathbf {I}},{\mathsf {e}}_i^{\mathbf {I}})$ has the set $I=\{v_1,v_2,\dots ,v_n,\dots \}$ as universe and ${\mathsf {e}}_i^{\mathbf {I}}=v_i$. The algebra ${\mathbf {I}}$ satisfies the identity

$$\begin{aligned} q_n(y, q_n(y, x_{11},\dots ,x_{1n}),\dots ,q_n(y,x_{n1},\dots ,x_{nn}))=q_n(y,x_{11},\dots ,x_{nn})\nonumber \\ \end{aligned}$$

(6.1)

but ${\mathcal {S}}^{cl}$ does not satisfy it. Here is a counterexample. Let $2=\{0,1\}$ and $f:2^2\rightarrow 2$ be a function such that $f(0,0)=0$ and $f(0,1)=f(1,0)=f(1,1)=1$. Then $1=f(f(0,1),f(1,0))\ne f(0,0)$. Then the pure functional clone algebra of universe ${\mathcal {O}}_2^{({\mathbb {N}})}$ does not satisfies the above identity (6.1): $1=q_2^{\mathbb {N}}(f^\top ,q_2^{\mathbb {N}}(f^\top ,{\mathsf {e}}_1^{\mathbb {N}},{\mathsf {e}}_2^{\mathbb {N}}), q_2^{\mathbb {N}}(f^\top ,{\mathsf {e}}_2^{\mathbb {N}},{\mathsf {e}}_1^{\mathbb {N}}))(r)\ne q_2^{\mathbb {N}}(f^\top ,{\mathsf {e}}_1^{\mathbb {N}},{\mathsf {e}}_1^{\mathbb {N}})(r)=0$, where $r\in 2^{\mathbb {N}}$ satisfies $r_1=0$ and $r_2=1$. $\square$

In Proposition 6.10 below we compare a clone $\tau$-algebra ${\mathbf {C}}$ with the clone $\rho _{\mathbf {C}}$-algebra of its ${\mathbf {C}}$-representable functions.

Lemma 6.9

Let ${\mathbf {C}}=({\mathbf {C}}_\tau ,q_n^{\mathbf {C}},{\mathsf {e}}_i^{\mathbf {C}})$ be a finite-dimensional clone $\tau$-algebra. Then $a\in M({\mathbf {C}})$ if and only if, for some $\tau$-term t, the block R(a) of ${\mathbf {C}}$-representable functions determined by a is equal to the block $T_t^{{\mathbf {C}}_\tau }$ of term operations determined by t.

Proof

($\Rightarrow$) If $a\in M({\mathbf {C}})$ has dimension n, then by Lemma 6.4 we have $a=t^{\mathbf {C}}({\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}})$ for some $\tau ({\mathsf {e}})$-term $t= t({\mathsf {e}}_1,\dots ,{\mathsf {e}}_n)$. Let $t^*= t(v_1,\dots ,v_n)$ be the corresponding $\tau$-term. Since

$$\begin{aligned} q_k^{\mathbf {C}}(a,{\mathbf {b}})= q_k^{\mathbf {C}}(t^{\mathbf {C}}({\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}}),{\mathbf {b}}) =_{(C7)}\dots =_{(C7,C2)} (t^*)^{{\mathbf {C}}_\tau ,k}({\mathbf {b}}) \end{aligned}$$

for every $k\ge n$ and ${\mathbf {b}}\in C^k$, then $R(a)=T_{t^*}^{{\mathbf {C}}_\tau }$.

($\Leftarrow$) If $R(a)=T_u^{{\mathbf {C}}_\tau }$ for some $\tau$-term $u=u(v_1,\dots ,v_n)$, then $a=q_n^{\mathbf {C}}(a,{\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}})= u^{{\mathbf {C}}_\tau ,n}({\mathsf {e}}_1^{\mathbf {C}},\dots ,e_n^{\mathbf {C}})=u({\mathsf {e}}_1,\dots ,{\mathsf {e}}_n)^{\mathbf {C}}$. By Lemma 6.4$a\in M({\mathbf {C}})$. $\square$

Proposition 6.10

Let ${\mathbf {C}}=({\mathbf {C}}_\tau ,q_n^{\mathbf {C}},{\mathsf {e}}_i^{\mathbf {C}})$ be a finite-dimensional clone $\tau$-algebra and $\overline{{\mathbf {R}}}_{\mathbf {C}}$ be the clone $\rho _{\mathbf {C}}$-algebra of ${\mathbf {C}}$-representable functions. Then the following conditions hold:

• (i) $\overline{{\mathbf {R}}}_{\mathbf {C}}$ is minimal.

• (ii) ${\mathbf {C}}$ is minimal if and only if $R_{\mathbf {C}} = \mathrm {Clo}\,{\mathbf {C}}_\tau$.

Proof

(i) By Theorem 5.5(ii) and Corollary 6.7.

(ii) First of all, we have $\mathrm {Clo}\,{\mathbf {C}}_\tau \subseteq R_{\mathbf {C}}$, because by Lemma 3.16 every basic operation of type $\tau$ is ${\mathbf {C}}$-representable. For the opposite inclusion it is sufficient to apply Lemma 6.9. $\square$

6.3 The category of clone algebras and pure homomorphisms

A map $f:C\rightarrow D$ is called a pure homomorphism from a clone $\tau$-algebra ${\mathbf {C}}$ into a clone $\nu$-algebra ${\mathbf {D}}$ if f is a homomorphism from the pure reduct ${\mathbf {C}}_0$ of ${\mathbf {C}}$ into the pure reduct ${\mathbf {D}}_0$ of ${\mathbf {D}}$.

Let Type be the class of all algebraic types. The category $\mathcal {CA}$ has the class $\bigcup _{\tau \in \mathrm {Type}} \mathsf {CA}_\tau$ as objects and pure homomorphisms as arrows. We denote by $\mathcal {MCA}$ the full subcategory of $\mathcal {CA}$ whose objects are the minimal clone algebras. The variety $\mathsf {CA}_0$ of pure clone algebras is a full subcategory of $\mathcal {CA}$. The categories $\mathcal {CA}$, $\mathcal {MCA}$ and $\mathsf {CA}_0$ are equivalent, because they have the same skeleton.

We denote by $\mathcal {VAR}$ the category whose objects are varieties of algebras and whose arrows are interpretations of varieties. We recall from [13, Page 245] that an interpretation of a variety ${\mathcal {V}}$ of type $\tau$ into a variety ${\mathcal {W}}$ of type $\nu$ is a mapping f with domain $\tau$ satisfying:

• If $\sigma \in \tau$ has arity $n>0$, then $f(\sigma )$ is an n-ary $\nu$-term;

• If $\sigma \in \tau$ has arity 0, then $f(\sigma )=t$ is a unary $\nu$-term such that the equation $t(v_1)=t(v_2)$ is valid in ${\mathcal {W}}$;

• For every algebra ${\mathbf {A}}\in {\mathcal {W}}$, the algebra ${\mathbf {A}}^f=(A,f(\sigma )^{{\mathbf {A}},k})_{\sigma \in \tau }$ belongs to ${\mathcal {V}}$, where $f(\sigma )^{{\mathbf {A}},k}$ ($\sigma$ of arity k) is the k-ary term operation determined by $f(\sigma )$.

Theorem 6.11

The categories $\mathcal {VAR}$ and $\mathcal {MCA}$ are categorically isomorphic. There is a bijection between the class of all varieties of algebras and the class of all minimal clone algebras:

$$\begin{aligned} \text{ Variety }\,\, {\mathcal {V}} \,\,\text{ of }\,\, \tau \text{-algebras }&\mapsto \text{ Clone } {\mathcal {V}}\text{--algebra } \mathbf {Cl}({\mathcal {V}}) \\ \,\,\text{ Minimal }\,\, \mathsf {CA}_\tau {\mathbf {C}}&\mapsto \,\,\text{ Variety } \,\,\mathrm {Var}({\mathbf {C}}_\tau )\, \text{ generated } \text{ by }\,\, {\mathbf {C}}_\tau . \end{aligned}$$

We have ${\mathcal {V}}= \mathrm {Var}(\mathbf {Cl}({\mathcal {V}})_\tau )$ and ${\mathbf {C}} \cong \mathbf {Cl}(\mathrm {Var}({\mathbf {C}}_\tau ))$. Moreover, there is a bijective correspondence between the sets $\mathrm {Hom}_{\mathcal {VAR}}({\mathcal {V}},{\mathcal {W}})$ of interpretations and the set $\mathrm {Hom}_{\mathcal {CA}}(\mathbf {Cl}({\mathcal {V}}),\mathbf {Cl}({\mathcal {W}}))$ of pure homomorphisms.

Proof

The first part follows from Theorem 6.6. We prove the second part. Let ${\mathcal {V}}$ be a variety of type $\tau$, ${\mathcal {W}}$ be a variety of type $\nu$, ${\mathbf {C}}= \mathbf {Cl}({\mathcal {V}})$ and ${\mathbf {D}}= \mathbf {Cl}({\mathcal {W}})$. We recall that ${\mathbf {C}}_\tau$ is the free ${\mathcal {V}}$-algebra over a countable set of generators. Similarly for ${\mathbf {D}}_\nu$. If f is an interpretation of ${\mathcal {V}}$ into ${\mathcal {W}}$ in category $\mathcal {VAR}$, then $({\mathbf {D}}_\nu )^f$ belongs to ${\mathcal {V}}$ and ${\mathbf {D}}^f = (({\mathbf {D}}_\nu )^f,q_n^{\mathbf {D}},{\mathsf {e}}_i^{\mathbf {D}})$ is a clone $\tau$-algebra. The unique homomorphism $F:{\mathbf {C}}_\tau \rightarrow ({\mathbf {D}}_\nu )^f$ of $\tau$-algebras extending $F({\mathsf {e}}_i^{\mathbf {C}})={\mathsf {e}}_i^{\mathbf {D}}$ is a homomorphism of clone $\tau$-algebras from ${\mathbf {C}}$ into ${\mathbf {D}}^f$. F is also a pure homomorphism from ${\mathbf {C}}$ into ${\mathbf {D}}$.

For the converse, let ${\mathbf {C}}$ be a minimal clone $\tau$-algebra, ${\mathbf {D}}$ be a minimal clone $\nu$-algebra and F be a pure homomorphism from ${\mathbf {C}}$ into ${\mathbf {D}}$. Then, for every n-ary operator $\sigma \in \tau$ ($n > 0$), we define $f(\sigma )$ to be any $\nu$-term $t=t(v_1,\dots ,v_n)$ belonging to $F(\sigma ^{\mathbf {C}}({\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}}))$ (see Proposition 5.3(2)). If $c\in \tau$ is a nullary operator, then we define f(c) to be any $\nu$-term $t=t(v_1)$ belonging to $F(c^{\mathbf {C}})$ (see Proposition 5.3(3)). f is an interpretation from $\mathrm {Var}({\mathbf {C}}_\tau )$ into $\mathrm {Var}({\mathbf {D}}_\nu )$. $\square$

We have shown that $\mathcal {VAR}$ and $\mathcal {MCA}$ are categorically isomorphic, but we claim that $\mathcal {MCA}$ is more manageable than $\mathcal {VAR}$, because methods of universal algebra can be directly applied to $\mathcal {MCA}$. For example, the factorisation of clone algebras through central elements guided the authors to a generalisation of the theorem on independent varieties presented by Grätzer et al. in [7] (see Theorems 6.13 and 6.17).

Given a clone algebra ${\mathbf {C}}$, recall from Definition 5.4 the definition of the type $\rho _{\mathbf {C}}$ and of the clone $\rho _{\mathbf {C}}$-algebra $\overline{R}_{{\mathbf {C}}}$.

Definition 6.12

The categorical product ${\mathbf {C}}\odot {\mathbf {D}}$ of ${\mathbf {C}},{\mathbf {D}}\in \mathcal {MCA}$ is defined as the clone $\rho _{{\mathbf {C}}_0\times {\mathbf {D}}_0}$-algebra $\overline{R}_{{\mathbf {C}}_0\times {\mathbf {D}}_0}$ of all ${\mathbf {C}}_0\times {\mathbf {D}}_0$-representable functions.

${\mathbf {C}}\odot {\mathbf {D}}$ is minimal by Proposition 6.10(i). Moreover, ${\mathbf {C}}\odot {\mathbf {D}}$ is the product of ${\mathbf {C}}$ and ${\mathbf {D}}$ in $\mathcal {MCA}$, because the categories $\mathcal {MCA}$ and $\mathsf {CA}_0$ are equivalent and $({\mathbf {C}}\odot {\mathbf {D}})_0={\mathbf {C}}_0\times {\mathbf {D}}_0$ is the product of ${\mathbf {C}}_0$ and ${\mathbf {D}}_0$ in the variety $\mathsf {CA}_0$ of pure clone algebras. Notice that every minimal clone algebra ${\mathbf {E}}$ such that ${\mathbf {E}}_0={\mathbf {C}}_0\times {\mathbf {D}}_0$ is purely isomorphic to the categorical product ${\mathbf {C}}\odot {\mathbf {D}}$.

Theorems 6.13 and 6.17 below provide necessary and sufficient conditions for the independence of varieties, improving a theorem on independent varieties by Grätzer et al. [7].

Theorem 6.13

Let ${\mathbf {C}}$ and ${\mathbf {D}}$ be minimal $\mathsf {CA}_\tau$s and let ${\mathbf {E}}={\mathbf {C}}\times {\mathbf {D}}$ be the clone $\tau$-algebra that is the product of ${\mathbf {C}}$ and ${\mathbf {D}}$ in the variety $\mathsf {CA}_\tau$. Then the following conditions are equivalent:

• (1) ${\mathbf {E}}$ is minimal.

• (2) The varieties $\mathrm {Var}({\mathbf {C}}_\tau )$ and $\mathrm {Var}({\mathbf {D}}_\tau )$ are independent.

• (3) $\mathrm {Clo}\,{\mathbf {E}}_\tau = R_{{\mathbf {E}}}$, where $R_{{\mathbf {E}}}$ is the clone of the ${\mathbf {E}}$-representable functions and $\mathrm {Clo}\,{\mathbf {E}}_\tau$ is the clone of term operations of the $\tau$-algebra ${\mathbf {E}}_\tau$.

If one of the above equivalent conditions holds, then $\mathrm {Var}({\mathbf {E}}_\tau )=\mathrm {Var}({\mathbf {C}}_\tau )\times \mathrm {Var}({\mathbf {D}}_\tau )=\mathrm {Var}({\mathbf {C}}_\tau )\vee \mathrm {Var}({\mathbf {D}}_\tau )$, where the join $\vee$ is taken in the lattice of subvarieties of $\mathrm {Var}({\mathbf {E}}_\tau )$.

Proof

(1 $\Rightarrow$ 2) Since ${\mathbf {E}}$ is a 2-CH and ${\mathbf {E}}={\mathbf {C}}\times {\mathbf {D}}$, then by Proposition 2.1 and by Proposition 6.2 there exists a 2-central element $c=({\mathsf {e}}_1^{{\mathbf {C}}},{\mathsf {e}}_2^{{\mathbf {D}}})\in E$ of dimension 2 such that ${\mathbf {C}} \cong {\mathbf {E}}/\theta (c,{\mathsf {e}}_1^{\mathbf {E}})$ and ${\mathbf {D}} \cong {\mathbf {E}}/\theta (c,{\mathsf {e}}_2^{\mathbf {E}})$. By Lemma 6.4 and the minimality of ${\mathbf {E}}$ there exists a ground $\tau ({\mathsf {e}})$-term $t=t({\mathsf {e}}_1,{\mathsf {e}}_2)$ such that $c=t^{\mathbf {E}}$. Let $t^*=t^*(v_1,v_2)$ be the $\tau$-term translation of t (defined in Section 6.2). By ${\mathbf {C}} \cong {\mathbf {E}}/\theta (c,{\mathsf {e}}_1^{\mathbf {E}})$ and ${\mathbf {D}} \cong {\mathbf {E}}/\theta (c,{\mathsf {e}}_2^{\mathbf {E}})$ we get $\mathrm {Var}({\mathbf {C}}_\tau ) \models t^*(v_1,v_2)=v_1$ and $\mathrm {Var}({\mathbf {D}}_\tau ) \models t^*(v_1,v_2)=v_2$. Hence, the varieties $\mathrm {Var}({\mathbf {C}}_\tau )$ and $\mathrm {Var}({\mathbf {D}}_\tau )$ are independent.

(2 $\Rightarrow$ 1) Let $t(v_1,v_2)$ be a $\tau$-term such that $\mathrm {Var}({\mathbf {C}}_\tau ) \models t(v_1,v_2)=v_1$ and $\mathrm {Var}({\mathbf {D}}_\tau ) \models t(v_1,v_2)=v_2$. Let $(a,b)\in E$ with $a\in C$ and $b\in D$. Since ${\mathbf {C}}$ and ${\mathbf {D}}$ are minimal, then by Lemma 6.4 there exist two $\tau ({\mathsf {e}})$-terms $u_1$ and $u_2$ such that $a=u_1^{\mathbf {C}}$ and $b=u_2^{\mathbf {D}}$. Then ${\mathbf {E}}$ is minimal, because the pair $(a,b)\in E$ coincides with the interpretation of the $\tau ({\mathsf {e}})$-term $t(u_1,u_2)$.

(1 $\Leftrightarrow$ 3) By Proposition  6.10(ii).

We now prove the last condition. If ${\mathbf {E}}$ is minimal, then by Theorem 6.6${\mathbf {E}}_\tau = {\mathbf {C}}_\tau \times {\mathbf {D}}_\tau$ is the free algebra of the variety $\mathrm {Var}({\mathbf {E}}_\tau )$. Then the decomposition operator $t^*(v_1,v_2)^{{\mathbf {E}}}$ giving the decomposition ${\mathbf {E}} = {\mathbf {C}}\times {\mathbf {D}}$ provides the decomposition $\mathrm {Var}({\mathbf {E}}_\tau )=\mathrm {Var}({\mathbf {C}}_\tau )\times \mathrm {Var}({\mathbf {D}}_\tau )$. $\square$

Remark 6.14

If $\tau$ is a type of unary operators, it is well known that there are no independent varieties of type $\tau$. By Theorem 6.13 the algebra ${\mathbf {E}}={\mathbf {C}}\times {\mathbf {D}}$ is never minimal, because every unary term operation cannot be a nontrivial decomposition operator on ${\mathbf {E}}$.

Definition 6.15

Let ${\mathbf {C}}$ be a clone $\tau$-algebra, ${\mathbf {D}}$ be a clone $\nu$-algebra and $f: {\mathbf {C}}\rightarrow {\mathbf {D}}$ be a pure homomorphism. The f-expansion of ${\mathbf {D}}$ is the clone $\tau$-algebra ${\mathbf {D}}^f=(({\mathbf {D}}_\nu )^f, q_n^{\mathbf {D}}, {\mathsf {e}}_i^{\mathbf {D}})$, where $({\mathbf {D}}_\nu )^f=(D,\sigma ^{{\mathbf {D}}^f})_{\sigma \in \tau }$ and $\sigma ^{{\mathbf {D}}^f}$ ($\sigma \in \tau$ of arity n) is the n-ary operation such that $\sigma ^{{\mathbf {D}}^f}(a_1,\dots ,a_n)= q_n^{\mathbf {D}}(f(\sigma ^{\mathbf {C}}({\mathsf {e}}_1^{\mathbf {C}},\dots ,{\mathsf {e}}_n^{\mathbf {C}})),a_1,\dots ,a_n)$ for every $a_1,\dots ,a_n\in D$.

Lemma 6.16

In the hypotheses of Definition 6.15 we have:

(1) The map $f:C\rightarrow D$ is a homomorphism of $\tau$-algebras from ${\mathbf {C}}$ into ${\mathbf {D}}^f$;

(2) If ${\mathbf {C}}$ is minimal and f is onto, then ${\mathbf {D}}^f$ is also minimal.

Theorem 6.17

Let ${\mathbf {C}}_j = ({\mathbf {C}}_{\tau _j},q_n^{{\mathbf {C}}_j}, {\mathsf {e}}_i^{{\mathbf {C}}_j})$ be a minimal clone $\tau _j$-algebra ($j=1,2$), ${\mathbf {E}}={\mathbf {C}}_1\odot {\mathbf {C}}_2$ be the categorical product in $\mathcal {MCA}$ and $\nu$ be the type of ${\mathbf {E}}$. Then the following conditions hold:

(1) If $\pi _j$ is the projection from ${\mathbf {E}}$ onto ${\mathbf {C}}_j$ ($j=1,2$), then the $\pi _j$-expansion ${\mathbf {C}}_j^{\pi _j}$ of ${\mathbf {C}}_j$ is a minimal clone $\nu$-algebra;

(2) ${\mathbf {C}}_j^{\pi _j}$ is purely isomorphic to ${\mathbf {C}}_j$ ($j=1,2$);

(3) ${\mathbf {E}}={\mathbf {C}}_1^{\pi _1}\times {\mathbf {C}}_2^{\pi _2}$, where the product ${\mathbf {C}}_1^{\pi _1}\times {\mathbf {C}}_2^{\pi _2}$ is taken in the variety $\mathsf {CA}_\nu$;

(4) The varieties $\mathrm {Var}(({\mathbf {C}}_{\tau _1})^{\pi _1})$ and $\mathrm {Var}(({\mathbf {C}}_{\tau _2})^{\pi _2})$ of type $\nu$ are independent;

(5) $\mathrm {Var} ({\mathbf {E}}_\nu )=\mathrm {Var}(({\mathbf {C}}_{\tau _1})^{\pi _1})\times \mathrm {Var}(({\mathbf {C}}_{\tau _2})^{\pi _2})= \mathrm {Var}({\mathbf {C}}_{\tau _1})\odot \mathrm {Var}({\mathbf {C}}_{\tau _2})$.

Proof

(1) By Lemma 6.16(2), because $\pi _j$ is an onto pure homomorphism.

(2) ${\mathbf {C}}_j^{\pi _j}$ and ${\mathbf {C}}_j$ have the same pure reduct.

(3) By Definition 6.12 the pure reduct of ${\mathbf {C}}_1\odot {\mathbf {C}}_2$ is $({\mathbf {C}}_1)_0\times ({\mathbf {C}}_2)_0$. The conclusion follows from the definition of ${\mathbf {C}}_j^{\pi _j}$.

(4) By (3) and Theorem 6.13, because ${\mathbf {C}}_j^{\pi _j}$ is a minimal clone $\nu$-algebra.

(5) By Theorem 6.13 because $\mathcal {MCA}$ and $\mathcal {VAR}$ are isomorphic. $\square$