1 Introduction

To every algebraic structure \({\mathbf {A}}\), one can associate certain subsets of its finite direct powers \({\mathbf {A}}^n\) (\(n \in {\mathbb {N}}\)). For example, the relational clone of \({\mathbf {A}}\) consists of all subuniverses of these direct powers. Two algebras defined on the same base set A, but possibly with different basic operations, may have the same relational clone: if A is finite, this happens if and only if the two algebras are term equivalent, i.e., each fundamental operation of one algebra is a term operation of the other algebra [8, p. 55, Folgerung 1.2.4]. Universal algebraic geometry associates with \({\mathbf {A}}\) all solution sets S of (possibly infinite) systems of algebraic equations of the form \(S = \{ (a_1, \ldots , a_n) \in A^n \mid f_i (a_1, \ldots , a_n) = g_i (a_1, \ldots , a_n) \text { for all } i \in I\}\), where \(f_i, g_i\) are term operations from \({\mathbf {A}}\). We will call such a solution set S an algebraic set. Following Pinus [6, p. 501], two algebras defined on the same base set A are called algebraically equivalent if they have the same algebraic sets. An algebra is called an equational domain if for all \(n \in {\mathbb {N}}\) and all algebraic subsets S, T of \(A^n\), the union \(S \cup T\) is again algebraic. Using a description of algebraic equivalence through certain invariants, Pinus proved that on a finite set, there are at most finitely many algebraically inequivalent equational domains [6, Theorem 3]. In the present note, we observe that this finiteness can also be obtained by considering the clonoid of the characteristic functions of algebraic sets and applying a consequence of the Baker Pixley Theorem [2, Theorem 2.1] that was recently proved by Sparks [9, Theorem 2.1] to these clonoids.

2 Definable sets

We note that the solutions of a term equation \(s(x_1, \ldots , x_n) = t (x_1, \ldots , x_n)\) in n variables over the algebra \({\mathbf {A}}\) can be written in the form

$$\begin{aligned} S = \{ (a_1, \ldots , a_n) \in A^n \mid {\mathbf {A}} \models \varphi (a_1, \ldots , a_n)\}, \end{aligned}$$

where \(\varphi \) is a logical formula of the form \(s \approx t\) with free variables \(x_1, \ldots , x_n\), and \(\varphi (a_1, \ldots , a_n)\) is the interpretation of this formula in \({\mathbf {A}}\) with the variable assignment \(x_i \mapsto a_i\). We put this into a more flexible frame allowing for arbitrary first order structures with both functional and relational symbols. By a first order formula, we always understand a formula in first order logic with equality, denoted by \(\approx \), over the set of variables \(\{x_i \mid i \in {\mathbb {N}}\}\).

Definition 2.1

Let \({\mathbf {A}}=(A, (f_{i})_{i\in I}, (\rho _{j})_{j\in J})\) be a first order structure, let \(\Phi \) be a set of first order formulas in the language of \({\mathbf {A}}\), let \(n \in {\mathbb {N}}\), and let \(B \subseteq A^n\). B is called \(\Phi \)-definable if there is a formula \(\varphi \in \Phi \) whose free variables are all contained in \(\{x_{1},\dots , x_{n}\}\) such that

$$\begin{aligned} B= \{(a_{1},\dots ,a_{n})\in A^{n} \mid {\mathbf {A}}\models \varphi (a_{1},\dots ,a_{n})\}. \end{aligned}$$

We define \({{\,\mathrm{Def}\,}}^{[n]}({\mathbf {A}},\Phi )\) to be the set of all \(\Phi \)-definable subsets of \(A^{n}\), and we set \({{\,\mathrm{Def}\,}}({\mathbf {A}},\Phi ):= \bigcup _{n \in {\mathbb {N}}} {{\,\mathrm{Def}\,}}^{[n]}({\mathbf {A}},\Phi )\).

