We assign a relational structure to any finite algebra in a canonical way, using solution sets of equations, and we prove that this relational structure is polymorphism-homogeneous if and only if the algebra itself is polymorphism-homogeneous. We show that polymorphism-homogeneity is also equivalent to the property that algebraic sets (i.e., solution sets of systems of equations) are exactly those sets of tuples that are closed under the centralizer clone of the algebra. Furthermore, we prove that the aforementioned properties hold if and only if the algebra is injective in the category of its finite subpowers. We also consider two additional conditions: a stronger variant for polymorphismhomogeneity and for injectivity, and we describe explicitly the finite semilattices, lattices, Abelian groups and monounary algebras satisfying any one of these three conditions.
We study polymorphism-homogeneity of finite algebraic structures and of certain relational structures constructed from algebras. Since homomorphisms depend on the term operations, not on the particular choice of basic operations, we work mainly with the clone C = Clo(A) of term operations of the algebraic structure A = (A, F ) (i.e., C is the clone generated by F ; see Section 2.1). An n-ary operation f : An ! A can be regarded as an (n + 1)-ary relation, called the graph of f , denoted by f • (see Section 2.3). Probably the most natural way to convert A into a relational structure is to consider the graphs of the operations of A, thus we define C• = {f • : f 2 C} to be the set of graphs of term operations of A. We will prove that if the relational structure (A, C•) is polymorphism-homogeneous, then the algebra A is also polymorphism-homogeneous, but the converse is not true in general.
To construct a relational structure that is equivalent to A in terms of polymorphism-homogeneity, observe that the relation f • is nothing else than the solution set of the equation f (x1, . . . , xn) = xn+1. We might consider more (A, C•) is polymorphismhomogeneous (A, C ) is polymorphismhomogeneous
homogeneous
general equations where the right hand side is not necessarily a single variable: let C be the set of solution sets of equations of the form f (x1, . . . , xn) = g(x1, . . . , xn), where f, g 2 C. It turns out that (A, C ) is the “right” choice for a relational counterpart of A: the algebra A is polymorphism-homogeneous if and only if the relational structure (A, C ) is polymorphism-homogeneous.
The elements of C are solution sets of single equations, hence intersections of such sets are solution sets of systems of
equations. The latter are also called algebraic sets, as they are analogues of algebraic varieties1 investigated in algebraic
geometry; the study of these sets can thus be regarded as universal algebraic geometry [
A k-ary partial operation on A is a map h : dom h ! A, where the domain of h can be any set dom h ✓ of all partial operations on A is denoted by PA, and the set of all k-ary partial operations on A is denoted by PA(k). A strong partial clone is a set of partial operations that is closed under composition, contains the projections, and contains all restrictions of its members to arbitrary subsets of their domains. Note that if C ✓ O A is a clone, then the least strong Ak. The set 1Note that the word variety has a different meaning in universal algebra: a variety is an equationally definable class of algebras, or, equivalently, a class of algebras that is closed under homomorphic images, subalgebras and direct products. partial clone Str(C) containing C consists of all restrictions of elements of C, i.e., h 2 PA belongs to Str(C) if and only if h can be extended to a total operation bh 2 C.
An n-ary relation on A is a subset of An; the set of all relations (of arbitrary arities) on A is denoted by RA. Given a set of relations R ✓ R A, a primitive positive formula ( x1, . . . , xn) over R is an existentially quantified conjunction: t ¯ i=1 ( x1, . . . , xn) = 9 y1 · · · 9 ym ⇢ i z1(i), . . . , zr(ii) , (2.1) where ⇢ i 2 R is a relation of arity ri, and each zj(i) is a variable from the set {x1, . . . , xn, y1, . . . , ym} for i = 1, . . . , t, j = 1, . . . , ri. The relation ⇢ = {(a1, . . . , an) : ( a1, . . . , an) is true} ✓ An is then said to be defined by the primitive positive formula . The set of all primitive positive definable relations over R is denoted by hRi9 , and such sets of relations are called relational clones. If we allow only quantifier-free primitive positive formulas, then we obtain the weak relational clone hRi@. 2.2
Galois connections between operations and relations We say that a k-ary (partial) operation h preserves the relation ⇢ ✓ An, denoted as h B ⇢ , if for every matrix M 2 An⇥ k such that each column of M belongs to ⇢ (and each row of M is in the domain of h), applying h to each row of M , we obtain a column that also belongs to ⇢ . If R is a set of relations, then we write h B R to indicate that h preserves all elements of R. In other words, h B R holds if and only if h is a (partial) polymorphism of the relational structure A = (A, R), i.e., h is a homomorphism from (the substructure dom h of) Ak to A. The set of all (partial) operations preserving each relation of R is denoted by Pol R (pPol R), and the set of all relations preserved by each member of a set F of (partial) operations is denoted by Inv F :
Pol R = pPol R = h 2 OA : h B ⇢ for every ⇢ 2 R ; h 2 PA : h B ⇢ for every ⇢ 2 R ;
Inv F = ⇢ 2 RA : h B ⇢ for every h 2 F .
Note that Pol R = pPol R \ O A.
The closed sets under the Galois connection Pol Inv (pPol Inv) between (partial) operations and relations are exactly the (strong partial) clones and the (weak) relational clones; this makes these Galois connections fundamental tools in clone theory.
Theorem 2.1 ([
Universal algebraic geometry and centralizers Let A be a finite algebra and let C = Clo(A). If f and g are n-ary term operations of A, then f (x1, . . . , xn) = g(x1, . . . , xn) is an equation in n variables over A, which we may simply write as a pair (f, g). The solution set of (f, g) is then the set Sol(f, g) = {(a1, . . . , an) 2 An : f (a1, . . . , an) = g(a1, . . . , an)}. Of special interest are the equations of the form f (x1, . . . , xn) = xn+1; the solution set of this equation is the (n + 1)-ary relation f • = {(a1, . . . , an, an+1) 2 An+1 : f (a1, . . . , an) = an+1)}, which is called the graph of f . We use the symbols C• and C for the set of graphs and for the set of all solution sets of equations over C:
C• = f • : f 2 C ; C =
Sol(f, g) : f, g 2 C(n), n 2 N .
Note that C• ✓ C , and it is easy to verify that hC•i9 = hC i9 (see Lemma 3.2 of [
The members of hC i@ are intersections of solution sets of finitely many equations, i.e., hC i@ consists of solution sets
of finite systems of equations over A. Allowing infinite systems of equations, we obtain the so-called algebraic sets,
which are the main objects of study in universal algebraic geometry [
As mentioned in Section 1, basic results of linear algebra hint at the possibility that algebraic sets can sometimes be
described by closure conditions. It turns out that if there is a clone D such that algebraic sets are exactly those sets of
tuples that are closed under D, then D must be the clone C⇤ = Pol C• (see Corollary 3.7 in [
Polymorphism-homogeneity
A first-order structure A (i.e., a set A equipped with relations and/or operations) is said to be
k-polymorphismhomogeneous, if every homomorphism h : B ! A defined on a finitely generated substructure B A k extends to a
homomorphism bh : Ak ! A. (As usual, a substructure B is said to be finitely generated if there is a finite set S ✓ A
such that B is the smallest substructure of A that contains S. Considering only finite structures, the assumption that B is
finitely generated can be omitted from the definition.) The case k = 1 gives the notion of homomorphism-homogeneity
introduced by P. J. Cameron and J. Nešetrˇil [
Proposition 2.2 ([
In the next proposition we recall a useful result from [
Proposition 2.3 ([
Proof. A finite relational structure A = (A, R) has quantifier elimination for primitive positive formulas if and only if hRi@ = hRi9 . Using the Galois connections Pol Inv (clones and relational clones) and pPol Inv (strong partial clones and weak relational clones), we can reformulate this condition in several steps to reach polymorphismhomogeneity: () () () { () A
Inv pPol R = Inv Pol R pPol Inv pPol R = pPol Inv Pol R pPol R = Str(Pol R) h 2 PA : h B R} = {h 2 PA : h extends to bh 2 OA such that bh B R}
is polymorphism-homogeneous.
Let K be a class of algebras and A 2 K. We say that A is injective in K if every homomorphism h : B ! A extends to
a homomorphism bh : C ! A whenever B, C 2 K and B C. Clearly, if A is injective in K, then A is also injective in
every subclass of K that contains A. Injectivity is most often considered in the largest relevant class K; for example,
if A is a group or a lattice, then K is usually chosen to be the class of all groups or lattices. In this paper we shall
consider smaller classes, namely the variety HSP A generated by A and the set of finite subpowers SPfin A of A (the
latter consists of all subalgebras of finite direct powers of A). Let us mention that in [
Polymorphism-homogeneity, algebraic sets and injectivity First let us prove the equivalences shown on the right hand side of Figure 1. The equivalence of property (SDC) and polymorphism-homogeneity of (A, C ) follows immediately from Proposition 2.3.
Proposition 3.1. If A is a finite algebra and C = Clo(A), then A has property (SDC) if and only if (A, C ) is polymorphism-homogeneous.
Proof. By Theorem 3.6 of [
Our main result is the following theorem that establishes the connection between “algebraic” and “relational” polymorphism-homogeneity (for the proof, see the extended version of the present paper at arXiv:2007.04405). Theorem 3.2. If A is a finite algebra and C = Clo(A), then A is polymorphism-homogeneous if and only if (A, C ) is polymorphism-homogeneous.
To complete the proof of the equivalences in the box on the right hand side of Figure 1, we relate injectivity and polymorphism-homogeneity.
Proposition 3.3. If A is a finite algebra, then A is polymorphism-homogeneous if and only if A is injective in SPfin(A). Proof. Assume that A is polymorphism-homogeneous, and let B, C 2 SPfin(A) such that B C. Then we have B C Ak for some k 2 N; in particular, B is a subalgebra of Ak. Therefore, if h : B ! A is a homomorphism, then h extends to a homomorphism bh : Ak ! A by the polymorphism-homogeneity of A. A restriction of bh then gives a homomorphism form C to A that extends h, thereby proving the injectivity of A.
(k) is a homomorphism from a subalgebra dom h Ak to A, then the Conversely, if A is injective in SPfin(A) and h 2 PA injectivity of A immediately yields an extension bh : Ak ! A of h, thus A is indeed polymorphism-homogeneous. Corollary 3.4. If A is a finite algebra and C = Clo(A), then the following conditions are equivalent: (i) A has property (SDC); (ii) A is polymorphism-homogeneous; (iii) (A, C ) is polymorphism-homogeneous; (iv) A is injective in SPfin(A).
It remains to verify the “one-way” implications in Figure 1. Since HSP(A) ◆ SPfin(A), it is trivial that if A is injective in HSP(A), then it is also injective in SPfin(A). We end this section by proving the remaining implication; in fact, we formulate it in a bit more explicit form, which will be useful in the next section.
Proposition 3.5. If A is a finite algebra and C = Clo(A), then (A, C•) is polymorphism-homogeneous if and only if (A, C ) is polymorphism-homogeneous and hC•i@ = hC i@.
Proof. According to Proposition 2.3, we need to prove the following equivalence:
We describe explicitly the finite algebras satisfying the properties considered in the previous section in certain well known varieties: semilattices, lattices, Abelian groups and monounary algebras. These characterizations will provide counterexamples showing that the only valid implications among these properties are the ones shown in Figure 1. If we consider finite semilattices, then it turns out that five of the six conditions of Figure 1 are equivalent, and these semilattices have already been determined in the literature.
Theorem 4.1. If A is a finite semilattice and C = Clo(A), then the following conditions are equivalent:
Proof. We know that conditions (i)–(iv) are equivalent (see Corollary 3.4), and it was proved in Theorem 5.5 of [
The top left condition of Figure 1 is not equivalent to the others; in fact, there is no nontrivial finite semilattice for which (A, C•) is polymorphism-homogeneous.
Lemma 4.2. Let A be a two-element semilattice and let C = Clo(A). Then the relational structure (A, C•) is not polymorphism-homogeneous.
Proof. We can assume without loss of generality that A = ({0, 1}, ^ ) with the usual ordering 0 < 1. Let us consider the equation x ^ y ^ z = x ^ y. Obviously, the solution set S = {0, 1}3 \ {(1, 1, 0)} of this equation is defined by a quantifier-free primitive positive formula over C . The nontrivial 3-variable equalities that can appear in a quantifier-free primitive positive formula over C• are the following: x = y, y = z, z = x, x = x ^ y, y = x ^ y, z = x ^ y, x = x ^ z, y = x ^ z, z = x ^ z, x = y ^ z, y = y ^ z, z = y ^ z, x = x ^ y ^ z, y = x ^ y ^ z, z = x ^ y ^ z.
It is easy to check that S does not satisfy any of the equalities above; therefore, S cannot be defined by a quantifier-free primitive positive formula over C•. Thus S belongs to hC i@ but not to hC•i@, hence (A, C•) is not polymorphismhomogeneous by Proposition 3.5.
Theorem 4.3. If A is a nontrivial finite semilattice and C = Clo(A), then the relational structure (A, C•) is not polymorphism-homogeneous.
Proof. Let a, b 2 A such that a < b, and let us consider the same equation as in the proof of Lemma 4.2. Now for the solution set S of this equation we have that S \ { a, b}3 = {a, b}3 \ {(b, b, a)}. The same argument as in the proof of Lemma 4.2 shows that S cannot be defined by a quantifier-free primitive positive formula over C•. For finite lattices the situation is very similar to the case of semilattices: five of the six conditions of Figure 1 are equivalent, and the sixth one is satisfied only by trivial lattices.
Theorem 4.4. If A is a finite lattice and C = Clo(A), then the following conditions are equivalent:
Proof. Just as in the proof of Theorem 4.1, the equivalence of (i)–(iv) follows from Corollary 3.4, (v) trivially implies
(iv), and the equivalence of (i) and (vi) is Theorem 4.8 of [
Lemma 4.5. Let A be a two-element lattice and let C = Clo(A). Then the relational structure (A, C•) is not polymorphism-homogeneous.
Proof. We can assume without loss of generality that A = ({0, 1}, _ , ^ ) with the usual ordering 0 < 1. Let us consider the equation (x1 _ x2) ^ (x3 ^ x4) = x3 ^ x4; the solution set S = {0, 1}4 \ {(0, 0, 1, 1)} of this equation is defined by a quantifier-free primitive positive formula over C . If S can be defined by a quantifier-free primitive positive formula over C•, then we can assume without loss of generality that consists of a single equality, as S misses only one element of {0, 1}4 (in other words, S is meet-irreducible in the lattice of subsets of {0, 1}4). Thus S is the solution set of an equation of the form f (x1, x2, x3, x4) = u, where u 2 {x1, x2, x3, x4}. Note that since f is generated by the lattice operations _ and ^ , it is a monotone function. We consider four cases corresponding to the variable u. 1. If u = x1, then f (x1, x2, x3, x4) = x1 holds for all (x1, x2, x3, x4) 2 S and f (0, 0, 1, 1) = 1. In particular, we have f (0, 1, 1, 1) = 0 < 1 = f (0, 0, 1, 1), contradicting the monotonicity of f . 2. If u = x2, then f (x1, x2, x3, x4) = x2 holds for all (x1, x2, x3, x4) 2 S and f (0, 0, 1, 1) = 1. In particular, we have f (1, 0, 1, 1) = 0 < 1 = f (0, 0, 1, 1), contradicting the monotonicity of f . 3. If u = x3, then f (x1, x2, x3, x4) = x3 holds for all (x1, x2, x3, x4) 2 S and f (0, 0, 1, 1) = 0. In particular, we have f (0, 0, 1, 0) = 1 > 0 = f (0, 0, 1, 1), contradicting the monotonicity of f . 4. If u = x4, then f (x1, x2, x3, x4) = x4 holds for all (x1, x2, x3, x4) 2 S and f (0, 0, 1, 1) = 0. In particular, we have f (0, 0, 0, 1) = 1 < 0 = f (0, 0, 1, 1), contradicting the monotonicity of f .
thus (A, C•) is not polymorphism-homogeneous by Proposition 3.5. Theorem 4.6. If A is a nontrivial finite lattice and C = Clo(A), then the relational structure (A, C•) is not polymorphism-homogeneous.
Proof. Let a, b 2 A such that a < b, and let us consider the same equation as in the proof of Lemma 4.5. Now for the solution set S of this equation we have that S \ { a, b}4 = {a, b}4 \ {(a, a, b, b)}. If S can be defined by a quantifier-free primitive positive formula over C•, then at least one of the equalities in defines the set {a, b}4 \ {(a, a, b, b)} when restricted to the sublattice {a, b}, and this leads to a contradiction using the same argument as in the proof of Lemma 4.5. For Abelian groups all six conditions of Figure 1 are equivalent, and these groups have already been determined, so we only need to combine some results from the literature to prove the following theorem.
Theorem 4.7. If A is a finite Abelian group and C = Clo(A), then the following conditions are equivalent: (viii) each Sylow-subgroup of A is homocyclic, i.e., A ⇠= Zqm11 ⇥ · · · ⇥ primes and m1, . . . , mk 2 N.
Zqmkk , where q1, . . . , qk are powers of different
Proof. Conditions (i), (iii), (iv) and (vi) are equivalent by Corollary 3.4. By Proposition 3.5, (iv) is equivalent to (v),
since we have hC•i@ = hC i@ for groups: every equality can be written in an equivalent form where there is only a
single variable on the right hand side. The equivalence of (ii) and (viii) follows from the description of quasi-injective
Abelian groups presented as an exercise in [
Monounary algebras
A monounary algebra is an algebra A = (A, f ) with a single unary operation f 2 OA(1). An element a 2 A is cyclic if
there is a natural number k such that f k(a) = a. (Here f k(a) stands for f (· · · f (a) · · · ) with a k-fold repetition of f ,
and we also use the convention f 0(a) = a.) If A is finite, then for every element a 2 A there is a least nonnegative
integer ht(a), called the height of a, such that f ht(a)(a) is cyclic. If a 2 A \ f (A), i.e., a has no preimage, then we say
that a is a source. (Note that ht(a) = 0 if and only if a is cyclic; in particular, ht(a) 1 for any source a.)
Polymorphism-homogeneous monounary algebras were characterized by Z. Farkasová and D. Jakubíková-Studenovská
in [
Theorem 4.8 ([
Next we determine finite monounary algebras corresponding to the top left box of Figure 1.
Theorem 4.9. Let A = (A, f ) be a finite monounary algebra, and let C = Clo(A). Then the relational structure (A, C•) is polymorphism-homogeneous if and only if f is either bijective or constant.
Proof. If f is constant, then it is clear that (A, C•) is polymorphism-homogeneous. Assume now that f is bijective. Then the condition of Theorem 4.8 is satisfied (there are no sources at all), so A is polymorphism-homogeneous, and thus by Theorem 3.2 (A, C ) is polymorphism-homogeneous as well. Therefore, by Proposition 3.5, it suffices to show that hC i@ = hC•i@. This is clear, as any equality of the form f k(x) = f `(y) with k < ` is equivalent to x = f ` k(y), since f is bijective (here x and y might be the same variable).
For the other direction, let us suppose that (A, C•) is polymorphism-homogeneous. By Proposition 3.5, (A, C ) is also polymorphism-homogeneous, and then Theorem 4.8 (together with Theorem 3.2) implies that either there are no sources, or there is an integer n 1 such that every source in A has height n. If there are no sources in A, then every element is cyclic, and therefore f is bijective. From now on let us suppose that A has sources with a common height n. Proposition 3.5 shows that there exists a quantifier-free primitive positive formula ( x, y) over C• such that ( x, y) is equivalent to f (x) = f (y). We can write ( x, y) in the following form:
t ¯ i=1 ( x, y) = f ri (ui) = vi , where t, ri are nonnegative integers, and ui, vi 2 {x, y} for i = 1, . . . , t. Obviously, ( a, a) holds for every element a 2 A. Let us choose a to be of height n, i.e., let a be a source. Then f ri (ui) = vi holds for ui = vi = a if and only if ri = 0, thus ( x, y) is equivalent either to x = y or to x = x. Taking into account that ( x, y) is also equivalent to f (x) = f (y), we can conclude that f (x) = f (y) () x = y or f (x) = f (y) () x = x. In the first case f is a bijection, and in the second case f is constant.
Injective objects in the category of all monounary algebras were determined by D. Jakubíková-Studenovská [
Theorem 4.10 ([
Let us note that comparing theorems 4.8, 4.9 and 4.10, one can construct examples illustrating each one of the “non-implications” of Figure 1.
The authors are grateful to Dragan Mašulovic´ and Christian Pech for helpful discussions.
This research was partially supported by the National Research, Development and Innovation Office of Hungary under grants K115518 and K128042 and by grant TUDFO/47138-1/2019-ITM of the Ministry for Innovation and Technology, Hungary.