2.1 Algebras and varieties

Let $A$ be a set and $n$ a non-negative integer. A map from $A^n$ to $A$ is called an $n$ -ary operation on $A$ . A subset of $A^n$ is called an $n$ -ary relation. We say that an $n$ -ary operation $f$ preserves a $k$ -ary relation $R$ if for any

$$ \begin{align*}\begin{gathered} r_1 = (r_{1,1},\dots, r_{1,k}),\dots, r_n=(r_{n,1},\dots, r_{n,k})\in R,\\ f(r_1,\dots, r_n) := (f(r_{1,1},\dots, r_{n,1}),\dots,f(r_{1,k},\dots, r_{n,k}))\in R. \end{gathered} \end{align*} $$

A signature (for algebras) is a set where a non-negative integer is assigned to each element of the set. The elements of a signature are called function symbols. If $f$ is a function symbol and $n$ is assigned to $f$ , then $n$ is called the arity of $f$ . We also say that $f$ is an $n$ -ary function symbol in this case. Let $A$ be a set, and for each function symbol $f$ in a given signature, let $f'$ be an operation of the same arity as $f$ on $A$ . Then the set $A$ with the operations $f'$ is called an algebra in the given signature. The set $A$ is called the base set (or underlying set) of the algebra, and the operations $f'$ are called the basic operations of the algebra. Throughout the article, we use bold face capitals and the same capitals to denote algebras and their base sets, respectively. Usually, we denote the basic operation $f'$ of an algebra $\mathbf {A}$ by $f^{\mathbf {A}}$ for any function symbol $f$ in the signature.

Let $\mathbf {A}$ and $\mathbf {B}$ be two algebras of the same signature. We say that $\mathbf {B}$ is a subalgebra of $\mathbf {A}$ if $B\subseteq A$ , and the basic operations of $\mathbf {A}$ preserve $B$ , and the basic operations of $\mathbf {B}$ are those of $\mathbf {A}$ , restricted to $B$ . Let $C\subseteq A$ . Then the smallest subalgebra that contains $C$ in $\mathbf {A}$ is called the subalgebra generated by $C$ . We say that $C$ generates $\mathbf {A}$ if $\mathbf {A}$ equals the subalgebra generated by $C$ . In this case, $C$ is called a generating set of $\mathbf {A}$ . An algebra is finitely generated if it has a finite generating set.

A map $\nu \colon A\to B$ is a homomorphism from $\mathbf {A}$ to $\mathbf {B}$ if for any function symbol $f$ , say $n$ -ary, and any $a_1,\dots ,a_n\in A$ ,

$$ \begin{align*}\nu(f^{\mathbf{A}}(a_1,\dots,a_n))=f^{\mathbf{B}}(\nu(a_1),\dots,\nu(a_n)).\end{align*} $$

A bijective homomorphism is called an isomorphism. An algebra $\mathbf {B}$ is a homomorphic image of $\mathbf {A}$ if there exists an onto homomorphism from $\mathbf {A}$ to $\mathbf {B}$ . An algebra $\mathbf {A}$ is isomorphic to $\mathbf {B}$ if there exists an isomorphism from $\mathbf {A}$ to $\mathbf {B}$ .

A congruence $\varrho $ of an algebra $\mathbf {A}$ is an equivalence on its base set such that the basic operations of $\mathbf {A}$ preserve $\varrho $ . If $\mathbf {A}$ is an algebra of some signature and $\varrho $ is a congruence of $\mathbf {A}$ , then we define the quotient algebra $\mathbf {A}/\varrho $ of the same signature to be the algebra whose base set is the set of the blocks of $\varrho $ and whose basic operations are defined for any function symbol $f$ , say $n$ -ary, and any $a_1,\dots ,a_n\in A$ by

$$ \begin{align*}f^{\mathbf{A}/\varrho}(a_1/\varrho,\dots ,a_n/\varrho):= f^{\mathbf{A}}(a_1,\dots ,a_n)/\varrho,\end{align*} $$

where for any $a\in A$ , $a/\varrho $ denotes the block of $a$ . Now, it is immediate from the definition that $\mathbf {A}/\varrho $ is a homomorphic image of $\mathbf {A}$ under the homomorphism $a\mapsto ~ a/\varrho $ . It is well-known, cf. Theorem 1.16 in [Reference McKenzie, McNulty and Taylor14], that the kernel of any homomorphism from $\mathbf {A}$ to $\mathbf {B}$ is a congruence of $\mathbf {A}$ and that the homomorphic images of any algebra $\mathbf {A}$ coincide with the quotient algebras of $\mathbf {A}$ up to isomorphism.