For example, given a finite relational structure \({\mathbf {A}} = ( {A}, {(\rho _i)_{i \in I}} )\), and taking \(\Phi \) to be the set of primitive positive formulas in the language of \({\mathbf {A}}\) (allowing also the the binary equality symbol \(\approx \)), \({{\,\mathrm{Def}\,}}({\mathbf {A}}, \Phi )\) is the relational clone generated by \(\{\rho _i \mid i \in I\}\) [8, Hauptsatz 2.1.3(i)]. Other examples for the operator \({{\,\mathrm{Def}\,}}\) come from Universal Algebraic Geometry (cf. [3, 5]). Let \({\mathbf {A}}=( {A}, {(f_i)_{i \in I}} )\) be a finite algebraic structure, and let \(\Phi \) consist of all (finite) conjunctions of atomic formulas in the language of \({\mathbf {A}}\). Then each formula in \(\Phi \) is of the form \(\bigwedge _{i=1}^m s_i (x_1, \ldots , x_n) \approx t_i (x_1, \ldots , x_n)\), where \(m, n \in {\mathbb {N}}\) and all \(s_i\) and \(t_i\) are terms in the language of \({\mathbf {A}}\), and hence \({{\,\mathrm{Def}\,}}({\mathbf {A}},\Phi )\) consists of all algebraic sets of \({\mathbf {A}}\). Another collection of finitary relations on an algebra \({\mathbf {A}}\) that can be expressed in this setting is the \(L_0\)-logical geometry of \({\mathbf {A}}\), which was studied, e.g., in [7]. This \(L_0\)-logical geometry is \({{\,\mathrm{Def}\,}}({\mathbf {A}}, \Phi ')\), where \(\Phi '\) is the set of all quantifier free formulas of \({\mathbf {A}}\). Two algebras \({\mathbf {A}}_1\) and \({\mathbf {A}}_2\) defined on the same universe are called \(L_0\)-logically equivalent if \({{\,\mathrm{Def}\,}}({\mathbf {A}}_{1}, \Phi _1') = {{\,\mathrm{Def}\,}}({\mathbf {A}}_{2}, \Phi _2')\), where \(\Phi _i'\) is the set of quantifier free formulas in the language of \({\mathbf {A}}_i\).

All sets of formulas that we have considered so far were closed under taking minors. To define this concept, we use the operation of substitution as defined in [4, Definition 8.2]. We call a first order formula \(\varphi \) a minor of the formula \(\varphi '\) if there is an \(n \in {\mathbb {N}}\) and a mapping \(\sigma : \{1,\ldots , n\} \rightarrow {\mathbb {N}}\) such that \(\varphi = \varphi '\frac{x_{\sigma (1)},\dots ,x_{\sigma (n)}}{x_{1},\dots , x_{n}}\); roughly speaking, \(\varphi \) is the result of substituting the free occurrences of \(x_1, \ldots , x_n\) in \(\varphi '\) simultaneously by \(x_{\sigma (1)}, \ldots , x_{\sigma (n)}\), sometimes denoted by \(\varphi = \varphi ' (x_{\sigma (1)}, \ldots , x_{\sigma (n)})\). The precise definition of the substitution operation in  [4] also takes care of substituting bound variables. For our purpose, it will be sufficient to know that for every structure \({\mathbf {A}}\) and for all \(a_1,\ldots ,a_n \in A\), \(\varphi ^{{\mathbf {A}}} (a_1,\ldots , a_n)\) is equivalent to \({\varphi '}^{{\mathbf {A}}} (a_{\sigma (1)}, \ldots , a_{\sigma (n)})\) [4, p. 65, Substitutions lemma 8.3]. A function \(f:A^{m}\rightarrow B\) is a minor of the function \(f':A^{n}\rightarrow B\) if there exists \(\sigma :\{1,\dots ,n\}\rightarrow \{1,\dots , m\}\) such that \(f(x_{1},\dots ,x_{m})=f'(x_{\sigma (1)},\dots ,x_{\sigma (n)})\) for all \(x_1, \ldots , x_m \in A\). Finally, a set \(B\subseteq A^{m}\) is a minor of the set \(B'\subseteq A^{n}\) if there exists \(\sigma :\{1,\dots ,n\}\rightarrow \{1,\dots , m\}\) such that \(B=\{ (a_{1},\dots ,a_{m})\in A^{m}\mid (a_{\sigma (1)},\dots ,a_{\sigma (n)})\in B'\}\). We say that a subset \({\mathcal {R}}\) of the set \(\bigcup _{n \in {\mathbb {N}}} {\mathcal {P}} (A^n)\) of all finitary relations on A is closed under finite intersections if for all \(m \in {\mathbb {N}}\) and for all \(S, T \subseteq A^m\) with \(S \in {\mathcal {R}}\) and \(T \in {\mathcal {R}}\), we have \(S \cap T \in {\mathcal {R}}\); being closed under finite unions is defined similarly. Using the substitution lemma for first order logic [4, Substitutionslemma 8.3], we obtain:

Proposition 2.2

Let \({\mathbf {A}}\) be a first order structure, and let \(\Phi \) be a set of first order formulas in its language closed under \(\wedge \), \(\vee \), and taking minors of formulas. Then \({{\,\mathrm{Def}\,}}({\mathbf {A}},\Phi )\) is closed under finite intersections, finite unions, and taking minors of sets.

For a subset T of \(A^n\), we define its characteristic function \({\mathbf {1}}_{T}:A^{n}\rightarrow \{0,1\}\) by \({\mathbf {1}}_T (x_1, \ldots , x_n) = 1\) if \((x_1, \ldots , x_n) \in T\), and \({\mathbf {1}}_T (x_1, \ldots , x_n) = 0\) if \((x_1, \ldots , x_n) \not \in T\). Let A be a set, and let \({\mathbf {B}}\) be an algebra. Following [1], a subset C of \(\bigcup _{n \in {\mathbb {N}}} B^{A^n}\) is called a clonoid from A to \({\mathbf {B}}\) if C is closed under taking minors of functions, and for every \(k \in {\mathbb {N}}\), the set \(C^{[k]} := C \cap B^{A^k}\) is a subuniverse of \({\mathbf {B}}^{A^k}\). If a set S is a minor of the set T, then its characteristic function \({\mathbf {1}}_S\) is a minor of the function \({\mathbf {1}}_T\). Hence we have:

Proposition 2.3

Let A be a finite set, and let \({\mathcal {R}}\) be a set of finitary relations on A that is closed under finite intersections, finite unions, and under taking minors of sets. Then the set \(C({\mathcal {R}}):=\{{\mathbf {1}}_{T}\mid T\in {\mathcal {R}}\}\) is a clonoid from A to the two element lattice \((\{0,1\},\wedge ,\vee )\).

We call \(C({\mathcal {R}})\) the characteristic clonoid of \({\mathcal {R}}\).

3 Recovering definable sets from those of bounded arity

Our main tool is a consequence of A. Sparks’s description of clonoids from a finite set into an algebra with a near-unanimity term. We note that a lattice has the near-unanimity (or majority) term \((x \wedge y) \vee (x \wedge z) \vee (y \wedge z)\), and hence as a consequence of [9, Theorem 2.1], a clonoid from a finite set A into the two element lattice is generated by its \(|A|^2\)-ary members.

Lemma 3.1

([9, Theorem 2.1]). Let A be a finite set, let \({\mathbf {B}} := (\{0,1\},\wedge , \vee )\) be the two element lattice, and let C, D be two clonoids from A to \({\mathbf {B}}\). Then \(C=D\) if and only if \(C^{[\,|A|^{2}\,]}=D^{[\,|A|^{2}\,]}\).

We apply this result to the characteristic clonoids of some \(\Phi \)-definable sets and obtain:

Theorem 3.2

Let \({\mathbf {A}}_{1}\) and \({\mathbf {A}}_{2}\) be two first order structures on a finite set A. For each \(i \in \{1,2\}\), let \(\Phi _{i}\) be a set of first order formulas in the language of \({\mathbf {A}}_{i}\) that is closed under \(\wedge \), \(\vee \), and taking minors of formulas. Then \({{\,\mathrm{Def}\,}}({\mathbf {A}}_{1},\Phi _{1})={{\,\mathrm{Def}\,}}({\mathbf {A}}_{2},\Phi _{2})\) if and only if \({{\,\mathrm{Def}\,}}^{[\,|A|^{2}\,]} ({\mathbf {A}}_{1},\Phi _{1})={{\,\mathrm{Def}\,}}^{[\,|A|^{2}\,]} ({\mathbf {A}}_{2},\Phi _{2})\).

Proof

Let \({\mathcal {R}}:={{\,\mathrm{Def}\,}}({\mathbf {A}}_{1},\Phi _{1})\) and \({\mathcal {S}}:={{\,\mathrm{Def}\,}}({\mathbf {A}}_{2},\Phi _{2})\). By Proposition 2.2, \({\mathcal {R}}\) and \({\mathcal {S}}\) are closed under finite intersections, finite unions, and taking minors of sets. Therefore, by Proposition 2.3, their characteristic clonoids \(C ({\mathcal {R}})\) and \(C({\mathcal {S}})\) are clonoids from A into the two element lattice. Clearly, \({\mathcal {R}}={\mathcal {S}}\) if and only if \(C({\mathcal {R}})=C({\mathcal {S}})\). By Lemma 3.1, the last equality holds if and only if \(C({\mathcal {R}})^{[\,|A|^{2}\,]}=C({\mathcal {S}})^{[\,|A|^{2}\,]}\), which is equivalent to \({{\,\mathrm{Def}\,}}^{[\,|A|^{2}\,]} ({\mathbf {A}}_1, \Phi _1) = {{\,\mathrm{Def}\,}}^{[\,|A|^{2}\,]} ({\mathbf {A}}_2, \Phi _2)\). \(\square \)

From this result, it follows that an arbitrary set of formulas closed under \(\wedge , \vee \), and taking minors can sometimes be replaced by a set of equal “expressive power” that consists only of disjunctions of conjunctions of atomic formulas:

Corollary 3.3

Let \({\mathbf {A}}\) be a finite first order structure, let \(\Phi \) be a set of first order formulas in the language of \({\mathbf {A}}\) that is closed under \(\wedge \), \(\vee \), and taking minors, and let \(m := |A|^2\). We choose a finite set I and a family \((S_i)_{i \in I}\) of subsets of \(A^m\) such that \(\{S_{i}\mid i\in I\} = {{\,\mathrm{Def}\,}}^{[m]}({\mathbf {A}},\Phi )\), and we let \((\sigma _{i})_{i\in I}\) be a family of relational symbols of arity m. For each \(i \in I\), let \(\sigma _i^{{\mathbf {A}}'} := S_i\), and let \({\mathbf {A}}'\) be the relational structure \(( {A}, {(\sigma _{i}^{{\mathbf {A}}'})_{i\in I}} )\). Let \(\Psi \) be the closure of \(\{\sigma _{i} (x_1,\ldots , x_m) \mid i\in I\}\) under taking minors of formulas, \(\wedge \), and \(\vee \). Then \( {{\,\mathrm{Def}\,}}({\mathbf {A}},\Phi )={{\,\mathrm{Def}\,}}({\mathbf {A}}', \Psi ). \)

Proof

We first show

$$\begin{aligned} {{\,\mathrm{Def}\,}}^{[m]} ({\mathbf {A}}', \Psi ) = \{S_i \mid i \in I\}. \end{aligned}$$
(3.1)

For \(\supseteq \), we observe that \(S_i\) is definable by the formula \(\sigma _i (x_1,\ldots , x_m)\). For \(\subseteq \), we choose a set \(T \subseteq A^m\) that is definable by \(\psi \in \Psi \) with free variables \(x_1, \ldots , x_m\). Then \(\psi \) is equivalent to a formula

$$\begin{aligned} \psi ' = \bigwedge _{k \in K} \bigvee _{l \in L} \sigma _{i (k,l)} (x_{\tau (k,l,1)},\ldots , x_{\tau (k,l,m)}) \end{aligned}$$

with \(i(k,l) \in I\) and \(\tau (k,l,r) \in \{1,\ldots , m\}\) for all \(k \in K\), \(l \in L\), and \(r \in \{1,\ldots , m\}\). For each \(i \in I\), \(S_i \in {{\,\mathrm{Def}\,}}^{[m]} ({\mathbf {A}}, \Phi )\), and therefore there is a formula \(\varphi _i \in \Phi \) such that \(S_i\) is definable by \(\varphi _i\). Now

$$\begin{aligned} \varphi ' := \bigwedge _{k \in K} \bigvee _{l \in L} \varphi _{i (k,l)} (x_{\tau (k,l,1)},\ldots , x_{\tau (k,l,m)}) \end{aligned}$$

is a formula in \(\Phi \) that defines T. Hence \(T \in {{\,\mathrm{Def}\,}}^{[m]} ({\mathbf {A}}, \Phi ) = \{S_i \mid i \in I\}\), which completes the proof of (3.1). Therefore \({{\,\mathrm{Def}\,}}^{[m]} ({\mathbf {A}}', \Psi ) = {{\,\mathrm{Def}\,}}^{[m]} ({\mathbf {A}}, \Phi )\). Applying Theorem 3.2 to \({\mathbf {A}}_1 := {\mathbf {A}}\), \(\Phi _1 := \Phi \), \({\mathbf {A}}_2 := {\mathbf {A}}'\), \(\Phi _2 := \Psi \), we obtain \({{\,\mathrm{Def}\,}}({\mathbf {A}},\Phi )={{\,\mathrm{Def}\,}}({\mathbf {A}}', \Psi )\). \(\square \)

4 Inequivalent algebras

Some of the finiteness results from universal algebraic geometry from [6, 7] can be viewed as consequences of Theorem 3.2. Let \({\mathbf {A}}\) be an algebraic structure. It is easy to see the the set of first order formulas consisting of all primitive positive formulas and the set of all finite conjunctions of atomic formulas in the language of \({\mathbf {A}}\) are both closed under \(\wedge \) and taking minors, but not under \(\vee \). Therefore it is impossible to apply Theorem 3.2 to all relational clones or to the algebraic geometry of every finite universal algebra. Hence we first restrict ourselves to equational domains; in these algebras, the union of two algebraic sets is again algebraic. For example, every field is an equational domain.

Corollary 4.1

([6, Theorem 3]). Let A be a finite set, and let \(({\mathbf {A}}_i)_{i \in I}\) be a family of pairwise algebraically inequivalent equational domains with universe A. Then I is finite.

Proof

Let \(m := |A|^2\). For each \(i \in I\), we let \(\Phi _i\) be the set of finite conjunctions of atomic formulas of \({\mathbf {A}}_i\), and we let \(\Phi _i'\) be the smallest set of formulas that contains \(\Phi _i\) and is closed under \(\wedge \) and \(\vee \). Since \({\mathbf {A}}_{i}\) is an equational domain, we can use induction on the number of \(\vee \) in a formula \(\varphi ' \in \Phi _i'\) to show that the subset defined by \(\varphi '\) is algebraic and hence lies in \({{\,\mathrm{Def}\,}}({\mathbf {A}}_{i}, \Phi _i)\). Hence \({{\,\mathrm{Def}\,}}({\mathbf {A}}_{i}, \Phi _i) = {{\,\mathrm{Def}\,}}({\mathbf {A}}_{i}, \Phi _i')\). We will now show that the mapping \(\alpha : I \rightarrow {\mathcal {P}} ({\mathcal {P}} (A^m))\), \(\alpha (i) := {{\,\mathrm{Def}\,}}^{[m]} ({\mathbf {A}}_{i}, \Phi _i')\), is injective. Suppose \(i,j \in I\) are such that \(\alpha (i) = \alpha (j)\). Then \({{\,\mathrm{Def}\,}}^{[m]} ({\mathbf {A}}_{i}, \Phi _i') = {{\,\mathrm{Def}\,}}^{[m]} ({\mathbf {A}}_{j}, \Phi _j')\), and thus by Theorem 3.2, \({{\,\mathrm{Def}\,}}({\mathbf {A}}_{i}, \Phi _i') = {{\,\mathrm{Def}\,}}({\mathbf {A}}_{j}, \Phi _j')\), which implies \({{\,\mathrm{Def}\,}}({\mathbf {A}}_{i}, \Phi _i) = {{\,\mathrm{Def}\,}}({\mathbf {A}}_{j}, \Phi _j)\). Hence \({\mathbf {A}}_i\) and \({\mathbf {A}}_j\) are algebraically equivalent, which implies \(i = j\). Thus \(\alpha \) is injective, and therefore \(I \le 2^{2^{|A|^{|A|^2}}}\). \(\square \)

The set of first order formulas consisting of all quantifier free formulas is closed under \(\wedge \), \(\vee \), and taking minors. Hence from Theorem 3.2, we also obtain:

Corollary 4.2

([7, Theorem 1]). The number of pairwise \(L_0\)-logically inequivalent algebras on a finite set A is finite.