P OLYMORPHISM - HOMOGENEITY AND UNIVERSAL ALGEBRAIC GEOMETRY Endre Tóth Tamás Waldhauser Bolyai Institute Bolyai Institute University of Szeged University of Szeged Aradi vértanúk tere 1 Aradi vértanúk tere 1 H–6720 Szeged, Hungary H–6720 Szeged, Hungary tothendre@math.u-szeged.hu twaldha@math.u-szeged.hu Dedicated to Maurice Pouzet on the occasion of his 75th birthday. A BSTRACT 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 polymorphism- homogeneity and for injectivity, and we describe explicitly the finite semilattices, lattices, Abelian groups and monounary algebras satisfying any one of these three conditions. Keywords Polymorphism-homogeneity · Algebraic set · Universal algebraic geometry · Solution set of a system of equations · Injective algebra 1 Introduction Various notions of homogeneity appear in several areas of mathematics, such as model theory, group theory, combi- natorics, etc. Roughly speaking, a structure A is said to be homogeneous if certain kinds of local morphisms (i.e., morphisms defined on “small” substructures of A) extend to endomorphisms of A. Specifying the kind of morphisms that are expected to be extendible, one can define many different versions of homogeneity. We consider a variant called polymorphism-homogeneity introduced by C. Pech and M. Pech [1] that involves “multivariable” homomorphisms: we require extendibility of homomorphisms defined on finitely generated substructures of direct powers of A (see Section 2.4 for the precise definition). 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 Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). (A, C • ) is polymorphism- (A, C ) is polymorphism- A is polymorphism- homogeneous homogeneous homogeneous A is injective in HSP(A) A is injective in SPfin (A) A has property (SDC) Figure 1: Relationships between property (SDC) and several variants of polymorphism-homogeneity and injectivity. 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 [2]. Motivated by the fact that a set of vectors over a field is the solution set of a system of (homogeneous) linear equations if and only if it is closed under affine linear combinations (all linear combinations), we investigated the possibility of characterizing algebraic sets by means of closure conditions in [3, 4]. If algebraic sets over A are exactly those sets of tuples that are closed under a suitably chosen set of operations, then we say that A has property (SDC) (see Section 2.3 for an explanation). We will see that this property is equivalent to polymorphism-homogeneity of (A, C ) and of A. The categorical notion of injectivity also asks for extensions of certain homomorphisms, so it is not surprising that a finite algebra A is polymorphism-homogeneous if and only if it is injective in a certain class of algebras, namely in the class of finite subpowers of A (see Section 2.5 for the definitions). Perhaps it is more natural to consider injectivity in the variety HSP A generated by A, hence we will also investigate the relationship between this notion and polymorphism-homogeneity. Figure 1 shows the six properties that we are concerned with in this paper. In Section 3 we prove all the implications and equivalences indicated in the figure. It turns out that for finite algebras four of the six conditions are equivalent, thus we have actually three different properties marked by the three boxes. In Section 4 we determine finite semilattices, lattices, Abelian groups and monounary algebras possessing these three properties, and these examples will justify all of the “non-implications” in Figure 1. 2 Preliminaries 2.1 Clones and relational clones (n) Let OA denote the set of all n-ary operations on a set A (i.e., maps f : An ! A), and let OA be the set of all operations of arbitrary finite arities on A. In this paper we will always assume that the set A on which we consider operations and relations is finite. A set C ✓ OA of operations is a clone if C is closed under composition and contains the projections (n) (x1 , . . . , xn ) 7! xi for 1  i  n. We use the symbol C (n) for the n-ary part of C, i.e., C (n) = C \ OA . The clone generated by F ✓ OA is the least clone Clo(F ) containing F . This is nothing else but the clone of term operations of the algebra A = (A, F ), hence we will also use the notation Clo(A) for this clone. 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 ✓ Ak . The set (k) 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 . 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 ✓ OA is a clone, then the least strong 1 Note 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 b h 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 ✓ RA , a primitive positive formula (x1 , . . . , xn ) over R is an existentially quantified conjunction: t̄ (i) (x1 , . . . , xn ) = 9y1 · · · 9ym ⇢i z1 , . . . , zr(i) i , (2.1) i=1 (i) where ⇢i 2 R is a relation of arity ri , and each zj 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 = h 2 OA : h B ⇢ for every ⇢ 2 R ; pPol 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 \ OA . 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 ([5, 6, 7]). For any set of operations F ✓ OA and any set of relations R ✓ RA , we have Clo(F ) = Pol Inv F and hRi9 = Inv Pol R. For any set of partial operations F ✓ PA and any set of relations R ✓ RA , we have Str(F ) = pPol Inv F and hRi@ = Inv pPol R. 2.3 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 [3]), but in general hC • i@ and hC i@ may be different weak relational clones. 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 [2]. Since we deal only with finite algebras, every system of equations is equivalent to a finite system of equations, thus the elements of hC i@ are exactly the algebraic sets. 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 [3]). This clone is called the centralizer of C, since it consists of those operations that commute with every member of C; in other words, a k-ary operation h belongs to C ⇤ if and only if h is a homomorphism from Ak to A. (Observe that since hC • i9 = hC i9 , the centralizer can equivalently be defined as C ⇤ = Pol C , by Theorem 2.1.) If the algebraic sets (i.e., solution sets of systems of equations) of A coincide with the C ⇤ -closed sets of tuples, then we say that the algebra A has property (SDC); this abbreviation stands for “Solution sets are Definable by closure under the Centralizer”. We proved in [4] that every two-element algebra has this property, and in [3] finite semilattices and lattices with property (SDC) were characterized (see Sections 4.1 and 4.2). In general, property (SDC) is easily seen to be equivalent to the condition hC i9 = hC i@ , i.e., the algebra A has property (SDC) if and only if quantifiers can be eliminated from primitive positive formulas over C (see Theorem 3.6 of [3]). 2.4 Polymorphism-homogeneity A first-order structure A (i.e., a set A equipped with relations and/or operations) is said to be k-polymorphism- homogeneous, if every homomorphism h : B ! A defined on a finitely generated substructure B  Ak extends to a homomorphism b h : 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šetřil [8]. If A is k-polymorphism-homogeneous for every natural number k, then we say that A is polymorphism-homogeneous [1]. These two notions are linked by the following result, which was proved for relational structures by C. Pech and M. Pech [1] and for algebraic structures by Z. Farkasová and D. Jakubíková-Studenovská [9], but the same proof works for arbitrary first-order structures. Proposition 2.2 ([1, 9]). A first-order structure A is polymorphism-homogeneous if and only if Ak is homomorphism- homogeneous for all natural numbers k. In the next proposition we recall a useful result from [1] that relates polymorphism-homogeneity and quantifier elimination for finite relational structures; we give a short proof utilizing the Galois connections between (partial) operations and relations. Proposition 2.3 ([1]). A finite relational structure has quantifier elimination for primitive positive formulas if and only if it is polymorphism-homogeneous. 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 polymorphism- homogeneity: hRi@ = hRi9 () 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 b h 2 OA such that b h B R} () A is polymorphism-homogeneous. 2.5 Injectivity 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 b h : 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 [10] a group A is called relatively injective if it is injective in the variety HSP A. 3 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 [3], property (SDC) of A is equivalent to quantifier elimination for primitive positive formulas for the relational structure (A, C ), and the latter is equivalent to polymorphism-homogeneity of (A, C ) by Proposition 2.3. 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 b h : Ak ! A by the polymorphism-homogeneity of A. A restriction of b h then gives a homomorphism form C to A that extends h, thereby proving the injectivity of A. (k) Conversely, if A is injective in SPfin (A) and h 2 PA is a homomorphism from a subalgebra dom h  Ak to A, then the injectivity of A immediately yields an extension b h : 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). Proof. Combine propositions 3.1 and 3.3 and Theorem 3.2. 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: hC • i@ = hC • i9 () hC i@ = hC i9 and hC • i@ = hC i@ . This follows immediately from the following chain of containments (the last containment is Lemma 3.2 of [3], the others are trivial): hC • i@ ✓ hC i@ ✓ hC i9 = hC • i9 . 4 Examples 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. 4.1 Semilattices 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: (i) A has property (SDC); (ii) A is polymorphism-homogeneous; (iii) (A, C ) is polymorphism-homogeneous; (iv) A is injective in SPfin (A); (v) A is injective in HSP(A); (vi) A is the semilattice reduct of a finite distributive lattice. Proof. We know that conditions (i)–(iv) are equivalent (see Corollary 3.4), and it was proved in Theorem 5.5 of [3] that (i) is equivalent to (vi). G. Bruns and H. Lakser [11] and, independently, A. Horn and N. Kimura [12] showed that the injective objects in the category of semilattices are the semilattice reducts of completely distributive lattices. Therefore, if A is the semilattice reduct of a finite distributive lattice, then A is injective in the variety of all semilattices, thus A is also injective in HSP(A). This proves that (vi) implies (v), and taking into account that (v) obviously implies (iv), the proof is complete. 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, x = x ^ y, x = x ^ z, x = y ^ z, x = x ^ y ^ z, y = z, y = x ^ y, y = x ^ z, y = y ^ z, y = x ^ y ^ z, z = x, z = x ^ y, z = x ^ z, z = 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 polymorphism- homogeneous 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 • . 4.2 Lattices 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: (i) A has property (SDC); (ii) A is polymorphism-homogeneous; (iii) (A, C ) is polymorphism-homogeneous; (iv) A is injective in SPfin (A); (v) A is injective in HSP(A); (vi) A is a finite Boolean lattice (i.e., a direct power of the two-element chain). 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 [3]. (Let us mention that I. Dolinka and D. Mašulović [13] proved that a finite lattice is homomorphism-homogeneous if and only if it is a chain or a Boolean lattice. This together with Proposition 2.2 can also be used to prove that (ii) and (vi) are equivalent.) To complete the proof, it suffices to prove that (vi) implies (v). This follows immediately from a result of R. Balbes [14]: the injective objects in the category of distributive lattices are the complete Boolean lattices (observe that if A is a nontrivial Boolean lattice, then HSP(A) is the variety of distributive lattices). 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 . We see that S cannot be defined by a quantifier-free primitive positive formula over C • , hence hC i@ 6= hC • i@ , and 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. 4.3 Abelian groups 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: (i) A has property (SDC); (ii) A is homomorphism-homogeneous; (iii) A is polymorphism-homogeneous; (iv) (A, C ) is polymorphism-homogeneous; (v) (A, C • ) is polymorphism-homogeneous; (vi) A is injective in SPfin (A); (vii) A is injective in HSP(A); (viii) each Sylow-subgroup of A is homocyclic, i.e., A ⇠ q1 ⇥ · · · ⇥ Zqk , where q1 , . . . , qk are powers of different = Zm 1 mk primes and m1 , . . . , mk 2 N. 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 [15] (for finite groups quasi-injectivity is equivalent to homomorphism- homogeneity). The class of groups given in (viii) is closed under taking finite direct powers, so we can conclude with the help of Proposition 2.2 that (iii) and (viii) are equivalent. It seems to be a folklore fact that the injective members of the variety of Abelian groups defined by the identity nx = 0 with n = q1 · . . . · qk are exactly the groups given by (viii) (see, e.g., [16]). Therefore, (viii) implies (vii), and this completes the proof, as (vii) trivially implies (vi). 4.4 Monounary algebras (1) A monounary algebra is an algebra A = (A, f ) with a single unary operation f 2 OA . 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 [9] using Proposition 2.2 and the description of homomorphism-homogeneous monounary algebras obtained by É. Jungábel and D. Mašulović [17]. Theorem 4.8 ([9]). If A = (A, f ) is a finite monounary 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); (v) Either A has no sources, or all sources of A have the same height: 8a, b 2 A \ f (A) : ht(a) = ht(b). Proof. Conditions (i)–(iv) are equivalent by Corollary 3.4, and the equivalence of (ii) and (v) follows from Theorem 5 of [17] and Theorem 4.3 of [9], specialized to finite monounary algebras. 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̄ (x, y) = f ri (ui ) = vi , i=1 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á [18]; in the finite case these are exactly the monounary algebras A = (A, f ) where f is bijective and has a fixed point. However, in order to complete the picture of Figure 1 for monounary algebras, we need to describe those monounary algebras A that are injective in the variety HSP A. This has been done by D. Jakubíková-Studenovská and G. Czédli, but this result appeared only in Hungarian in the masters thesis [19] of T. Jeges, a student of G. Czédli. Theorem 4.10 ([19]). A finite monounary algebra A = (A, f ) is injective in the variety HSP(A) if and only if all of its sources have the same height and it has a one-element subalgebra (i.e., f has a fixed point). 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. Acknowledgements The authors are grateful to Dragan Mašulović 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. References [1] Christian Pech and Maja Pech. On polymorphism-homogeneous relational structures and their clones. Algebra Universalis, 73(1):53–85, 2015. [2] Boris Plotkin. Some results and problems related to universal algebraic geometry. Internat. J. Algebra Comput., 17(5-6):1133–1164, 2007. [3] Endre Tóth and Tamás Waldhauser. Solution sets of systems of equations over finite lattices and semilattices. Algebra Universalis, 81(2):13, 2020. [4] Endre Tóth and Tamás Waldhauser. On the shape of solution sets of systems of (functional) equations. Aequationes Math., 91(5):837–857, 2017. [5] V. G. Bodnarčuk, L. A. Kalužnin, V. N. Kotov, and B. A. Romov. Galois theory for Post algebras. I, II. Kibernetika (Kiev), (3):1–10; ibid. 1969, no. 5, 1–9, 1969. [6] David Geiger. Closed systems of functions and predicates. Pacific J. Math., 27:95–100, 1968. [7] B. A. Romov. The algebras of partial functions and their invariants. Kibernetika (Kiev), (2):i, 1–11, 149, 1981. [8] Peter J. Cameron and Jaroslav Nešetřil. Homomorphism-homogeneous relational structures. Combin. Probab. Comput., 15(1-2):91–103, 2006. [9] Zuzana Farkasová and Danica Jakubíková-Studenovská. Polymorphism-homogeneous monounary algebras. Math. Slovaca, 65(2):359–370, 2015. [10] L. G. Kovács and M. F. Newman. Injectives in varieties of groups. Algebra Universalis, 14(3):398–400, 1982. [11] G. Bruns and H. Lakser. Injective hulls of semilattices. Canad. Math. Bull., 13:115–118, 1970. [12] Alfred Horn and Naoki Kimura. The category of semilattices. Algebra Universalis, 1(1):26–38, 1971. [13] Igor Dolinka and Dragan Mašulović. Remarks on homomorphism-homogeneous lattices and semilattices. Monatsh. Math., 164(1):23–37, 2011. [14] Raymond Balbes. Projective and injective distributive lattices. Pacific J. Math., 21:405–420, 1967. [15] László Fuchs. Infinite abelian groups. Vol. I. Pure and Applied Mathematics, Vol. 36. Academic Press, New York-London, 1970. [16] O. C. García and F. Larrión. Injectivity in varieties of groups. Algebra Universalis, 14(3):280–286, 1982. [17] Éva Jungábel and Dragan Mašulović. Homomorphism-homogeneous monounary algebras. Math. Slovaca, 63(5):993–1000, 2013. [18] Danica Jakubíková-Studenovská. Retract injective and retract projective monounary algebras. In Contributions to general algebra, 10 (Klagenfurt, 1997), pages 207–214. Heyn, Klagenfurt, 1998. [19] Tünde Jeges. Injektív algebrák. University of Szeged, Hungary, 2000. Thesis (MA in Mathematics Education)– University of Szeged (Hungary).