Let $\mathbf {A}_i$ , $i\in I$ , be algebras of the same signature. Their product $\prod \limits _{i\in I}\mathbf {A}_i$ is the algebra whose base set equals $\prod \limits _{i\in I}A_i$ and whose basic operations are defined as follows: for any function symbol $f$ , say $n$ -ary,

$$ \begin{align*}f^{\prod\limits_{i\in I}\mathbf{A}_i}((a_{1,i})_{i\in I},\dots, (a_{n,i})_{i\in I}):= (f^{\mathbf{A}_i}(a_{1,i},\dots, a_{n,i}))_{i\in I}.\end{align*} $$

Let $S$ be any set, sometimes called the set of variables. In a given signature, the $S$ -ary terms are the finite sequences of symbols given by the following recursive definition:

1. (1) the elements of $S$ are all $S$ -ary terms;

2. (2) for any function symbol $f$ , say $n$ -ary, and $S$ -ary terms $t_1,\dots , t_n$ , the term $f(t_1,\dots , t_n)$ is also an $S$ -ary term.

Let $\mathbf {A}$ be an algebra and $t$ be an $S$ -ary term in the same signature. Then $t$ determines a map $t^{\mathbf {A}}\colon A^S\to A$ that is called the $S$ -ary term operation related to $t$ in $\mathbf {A}$ and defined recursively as follows:

1. (1) if $t=s$ for some $s\in S$ , then $t^{\mathbf {A}}$ equals the projection to the $s$ -th coordinate;

2. (2) if $t=f(t_1,\dots , t_n)$ for an $n$ -ary function symbol $f$ and $S$ -ary terms $t_1,\dots , t_n$ , then

   $$ \begin{align*}t^{\mathbf{A}}:= f^{\mathbf{A}}(t_1^{\mathbf{A}},\dots, t_n^{\mathbf{A}}).\end{align*} $$

A pair of two $S$ -ary terms put in the form $t=u$ is called an $S$ -ary identity. An algebra $\mathbf {A}$ satisfies $t=u$ if $t^{\mathbf {A}}=u^{\mathbf {A}}$ . Let $\Sigma $ be a set of $S$ -ary identities. An algebra $\mathbf {A}$ satisfies (or is a model of) $\Sigma $ if $\mathbf {A}$ satisfies all the identities in $\Sigma $ .

Birkhoff’s famous theorem in [Reference Birkhoff3] asserts that the varieties are exactly the classes of algebras of the same signature that are closed under product, subalgebra, and homomorphic image of algebras. The variety defined by the set of identities

$$ \begin{align*}\{x\wedge y=y\wedge x,\ (x\wedge y)\wedge z= x\wedge (y\wedge z),\ x\wedge x=x\}\end{align*} $$

in a signature with a single binary operation symbol $\wedge $ plays a major role in the present article. This variety is called the variety of semilattices and denoted by $\mathcal {S}\mathcal {L}$ .

Definition 2.2. Let $S$ be a set, and let $T_S$ denote the set of $S$ -ary terms in a given signature. The term algebra $\mathbf {T}_S$ over $S$ is the algebra with the base set $T_S$ and basic operations defined for every function symbol $f$ , say $n$ -ary, in the signature and every $t_1,\dots , t_n\in T_S$ by

$$ \begin{align*}f^{\mathbf{T}_S}(t_1,\dots, t_n):= f(t_1,\dots, t_n).\end{align*} $$

It is clear from the definition that for any $S'\subseteq S$ , $\mathbf {T}_{S'}$ is a subalgebra of $\mathbf {T}_S$ . Let $\mathcal {V}$ be a variety in a given signature. Then the free algebra $\mathbf {F}_{\mathcal {V}}(S)$ in $\mathcal {V}$ equals the factor algebra $\mathbf {T}_S/\Theta _S$ where $\Theta _S$ is the set of pairs $(t,u)$ for which $\mathcal {V}$ satisfies the $S$ -ary identity $t=u$ . It can be shown that $\Theta _S$ is indeed a congruence of $\mathbf {T}_S$ , and hence, $\mathbf {T}_S/\Theta _S$ is well defined. Clearly, $\mathbf {F}_{\mathcal {V}}(S)\in \mathcal {V}$ also holds. The blocks $s/\Theta _S$ where $s\in S$ generate $\mathbf {F}_{\mathcal {V}}(S)$ . If $\mathcal {V}$ is non-trivial, then these blocks are pairwise different. This set of blocks is called a free generating set of $\mathbf {F}_{\mathcal {V}}(S)$ , since for any two $S$ -ary terms $t$ and $u$ , the identity $t=u$ is satisfied by $\mathcal {V}$ if and only if the values of the term operations $t^{\mathbf {F}_{\mathcal {V}}(S)}$ and $u^{\mathbf {F}_{\mathcal {V}}(S)}$ coincide at the tuple $(s/\Theta _S)_{s\in S}$ . An algebra isomorphic to $\mathbf {F}_{\mathcal {V}}(S)$ is called the free algebra with free generating set $S$ in $\mathcal {V}$ . $\bigstar $

It is useful to conceive of the free algebra with free generating set $S$ in $\mathcal {V}$ in the following two ways:

1. (1) We pick a term from each block of $\Theta _S$ , and we think of the set of these designated $S$ -ary terms as the base set of the free algebra in $\mathcal {V}$ . A basic operation $f$ on this set works like in $\mathbf {T}_S$ , except that any value of $f$ in $\mathbf {T}_S$ is replaced by the designated $S$ -ary term from the $\Theta _S$ -block of the value.

2. (2) We may think of the base set of the free algebra in $\mathcal {V}$ as the set of the $S$ -ary term operations of $\mathbf {F}_{\mathcal {V}}(S)$ . Then the basic operations of $\mathbf {F}_{\mathcal {V}}(S)$ act naturally on the set of the $S$ -ary term operations, which yields the basic operations of the free algebra.

For further topics on varieties, the interested reader may consult [Reference Bergman2, Reference Burris and Sankappanavar5, Reference McKenzie, McNulty and Taylor14].

2.2 Clones and interpretability

A clone on $A$ is a set of finitary operations on $A$ that contains all projection operations and is closed under composition. A clone homomorphism from a clone $\mathscr C$ to a clone $\mathscr D$ is a map from $\mathscr C$ to $\mathscr D$ that maps each projection of $\mathscr C$ to the corresponding projection of $\mathscr D$ and commutes with composition. Let $\mathbf {A}$ be an algebra. The clone of $\mathbf {A}$ denoted by $\mathrm {Clo} (\mathbf {A})$ is the clone of finitary term operations of $\mathbf {A}$ . The clone of a variety $\mathcal {V}$ is the clone of the free algebra with countably infinite free generating set.

There is a way to express interpretation of varieties in terms of subvariety and term reduct: $\mathcal {V}\leq \mathcal {W}$ if and only if there is a variety $\mathcal {V}'$ of the same signature as $\mathcal {V}$ such that $\mathcal {V}'$ is a subvariety of $\mathcal {V}$ and $\mathcal {V}'$ is a term reduct of $\mathcal {W}$ . To verify the “only if” part of the latter statement, let us suppose that $\mathcal {V}\leq \mathcal {W}$ , and that this is witnessed by the clone homomorphism $\alpha $ . Let $\omega $ denote the set of non-negative integers. Then the operations $\alpha (f^{\mathbf {F}_{\mathcal {V}}(\omega )})$ where $f$ runs through the signature of $\mathcal {V}$ yield an algebra $\mathbf {A}$ on the base set of $\mathbf {F}_{\mathcal {W}}(\omega )$ . Since $\alpha $ is a homomorphism, $\mathbf {A}$ satisfies all identities of $\mathcal {V}$ . On the other hand, the $\alpha (f^{\mathbf {F}_{\mathcal {V}}(\omega )})$ are term operations of the free algebra $\mathbf {F}_{\mathcal {W}}(\omega )$ , hence, the set $\Sigma $ of identities given by the $\alpha (f^{\mathbf {F}_{\mathcal {V}}(\omega )})$ is satisfied by each algebra in $\mathcal {W}$ . Since $\Sigma $ contains the identities satisfied by $\mathcal {V}$ , it defines a subvariety $\mathcal {V}'$ of $\mathcal {V}$ . Clearly, $\mathcal {V}'$ also is a term reduct of $\mathcal {W}$ . The “if” part of the statement also holds, since any variety interprets in each of its subvarieties, and any term reduct of a variety $\mathcal {W}$ interprets in $\mathcal {W}$ .

For an example of an interpretation, we consider two varieties. Let $\mathcal {S}\mathcal {E}\mathcal {T}$ be the variety of sets, the variety defined by the empty set of identities in the empty signature. Let $\mathcal {S}\mathcal {G}$ be the variety of semigroups, the variety defined by the single identity $(xy)z=x(yz)$ in the signature of one binary operation symbol. Clearly, there is a clone homomorphism from the clone of $\mathcal {S}\mathcal {E}\mathcal {T}$ to the clone of $\mathcal {S}\mathcal {G}$ , mapping the projections to the corresponding projections. So, $\mathcal {S}\mathcal {E}\mathcal {T}\leq \mathcal {S}\mathcal {G}$ . On the other hand, there is also a clone homomorphism from the clone of $\mathcal {S}\mathcal {G}$ to the clone of $\mathcal {S}\mathcal {E}\mathcal {T}$ , mapping the product operation to the projection to the first coordinate. Thus, $ \mathcal {S}\mathcal {G}\leq \mathcal {S}\mathcal {E}\mathcal {T}$ also holds. Hence, by the definition just follows, $\mathcal {S}\mathcal {E}\mathcal {T}$ and $ \mathcal {S}\mathcal {G}$ have the same interpretability type.

Definition 2.4. As easily seen, interpretability is a quasiorder on the class of varieties. The blocks of this quasiorder are called interpretability types. By following [Reference Garcia and Taylor7], we define the lattice $\boldsymbol{\mathcal {L}}$ of interpretability types of varieties that is obtained by taking the quotient of the class of varieties quasiordered by interpretability and the related equivalence.

The join in $\boldsymbol{\mathcal {L}}$ is described as follows. Let $\mathcal {V}_1$ and $\mathcal {V}_2$ be two varieties of disjoint signatures. Let $\mathcal {V}_1$ and $\mathcal {V}_2$ be defined by the sets $\Sigma _1$ and $\Sigma _2$ of identities, respectively. Their join $\mathcal {V}_1\vee \mathcal {V}_2$ is the variety defined by the set of identities $\Sigma _1\cup \Sigma _2$ in the signature that equals the union of the signatures $\mathcal {V}_1$ and $\mathcal {V}_2$ . The so defined join is compatible with the interpretability relation of varieties, and naturally yields the join operation in $\boldsymbol{\mathcal {L}}$ .

In this article, the meet operation of $\boldsymbol{\mathcal {L}}$ is not used, but for completeness we describe it. The meet $\mathcal {V}\wedge \mathcal {W}$ of varieties $\mathcal {V}$ and $\mathcal {W}$ has the signature $\cup _{n=0}^\infty T_n\times S_n$ where $T_n$ and $S_n$ are the sets of $n$ -ary terms of $\mathcal {V}$ and $\mathcal {W}$ , respectively. For any $\mathbf {A}\in \mathcal {V}$ and $\mathbf {B}\in \mathcal {W}$ , we define an algebra $\mathbf {C}$ with base set $A\times B$ where for any $(s,t)\in T_n\times S_n$ , $a_1,\dots ,a_n\in A$ , and $b_1,\dots ,b_n\in B$

$$ \begin{align*}(s,t)^{\mathbf{C}}((a_1,b_1),\dots,(a_n,b_n))= (s^{\mathbf{A}}(a_1,\dots,a_n), t^{\mathbf{B}}(b_1,\dots,b_n)).\end{align*} $$

Now, $\mathcal {V}\wedge \mathcal {W}$ is the variety that consists of the isomorphic copies of the so defined algebras $\mathbf {C}$ . The meet of varieties is compatible with the interpretability relation of varieties, and naturally yields the meet operation in $\boldsymbol{\mathcal {L}}$ . $\bigstar $

We note that the interpretability types of varieties actually form a proper class. Also, $\boldsymbol{\mathcal {L}}$ has a smallest and a largest element. The smallest element of $\boldsymbol{\mathcal {L}}$ is the interpretability type of the variety of sets. The largest element of $\boldsymbol{\mathcal {L}}$ is the interpretability type that contains the trivial varieties.

A filter is proper if it is non-empty and it differs from the whole lattice. A proper filter $F$ in a lattice is called prime if for any two elements $a,b\not \in F$ , we have $a\vee b\not \in F$ . To gain information on the structural properties of $\boldsymbol{\mathcal {L}}$ , it is useful to determine which of the well-known classical Maltsev filters are prime filters in $\boldsymbol{\mathcal {L}}$ . In case a Maltsev filter is (not) prime, we just say sometimes that the related Maltsev condition is (not) prime.

2.3 Hobby–McKenzie varieties

Let $A$ be a set. An $n$ -ary operation $f$ on $A$ is idempotent if $f(a,\dots ,a)=a$ for all $a\in A$ . An algebra is idempotent if its all basic operations are idempotent. An $n$ -ary term $t$ of a variety $\mathcal {V}$ is called an idempotent term if $\mathcal {V}$ satisfies the identity $t(x,\dots ,x)=x$ . A variety $\mathcal {V}$ is idempotent if all algebras in the variety are idempotent, or equivalently, for all $n$ , all $n$ -ary terms of $\mathcal {V}$ are idempotent.

In a lattice, a filter is called a principal filter if it consists of all elements that are greater than or equal to some element of the lattice. Clearly, any strong Maltsev filter is a principal filter in $\boldsymbol{\mathcal {L}}$ . On the other hand, any Maltsev filter that is a principal filter is easily seen to be a strong Maltsev filter. In [Reference Kozik, Krokhin, Valeriote and Willard13], it was shown that there is no strong Maltsev condition that characterizes the class of Hobby–McKenzie varieties. In other words, the Hobby–McKenzie filter is not a strong Maltsev filter or, equivalently, it is not a principal filter in $\boldsymbol{\mathcal {L}}$ .

The full idempotent reduct of a variety $\mathcal {V}$ is the variety whose signature is the set of idempotent terms of $\mathcal {V}$ , and whose identities are those satisfied by $\mathcal {V}$ for its idempotent terms. Let $\mathcal {V}_{\mathrm {Id}}$ denote the full idempotent reduct of $\mathcal {V}$ . We require the following characterization of Hobby–McKenzie varieties.

By the use of the preceding theorem, it follows that if $\mathcal {V}_1$ and $\mathcal {V}_2$ are idempotent non-Hobby–McKenzie varieties, then they both interpret in $\mathcal {S}\mathcal {L}$ . So, their join also interprets in $\mathcal {S}\mathcal {L}$ . Hence, in the sublattice of interpretability types of idempotent varieties, the filter of the types of idempotent Hobby–McKenzie varieties is prime. The main result of this article states that we can drop idempotency from this statement, that is, the Hobby–McKenzie filter is prime in $\boldsymbol{\mathcal {L}}$ .

2.4 Relational structures and connectivity

A signature (for relational structures) is a set where a non-negative integer is assigned to each element of the set. The elements of a signature are called relation symbols. If $R$ is a relation symbol and $n$ is assigned to $R$ , then $n$ is called the arity of $R$ . We also say that $R$ is an $n$ -ary relation symbol in this case. Let $G$ be a set, and for each relation symbol $R$ in a given signature, let $R'$ be a relation of the same arity as $R$ on $G$ . Then the set $G$ with the relations $R'$ is called a relational structure in the given signature. The set $G$ is called the base set of the relational structure. Throughout the article, we use blackboard bold capitals and the same capitals to denote relational structures and their base sets, respectively. For any relation symbol $R$ in the signature of a relational structure $\mathbb {G}$ , we denote the corresponding relation $R'$ of $\mathbb {G}$ by $R^{\mathbb {G}}$ . On some occasions, though, we leave off the superscript to ease up notation.

A map $\varphi \colon G\to H$ is called a homomorphism from $\mathbb {G}$ to $\mathbb {H}$ if $\varphi $ maps any tuple of any relation of $\mathbb {G}$ to a tuple of the corresponding relation of $\mathbb {H}$ . If $\varphi $ is a homomorphism from $\mathbb {G}$ to $\mathbb {H}$ , we also say that $\varphi $ preserves the relations of $\mathbb {G}$ . For a homomorphism $\varphi \colon \mathbb {G}\to \mathbb {H}$ , we denote by $\varphi (\mathbb {G})$ the relational structure whose base set is $\varphi (G)$ and whose relations are the images of the relations of $\mathbb {G}$ under $\varphi $ . We say that $\mathbb {H}$ is a weak substructure of $\mathbb {G}$ if every element of $\mathbb {H}$ is an element of $\mathbb {G}$ and every tuple of a relation of $\mathbb {H}$ is in the corresponding relation of $\mathbb {G}$ . We use $\mathbb {H}\subseteq \mathbb {G}$ to denote that $\mathbb {H}$ is a weak substructure of $\mathbb {G}$ . For example, $\varphi (\mathbb {G})\subseteq \mathbb {H}$ for any homomorphism $\varphi \colon \mathbb {G}\to \mathbb {H}$ . We call $\mathbb {H}$ a substructure of $\mathbb {G}$ , if $\mathbb {H}\subseteq \mathbb {G}$ and every relation of $\mathbb {H}$ coincides with the restriction of the corresponding relation of $\mathbb {G}$ to $H$ .

A homomorphism $\alpha \colon \mathbb {G} \to \mathbb {H}$ is a retraction if there is a homomorphism $\beta \colon \mathbb {H} \to ~\mathbb {G}$ such that $\alpha \beta $ coincides with the identity map on $H$ . Then the homomorphism $\beta $ is called a coretraction and the structure $\mathbb {H}$ is called a retract of $\mathbb {G}$ . A bijective retraction is called an isomorphism. The structures $\mathbb {G}$ and $\mathbb {H}$ are isomorphic if there exists an isomorphism from $\mathbb {G}$ to $\mathbb {H}$ . We remark that if $\mathbb {H}$ is a retract of $\mathbb {G}$ with a coretraction $\beta $ , then $\beta (\mathbb {H})$ is a substructure isomorphic to $\mathbb {H}$ in $\mathbb {G}$ .

Let $\varrho $ be an equivalence of a relational structure $\mathbb {G}$ . We define the quotient structure $\mathbb {G}/\varrho $ of the same signature as $\mathbb {G}$ to be the relational structure whose base set is the set of the blocks of $\varrho $ , and for any relational symbol $R$ , $R^{\mathbb {G}/\varrho }$ consists of the tuples $r/\varrho $ where $r\in R^{\mathbb {G}}$ and each component of $r/\varrho $ is the block of the related component of $r$ . We note that the map $a \mapsto a/\varrho $ is a homomorphism from $\mathbb {G}$ to $\mathbb {G}/\varrho $ . Moreover, for any homomorphism $\varphi \colon \mathbb {G}\to \mathbb {H}$ , $\varphi (\mathbb {G})$ is isomorphic to $\mathbb {G}/\ker (\varphi )$ where $\ker (\varphi )$ denotes the kernel of $\varphi $ .

Let $I$ be an arbitrary set, and let $\mathbb {H}_i$ be relational structures of the same signature where $i\in I$ . The disjoint union $\dot \bigcup _{i\in I}\mathbb {H}_i$ of the $\mathbb {H}_i$ is the relational structure of the same signature as the $\mathbb {H}_i$ , $i\in I$ , whose base set is the disjoint union of the base sets $H_i$ , $i\in I$ , and whose relations are the disjoint unions of the corresponding relations of the $\mathbb {H}_i$ , $i\in I$ . The product $\prod \limits _{i\in I}\mathbb {H}_i$ of the $\mathbb {H}_i$ is the relational structure of the same signature as the $\mathbb {H}_i$ , $i\in I$ , whose base set equals $\prod \limits _{i\in I} H_i$ and whose relations are defined as follows: for any relation symbol $R$ , say $k$ -ary,

$$ \begin{align*}((h_{1,i})_{i\in I},\dots, (h_{k,i})_{i\in I})\in R^{\prod\limits_{i\in I} \mathbb{H}_i}\text{ iff } (h_{1,i},\dots, h_{k,i})\in R^{\mathbb{H}_i} \text{ for all }{i\in I}.\end{align*} $$

The $I$ -th power $\mathbb {H}^I$ of $\mathbb {H}$ is defined to be the relational structure $\prod \limits _{i\in I}\mathbb {H}_i$ where $\mathbb {H}_i=\mathbb {H}$ for all $i\in I$ . A homomorphism from $\mathbb {H}^n$ to $\mathbb {H}$ is called an $n$ -ary polymorphism of $\mathbb {H}$ . We note that the polymorphisms of $\mathbb {H}$ coincide with the finitary operations of $H$ that preserve the relations of $\mathbb {H}$ . Let $\mathrm {Pol}(\mathbb {H})$ denote the clone of polymorphisms of $\mathbb {H}$ .

It is easy to see that a relational structure $\mathbb {G}$ is compatible in a variety $\mathcal {V}$ if and only if there is a clone homomorphism from $\mathrm {Clo}(\mathcal {V})$ to $\mathrm {Pol}(\mathbb {G})$ . Hence, if $\mathcal {V}\leq \mathcal {W}$ and $\mathbb {G}$ is compatible in $\mathcal {W}$ , then $\mathbb {G}$ is also compatible in $\mathcal {V}$ .

We also have that if $\mathbb {G}$ is compatible in the varieties $\mathcal {V}_1$ and $\mathcal {V}_2$ of disjoint signatures, then $\mathbb {G}$ is compatible in $\mathcal {V}_1\vee \mathcal {V}_2$ as well. Indeed, the premise gives that for $1\leq i\leq 2$ , there exist $\mathbf {A}_i\in \mathcal {V}_i$ such that $A_i=G$ and the basic operations of $\mathbf {A}_i$ preserve the relations of $\mathbb {G}$ . Now, let $\mathbf {B}$ denote the algebra on $G$ with basic operations $f_i^{\mathbf {A}_i}$ for any $1\leq i\leq 2$ where $f_i$ is an arbitrary function symbol in the signature of $\mathcal {V}_i$ . Then $\mathbf {B}\in \mathcal {V}_1\vee \mathcal {V}_2$ and $\mathbb {G}$ is compatible in $\mathbf {B}$ , and hence, in $\mathcal {V}_1\vee \mathcal {V}_2$ as well.

Now we introduce a notion of connectivity for relational structures, and then, we shall prove a related lemma that will be frequently used in the later sections.

Definition 2.10. We define the binary projection $\mathbb {B}$ of a relational structure $\mathbb {G}$ as follows: $\mathbb {B}$ is a binary relational structure on $G$ such that the signature of $\mathbb {B}$ consists of the binary relational symbols $R_{i,j}$ where $R$ is a $k$ -ary relational symbol in the signature of $\mathbb {G}$ and $1\leq i<j \leq k$ , and the relations of $\mathbb {B}$ are the

$$ \begin{align*}R_{i,j}^{\mathbb{B}}=\{(a_i, a_j)\colon (a_1, \dots, a_k) \in R^{\mathbb{G}}\}.\end{align*} $$

We note that $\mathrm {Pol}(\mathbb {G})\subseteq \mathrm {Pol}(\mathbb {B})$ . An oriented path of $\mathbb {B}$ is a sequence of elements $b_0\dots ,b_t$ in $B$ where for all $0\leq s\leq t-1$ either $(b_s,b_{s+1})$ or $(b_{s+1},b_s)$ is in some relation of $\mathbb {B}$ . We define the connectivity equivalence $\alpha $ of a relational structure $\mathbb {G}$ by

$$ \begin{align*}(a,b)\in \alpha\text{ if and only if there is an oriented path from } a\text{ to }b\text{ in }\mathbb{B}.\end{align*} $$

It is easy to see that $\alpha $ indeed is an equivalence on $G$ . The blocks of the connectivity equivalence are called the (connected) components of $\mathbb {G}$ . Clearly, every relational structure $\mathbb {G}$ may be regarded as the disjoint union of its components. We say that $\mathbb {G}$ is connected if it has precisely one component. Clearly, if $\mathbb {G}$ is connected, then for any homomorphism $\alpha \colon \mathbb {G}\to \mathbb {H}$ , $\alpha (\mathbb {G})$ is also connected. $\bigstar $

A relation on $G$ is called reflexive if it contains all of the constant tuples of $G$ . A relational structure is reflexive if all of its relations are reflexive. Clearly, if $\mathbb {G}$ is reflexive, then its binary projection $\mathbb {B}$ is reflexive, and for any homomorphism $\alpha \colon \mathbb {G}\to \mathbb {H}$ , $\alpha (\mathbb {G})$ is also reflexive. We require the following lemma on connectivity of reflexive structures.

We note that if $K$ is a finite set of finite reflexive connected relational structures, then by item (3) of the lemma, $K$ satisfies the conditions of items (4) and (5).