Abstract
An algebraic structure is finitely related (has finite degree) if its term functions are determined by some finite set of finitary relations. We show that the following finite semigroups are finitely related: commutative semigroups, 3-nilpotent monoids, regular bands, semigroups with a single idempotent, and Clifford semigroups. Further we provide the first example of a semigroup that is not finitely related: the 6-element Brandt monoid. This answers a question by Davey, Jackson, Pitkethly, and Szabó from Davey et al. (Semigroup Forum, 83(1):89–122, 2011).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
A semigroup term t in k variables is a word in the alphabet x 1,…,x k . On a fixed semigroup S:=〈S,⋅〉, such a term t induces a k-ary term operation t S:S k→S by evaluation. The set of all finitary term functions on S is called the clone of term operations of S, denoted by Clo(S).
Clearly every term operation on S preserves all subsemigroups of S n for any n∈ℕ. By a classical result in universal algebra, on a finite algebra A every finitary operation that preserves all subuniverses of A n for every n∈ℕ is actually a term operation [6, 16]. This gives an implicit description of the term clone by infinitely many relations. For certain algebraic structures, like finite lattices, already finitely many relations determine the clone [3]. Hence we say that finite lattices are finitely related (or have finite degree). In contrast, the term clone of the 2-element implication algebra 〈{0,1},→〉 is not determined by any finite set of relations (here 1→0 is 0 and x→y is 1 for all other combinations x,y∈{0,1}).
It has recently been shown that all finite groups are finitely related [1]. In [11] Davey, Jackson, Pitkethly, and Szabó started the investigation of clones of semigroups and the relations that determine them. In particular, they posed the question:
Is the clone Clo(S) of all term functions of a finite semigroup S necessarily determined by a finite set of relations?
They showed that the answer is yes for finite nilpotent semigroups and for finite commutative semigroups. They also gave an example of a semigroup expanded with an additional unary operation which is not finitely related. Their question for semigroups remained open.
We give an alternative proof for the finite relatedness of commutative semigroups in Theorem 3.1 and show that adjoining a 0 to a finitely related semigroup yields again a finitely related semigroup in Theorem 4.1. Then we will add on to the results by Davey, et al., by showing that the following finite semigroups are finitely related:
-
(1)
Clifford semigroups (Corollary 4.3).
-
(2)
3-nilpotent monoids (Theorem 5.1),
-
(3)
regular bands (Theorem 6.2),
-
(4)
semigroups with a single idempotent (Theorem 7.1),
Finally we prove that the 6-element Brandt monoid is not finitely related (Theorem 8.2). This is the first known example of such a semigroup. Hence the above question by Davey, et al., has a negative answer.
The authors of [11] and Marković, Maróti, and McKenzie in [24] independently proved that, for finite algebras A,B that generate the same variety, A is finitely related if and only if B is. In this respect finite relatedness is a finiteness condition on varieties just like being finitely based. Recall that a finite algebra of finite type is finitely based if the variety it generates can be axiomatized by finitely many equations. Further both properties seem similar in that they pertain to terms on an algebra. Still in general neither implies the other: Baker proved that every finite algebra that generates a congruence distributive variety is finitely based [2]. However the 2-element implication algebra 〈{0,1},→〉 which generates a congruence distributive variety is not finitely related (see for example [11] for an elementary proof). Conversely, every finite group (possibly expanded with additional operations) is finitely related by [1]. Still Bryant [8] showed that there are finite groups with an additional constant operation that are not finitely based.
Finitely related clones received some renewed interest lately because of their connection with Constraint Satisfaction Problems (CSP). In [4] Barto showed that every finite, finitely related algebra in a congruence distributive variety actually has a near unanimity term operation. Consequently the corresponding CSPs have bounded strict width [14].
Valeriote conjectured that a generalization of Barto’s result may be true [7]: Every finite, finitely related algebra in a congruence modular variety has few subpowers. Here a finite algebra A has few subpowers if there exists a polynomial p such that A n has at most 2p(n) subalgebras (see [5] for a thorough investigation of this condition). The class of finite algebras with few subpowers contains Mal’cev algebras (in particular groups) and algebras with near unanimity term operations. In [1] some kind of converse to Valeriote’s conjecture is proved: Every finite algebra with few subpowers is finitely related.
2 Preliminaries
For notation and general facts on semigroups we refer to [10, 19], for term functions and relations to [9, 28].
We consider an algebraic structure (an algebra) A:=〈A,F〉 as set A together with a set of finitary operations F on A. A clone on a set A is a set of finitary operations that is closed under composition and contains the projections e i (x 1,…,x k )=x i for all k∈ℕ and for all i in \(\underline{k}:= \{1,\dots,k\}\). The clone of term operations of an algebra A:=〈A,F〉, denoted by Clo(A), is the smallest clone on A that contains F. The set of k-ary term functions is denoted Clo k (A).
Two algebras 〈A,F 1〉 and 〈A,F 2〉 on the same set are said to be term equivalent if their clones are equal. For example, a finite group can be viewed as 〈G,⋅,−1,1〉 with binary operation ⋅ and unary operations −1 and 1 or just as 〈G,⋅〉. If G is finite, then both these algebras are term equivalent. Since we are interested in describing term clones, we will not distinguish between term equivalent algebras in this paper.
For sets A and I, a subset R of A I is called a relation on A. An operation f:A k→A preserves a relation R on A if f(r 1,…,r k )∈R for all r 1,…,r k ∈R. Here f is applied to the tuples in R coordinatewise. We say that an algebra A (its clone Clo(A)) is finitely related if there exist subalgebras R 1,…,R l of finitary powers of A such that every operation on A that preserves every R i for 1≤i≤l is a term operation on A.
Finitely related algebras have been called predicately describable by Jablonskiĭ [20], finitely definable by Romov [29], of finite relational degree by Rosenberg [30], or of finite degree by Rosenberg and Szendrei [31]. Introducing yet another name for the same concept may seem superfluous but since “finitely related” has become popular in the more recent literature [1, 4, 24], we will use it in this paper as well.
Note that Clo n (A) forms a subalgebra of \({\mathbf{A}}^{A^{n}}\). To say that f:A k→A preserves Clo n (A) actually means that for all g 1,…,g k ∈Clo n (A) the composition of functions
is in Clo n (A).
We say an function f:A k→A depends on its i-th argument x i (or the i-th argument of f is essential) if there exist a,b∈A k such that a j =b j for all \(j\in\underline {k}\setminus\{i\}\) and f(a)≠f(b). For example, the projection on the i-th coordinate depends on x i but not on its other arguments.
Let k∈ℕ, and let α be an equivalence relation on \(\underline{k}\). For a set A and f:A k→A we define a new function by identifying arguments whose indices are α-related. Let
Then f α depends on at most as many arguments as there are blocks in α. For 1≤i<j≤k and α the equivalence with one block {i,j} and all singletons on \(\underline{k}\setminus\{i,j\}\), we also write f ij :=f α .
If f:A k→A preserves a relation R on A, then clearly f α preserves R for every equivalence α on \(\underline{k}\). If f is a term operation on some algebra A, then f α is a term operation as well.
We can now collect some classical conditions that are equivalent to being finitely related. For the majority of our results in this paper, property (3) of the following is the most convenient to check.
Lemma 2.1
For a finite algebra A the following conditions are equivalent:
-
(1)
A is finitely related.
-
(2)
∃n∈ℕ ∀k>n ∀f:A k→A: if f α ∈Clo(A) for every equivalence relation α with n blocks on \(\underline{k}\), then f∈Clo(A).
-
(3)
∃n∈ℕ ∀k>n ∀f:A k→A: if f ij ∈Clo(A) for all 1≤i<j≤k, then f∈Clo(A).
Proof
Jablonskiĭ [20] observed that if there exist relations R 1,…,R l such that Clo(A) is the clone of functions that preserve R 1,…,R l , then (2) holds with n:=max(|R 1|,…,|R l |). Conversely, if A satisfies (2), then Clo(A) is the clone of functions preserving Clo n (A), hence A is finitely related. Rosenberg and Szendrei showed that (2) and (3) are equivalent for the same n in [31]. □
In [31] Rosenberg and Szendrei defined the degree of an algebra A as the least n that satisfies condition (2) in Lemma 2.1. The term degree of an algebra A as defined by Davey, et al., in [11, Definition 2.10] is the least n≥|A| that satisfies condition (2) in Lemma 2.1. Hence the term degree of A is as least as great as its degree. They are both finite if and only if A is finitely related.
Note that if A has degree n, then every operation on A that preserves Clo n (A) is a term operation. The converse is not necessarily true.
The next fact is a well known consequence of a result by Willard [34, Lemma 1.2].
Lemma 2.2
[11, Lemma 3.1]
Let A be a finite algebra. Assume that there exists k∈ℕ such that every term function on A depends on at most k arguments.
Then A is finitely related with degree at most max(|A|,k+2).
We restate 2 immediate consequences of the previous lemma from [11].
For l∈ℕ, a semigroup is l-nilpotent if it satisfies x 1⋯x l =y 1⋯y l . Then every term function depends on at most l−1 arguments. A semigroup is nilpotent if it is l-nilpotent for some l∈ℕ. From Lemma 2.2 we obtain the following.
Corollary 2.3
[11, Theorem 3.4]
Every finite nilpotent semigroup S is finitely related with degree at most |S|+1.
It is known that the ratio of 3-nilpotent semigroups with n elements to the number of all semigroups with n elements goes to 1 as n goes to infinity [21]. In this sense almost all finite semigroups are nilpotent and hence finitely related by the previous result. We will prove a similar statement for monoids in Sect. 5, Theorem 5.1.
A semigroup satisfying x 2=x (i.e., all elements are idempotent) is called a band. A band is rectangular if it satisfies xyz=xz. In this case any term function has essential arity at most 2 and Lemma 2.2 yields the next statement.
Corollary 2.4
Every finite rectangular band S is finitely related with degree at most max(|S|,4).
Let us recall some more terminology and notations for semigroups that will be used in the paper. Let S:=〈S,⋅〉 be a semigroup. We denote the set of idempotents of S by E(S). A non-empty subset I of S is an ideal of S if IS⊆I and SI⊆I. Every ideal I of S induces a congruence ρ=(I×I)∪{(x,x):x∈S} which identifies the elements in I. We will denote the quotient S/ρ simply by S/I (the Rees quotient of S by I). Every finite semigroup S has a unique minimal ideal, the socalled kernel of S.
Let G:=〈G,⋅〉 be a finite group, let I,Λ be non-empty sets, and let P be a Λ×I matrix with entries in G. On I×G×Λ we define a multiplication by
for i,j∈I,g,h∈G,λ,μ∈Λ. Then M(G,I,Λ,P):=〈I×G×Λ,⋅〉 is a semigroup, called a Rees matrix semigroup.
We state some straightforward facts on the kernel of a semigroup for later use.
Lemma 2.5
Let S be a finite semigroup, and let K be the kernel of S. Then we have:
-
(1)
〈K,⋅〉 is isomorphic to some Rees matrix semigroup M(G,I,Λ,P).
-
(2)
If S contains no non-trivial semilattice, then S/K is nilpotent.
Proof
Note that K is simple and even completely simple by its finiteness. Hence (1) follows from [19, Theorem 3.3.1].
For proving (2) assume that S contains no non-trivial semilattice. Suppose that there exists an idempotent a∈S∖K. Let b∈K. Then aba∈K, and (aba)m is idempotent for some m∈ℕ. Hence a and (aba)m form a 2-element semilattice contradicting the assumption. Thus there are no idempotents in S∖K and (2) follows. □
Finally we state two auxiliary results that we will use frequently.
Lemma 2.6
Let A be a finite set, let k>|A|+1, and let f:A k→A. If f depends on its l-th argument for some \(l\in\underline{k}\), then there exist distinct \(i,j\in\underline{k}\setminus\{l\}\) such that f ij depends on its l-th argument.
Proof
Pigeonhole principle. □
Lemma 2.7
Let S be a finite semigroup, let k>|S|2, and let f:S k→S. Assume that f depends on all its k arguments and that f ij ∈Clo(S) for all 1≤i<j≤k. Then the image of f is contained in \(I := \{ \prod_{i=1}^{|S|} a_{i} : a_{i} \in S \}\).
Proof
Assume |S|≥2 because the statement of the lemma is trivial otherwise. For n∈ℕ, let \(I_{n} := \{ \prod_{i=1}^{n} a_{i} : a_{i} \in S \}\). Then
Let d∈{1,…,|S|} be minimal such that I d =I d+1. Such a d exists since S is finite. Then I d+l =I d for all l∈ℕ.
Let f satisfy the assumptions of the lemma.
Case, d=|S|: Then I d is a singleton, say I d =I={0}, and S is nilpotent. By [34, Lemma 1.2] we have 1≤i<j≤k such that f ij depends on at least k−2 arguments. Since k−2≥|S|2−1≥|S| and f ij ∈Clo(S), we obtain that S has a term function depending on at least |S| variables. This contradicts the assumption that the product of any |S| elements from S is 0. Hence in this case no such f exists, and the result is proved.
Case, d≤|S|−1: By [34, Lemma 1.2] there exists a partition γ of \(\underline{k}\) such that f γ has either |S| or |S|−1 essential arguments. We may assume that γ has |S| or |S|−1 blocks, respectively.
Let a∈S k, and let \(\alpha:= \{ (i,j)\in\underline{k}^{2} : a_{i} = a_{j} \}\). Then α partitions \(\underline{k}\) into at most |S| classes. Hence γ∧α has at most |S|2 blocks. So we have a term t such that f γ∧α =t S. Clearly f γ∧α depends on at least as many arguments as f γ , that is, on at least |S|−1. Thus t contains at least |S|−1 distinct variables out of x 1,…,x k . Now f(a)=f γ∧α (a)=t S(a) yields f(a)∈I |S|−1. From d≤|S|−1 it follows that f(a)∈I. □
3 Commutative semigroups
Theorem 3.12 in [11] states that every finite commutative semigroup S is finitely related. A finite commutative semigroup S decomposes into a subdirect product of some finite family of monoids M 1,…,M l and a nilpotent semigroup N by [18, Corollary IV.4.6]. This fact is quoted in the proof of [11, Theorem 3.12] but incorrectly stated as “a monoid M” instead of “a finite family of monoids”. Consequently the argument given there seems to apply only to subdirect products of a monoid and a nilpotent semigroup. Not every finite commutative semigroup is of this form (see for example, a semilattice without 1). However the argument is easily fixed as follows: The direct product M:=M 1×…×M l is a commutative monoid and hence finitely related by [11, Theorem 3.6]. Since a finite direct product of a finitely related semigroup and a nilpotent semigroup is finitely related by [11, Lemma 3.11], it follows that M×N is finitely related. Clearly S and M×N generate the same variety. Thus S is finitely related by [11, Theorem 2.11], [24, Corollary 4.3] . This adapted proof does not yield the precise statement of Theorem 3.12 in [11], namely that S has term degree at most 2|S|.
In this section we give a self-contained alternative approach for the result on commutative semigroups.
Theorem 3.1
[11, Theorem 3.6]
Let S be a finite commutative semigroup. Then S is finitely related and has degree at most |S|2.
Proof
Let k>|S|2, and let f be a k-ary operation on S such that f ij is a term function for all 1≤i<j≤k. We will prove that f∈Clo(S). For that we may assume that f depends on all its arguments.
First consider the ternary relation R:={(a,b,ab):a,b∈S}. Since S is commutative, R forms a subsemigroup of S 3. We claim that
Let r 1,…,r k ∈R. Since |R|=|S|2<k, we have 1≤i<j≤k such that r i =r j . Hence f(r 1,…,r k )=f ij (r 1,…,r k ). The latter lies in the R because the term function f ij preserves the semigroup R. This proves (3.1). Hence f is a semigroup homomorphism from S k to S.
Let \(i\in\underline{k}\), and define \(g_{i}(x_{i},z) := f(z,\dots ,z,\underset{i}{x_{i}},z,\dots,z)\). Since k>2, g i is a term function. From commutativity and Lemma 2.6 it follows that
Here \(x_{i}^{e_{i}}z^{0}\) denotes \(x_{i}^{e_{i}}\).
Next we show that
Let x∈S k,z∈S. Since f is a homomorphism,
Together with (3.2) this yields that for some e 1,…,e k ∈ℕ and some d∈ℕ0
Since f(z k−1,…,z k−1)=z c for some c∈ℕ, (3.3) follows.
For n∈ℕ, let \(I_{n} := \{ \prod_{i=1}^{n} a_{i} : a_{i} \in S \}\). Since S is commutative, for every \(a\in I_{|S|^{|S|}}\) there exists b∈S such that a∈b |S| S. Now for b |S| we have u∈S such that b |S| u=b |S|. Hence au=a. Note that I |S|+l =I |S| for all l∈ℕ by the finiteness of S. Hence for every element a in I:=I |S| there exists u∈S such that au=a.
Let x∈S k. By Lemma 2.7 we have f(x)∈I and hence there exist u∈S such that f(x)u=f(x). Since k≥|S| and all e i >0 in (3.3), also \(\prod_{i=1}^{k} x_{i}^{e_{i}} \in I\) and we have v∈S such that \(\prod_{i=1}^{k} x_{i}^{e_{i}} v = \prod_{i=1}^{k} x_{i}^{e_{i}}\). Now (3.3) yields
Thus f∈Clo(S), and the result follows from Lemma 2.1. □
4 Adjoining 0
Davey, et al., [11], gave examples of groupoids and expansions of the implication algebra showing that being finitely related is not necessarily inherited by any of the following:
-
(1)
subalgebras,
-
(2)
homomorphic images,
-
(3)
subdirect factors,
-
(4)
direct products.
We will show that for semigroups at least the following innocuous construction behaves well with respect to finite relatedness.
Let S:=〈S,∗〉 be a semigroup which may or may not contain a zero element, let \(0\not\in S\). Then S 0:=〈S∪{0},⋅〉 denotes the semigroup S with 0 adjoined where x⋅y=x∗y for x,y∈S and x0=0x=0 for x∈S∪{0}.
Theorem 4.1
Let S be a finite semigroup. Then S is finitely related if and only if S 0 is finitely related.
In the proof we will need the following definition. Let G be a group, let I,Λ be non-empty sets, and let P be a Λ×I matrix with entries in G. On I×G×Λ we define a multiplication by
for i,j∈I,g,h∈G,λ,μ∈Λ. Then M(G,I,Λ,P):=〈I×G×Λ,⋅〉 is a semigroup, called a Rees matrix semigroup. Every completely simple semigroup is of this form [19, Theorem 3.3.1].
Proof of Theorem 4.1
The result is immediate from Theorem 3.1 if |S|=1. Assume S is finitely related with degree n and |S|>1. We will show that
Let k>max(n,|S|2), and let f:(S 0)k→S 0 such that f ij ∈Clo(S 0) for all 1≤i<j≤n. For proving f∈Clo(S 0) we may assume that f depends on all its arguments. First we claim that
Fix a∈(S 0)k such that a l =0 for some \(l\in\underline{k}\). By Lemma 2.6 we have distinct indices \(i,j\in\underline{k}\setminus\{l\}\) such that f ij depends on its l-th argument. In particular, f ij is induced by a term which contains x l . Hence
Since k−1>|S 0|, we have distinct indices \(r,s\in\underline {k}\setminus\{l\}\) such that a r =a s . Then \(f_{rs}(c,\dots,c,\underset{l}{0},c,\dots,c) = 0\) for all c∈S implies that f rs is induced by a term that contains x l . So f(a)=f rs (a)=0 and (4.2) is proved.
Since k>|S|, f preserves S. That is \(g := f|_{S^{k}}\), the restriction of f to S k, has its image contained in S. It follows that g ij ∈Clo(S) for all 1≤i<j≤k. Since k>n and S has degree n by assumption, we have a term t such that g=t S. In the following we consider two cases.
Case, S contains a non-trivial semilattice: Then we have distinct b,c∈S such that \(b^{2} \hspace{-0.5pt}=\hspace{-0.5pt} b, c^{2} \hspace{-0.5pt}=\hspace{-0.5pt} c\), and \(bc \hspace{-0.5pt}=\hspace{-0.5pt} cb \hspace{-0.5pt}=\hspace{-0.5pt} b\). From (4.3) it follows that \(f(c,\dots,c,\underset{l}{b},c,\dots,c) \hspace{-0.5pt}=\hspace{-0.5pt} b\). Hence g depends on its l-th argument for every \(l\in\underline {k}\), and t contains all variables x 1,…,x k . Thus t S(a)=0 for all a∈(S 0)k∖S k. Now \(f = t^{{\mathbf{S}}^{0}}\) follows with (4.2).
Case, S contains no non-trivial semilattice: By Lemma 2.5 the kernel K of S forms a semigroup isomorphic to some Rees matrix semigroup M(G,I,Λ,P) for a group G, index sets I,Λ, and P a Λ×I matrix with entries in G. To simplify notation we assume K=I×G×Λ. We will prove that the term
Let a∈S k. Since k>|S|2 and S/K is nilpotent by Lemma 2.5, Lemma 2.7 implies that f(a) is contained in K. Furthermore a 1⋯a k is in K. Say f(a)=(i,g,λ) and a 1⋯a k =(j,h,μ) for i,j∈I,g,h∈G,λ,μ∈Λ. Now
Thus f(a)=u S(a) for all a∈S k. Since f(a)=0=u S(a) for all a∈(S 0)k∖S k, (4.4) follows. We have proved (4.1). Hence S 0 is finitely related if S is finitely related.
The proof for the converse implication follows similar lines and is omitted. □
A semigroup is completely regular if every one of its elements lies in a subgroup. A completely regular semigroup in which all idempotents are central is called a Clifford semigroup. Groups are just Clifford semigroups with a unique idempotent. We will show that finite Clifford semigroups are finitely related, thereby generalizing the result on groups from [1]. For the proof we use the following fact which is well-known and can be easily deduced from a combination of results from [25] and [32]. We include its proof for the sake of completeness.
Lemma 4.2
Let S be a finite Clifford semigroup that is not a group. Then there exist a finite group G such that S and G 0 generate the same variety.
Proof
Recall that Green’s \(\mathcal{J}\)-relation is a congruence on S, \({\mathbf{S}}/\mathcal{J}\) is a semilattice isomorphic to 〈E(S),⋅〉, and every \(\mathcal {J}\)-class of S is a group [10, Theorem 4.11]. In particular we have a partial order ≤ on the semilattice \({\mathbf{S}} /\mathcal{J}\).
Let V(S) denote the variety generated by S. Since S is not a group by assumption, V(S) contains the 2-element semilattice L:=〈{0,1},⋅〉. Further for every H∈V(S) we have that H 0 is isomorphic to the Rees quotient (H×L)/(H×{0}) and consequently in V(S).
Let T:=∏ e∈E(S)〈J e ,⋅〉o. We claim
Then T is in V(S) by the previous remark. For proving that conversely S is in V(T) consider the map \(h: S \to\prod_{e\in E({\mathbf{S}})} (J_{e} \cup\{0\}), x \mapsto\bar{x}\), where
Let x,y∈S, e∈E(S). If J e ≤J x and J e ≤J y , then \(\overline{xy}(e) = xye = xeye = (\bar{x}\bar{y})(e)\). Otherwise \(\overline{xy}(e) = 0 = (\bar{x}\bar{y})(e)\). Hence h is a homomorphism. Since h is clearly one-to-one, we have shown that S is isomorphic to a subsemigroup of T. This proves (4.5).
Now choose G:=∏ e∈E(S) J e to be the direct product of all \(\mathcal{J}\)-classes in S. Then G:=〈G,⋅〉 is a group. It is straightforward that G 0 and T generate the same variety. Thus the result follows from (4.5). □
Corollary 4.3
Finite Clifford semigroups are finitely related.
Proof
By [1] every finite group is finitely related. Hence the result follows from Lemma 4.2 and Theorem 4.1 together with [11, Theorem 2.11]. □
5 Nilpotent monoids
If S is an l-nilpotent semigroup, we call the monoid S 1 obtained from S by adjoining 1 an l-nilpotent monoid. Similar to the case of semigroups, the ratio of 3-nilpotent monoids on n elements to the number of all monoids on n elements goes to 1 as n goes to infinity [23]. So, by our next result, we may say that almost all finite monoids are finitely related.
Theorem 5.1
Every finite 3-nilpotent monoid S is finitely related with degree at most max(4,|S|+1).
Proof
Note that S satisfies x 2 y=yx 2=xyx and x 4=x 3. Consequently, for every term t on S containing x 1,…,x k there exists a permutation p on \(\underline{k}\) and there exist e 1,…,e k ∈{1,2,3} such that t is equivalent to \(x_{p(1)}^{e_{1}}\cdots x_{p(k)}^{e_{k}}\).
Let k>max(4,|S|+1), and let f be a k-ary operation on S such that f ij ∈Clo(S) for all 1≤i<j≤k and f depends on all its arguments. We will prove f∈Clo(S).
For \(i,j,l\in\underline{k}\), let α be the equivalence relation of \(\underline{k}\) with blocks {i},{j},{l}, and \(\underline{k}\setminus\{i,j,l\}\). Since k>4 by assumption, f α is a term function. In particular there exist u,v,w with {i,j,l}={u,v,w} and there exist e u ,e v ,e w ∈{1,2,3} such that
Note that the exponents e u ,e v ,e w are necessarily positive since f(1,…,1,0,1,…,1)=0 by Lemma 2.6. Let
For distinct i,j∈I define
If S is commutative, then the reflexive closure ⪯ of ≺ is the total relation on I. If S is not commutative, then ⪯ is a linear order on I. Anti-symmetry follows from non-commutativity. For transitivity let i,j,l∈I be such that i≺j and j≺l. Then non-commutativity and (5.1) yields \(f(1,\dots, 1, \underset{i}{x_{i}},1,\dots, 1,\underset {j}{x_{j}},1,\dots, 1,\underset{l}{x_{l}},1,\dots, 1) = x_{i}x_{j}x_{l}\) and i≺l follows by letting x j =1. Linearity is immediate.
Let I={i 1,…,i m } with i 1≺…≺i m . Define
By its definition g is a term function. To show f=g, fix a∈S k. If all but one coordinate of a are 1, then f(a)=g(a). Assume exactly 2 coordinates of a are distinct from 1, say a i and a j . If i,j∈I and i≺j, then f(a)=a i a j =g(a). If i or j are not in I, then f(a)=0=g(a). Similarly, if a has 3 or more coordinates distinct from 1, then their product is 0 and f(a)=0=g(a). Thus f=g, and the result follows from Lemma 2.1. □
Our proof of Theorem 5.1 is quite different from the proof that nilpotent semigroups are finitely related. Note that unlike in the case of nilpotent semigroups, for nilpotent monoids there is no constant k such that every term function depends on at most k arguments. It is not clear whether all nilpotent monoids are finitely related and how this could follow from the result for nilpotent semigroups. Unlike for adjoining 0 (see Theorem 4.1), we do not know whether the class of finitely related semigroups is closed under adjoining 1.
6 Bands
It was already observed that finite semilattices and rectangular bands are finitely related. In this section we show finite relatedness for the larger class of regular bands (see Theorem 6.2). After submitting the present article we received notice that Dolinka independently proved the same result using a different approach [12].
A band is called left (respectively right) normal if it satisfies xyz=xzy (respectively xyz=yxz). It is left (respectively right) regular if it satisfies xyx=xy (respectively xyx=yx). A band is regular if it satisfies xyzx=xyxzx.
Lemma 6.1
Let S be a finite left regular band. Then S is finitely related with degree at most max(4,|S|+1).
Proof
We will use ideas similar to those in the proof for Theorem 5.1. Observe that for every term t on S containing x 1,…,x k there exists a permutation p on \(\underline{k}\) such that t is equivalent to x p(1)⋯x p(k).
Recall that Green’s \(\mathcal{J}\)-relation is a congruence on the band S and that \({\mathbf{S}}/\mathcal{J}\) is a semilattice [19, Theorem 4.1.3]. We may assume that \(|S/\mathcal{J}| > 1\) because otherwise S is rectangular and the result follows from Corollary 2.4.
Let k>max(4,|S|+1), and let f:S k→S such that f ij ∈Clo(S) for all 1≤i<j≤k and f depends on all its arguments. We will show f∈Clo(S).
For distinct \(i,j,l\in\underline{k}\) consider the 4-ary operation
on S. Since k>4, g is induced by a term u in the variables x i ,x j ,x l , and z. By assumption we have a,b∈S with J a >J b with respect to the semilattice order on \({\mathbf{S}}/\mathcal{J}\). Since g is a term function, we have f(a,…,a)=a. Further Lemma 2.6 yields f(a,…,a,b,a,…,a)∈J b . Hence
It follows that for distinct \(i,j\in\underline{k}\) the ternary operation
on S is induced by zx i x j ,x i zx j ,x i x j z or one of these words with x i and x j exchanged. We define
Note that at least one of i≺j or j≺i1 are satisfied. We will investigate the relation ≺ in the following 3 cases:
Case, S is commutative: Then \((\underline {k},\prec)\) is the complete digraph without loops.
Case, S is left normal, not commutative: We claim that
To see that we first show that there exists a unique index \(s\in \underline{k}\) such that
Seeking a contradiction we first suppose that no such s exists. Then for all 1≤i<j≤k the operation f ij is induced by a term starting in x j . Let α be the equivalence relation on \(\underline{k}\) with blocks {1,2}, {3,4}, and {5,…,k}. Since the term for f 12 starts with x 2, also f α is induced by a term starting in x 2. But similarly f α is induced by a term starting in x 4. It follows that S is commutative which contradicts the assumption. Hence s as in (6.3) exists. For the uniqueness suppose that there are distinct \(i,j\in\underline{k}\) such that \(f(z,\dots, z, \underset{i}{x_{i}},z,\dots, z) = x_{i}z\) and \(f(z,\dots, z,\underset{j}{x_{j}},z,\dots, z) = x_{j}z\) for all x i ,x j ,z∈S. Together with i≺j or j≺i, this immediately yields that S is commutative. Hence s as in (6.3) is unique.
Let s as in (6.3), and \(i,j\in\underline{k}\setminus\{s\}, i\neq j\). Then it is straightforward to check that \(f(z,\dots, z, \underset{i}{x_{i}},z,\dots, z,\underset {s}{x_{s}},z,\dots, z) = x_{s}x_{i}z\) and \(f(z,\dots, z, \underset{i}{x_{i}},z,\dots, z,\underset {j}{x_{j}}, z,\dots, z) = zx_{i}x_{j} = zx_{j}x_{i}\) for all x i ,x j ,x s ,z∈S. Hence s≺i and i≺j,j≺i. Note that i≺s together with (6.3) would imply that S is commutative. Hence (6.2) is proved.
Case, S is left regular, not left normal: Then \((\underline {k},\prec)\) is a transitive tournament. Anti-symmetry of ≺ follows since S is idempotent and not left regular. If i≺j and j≺l, then g(x i ,x j ,x l ,z) is induced by a term where x i occurs to the left of x j and x j to the left of x l . Hence x i ≺x l follows by setting x j =x l .
In all 3 cases we have \(\underline{k}= \{i_{1},\dots,i_{k}\}\) with i 1≺…≺i k . Define
For proving f=t, let a∈S k be arbitrary. Since k>|S|, we have 1≤j<l≤k such that a j =a l . By (6.1) f jl depends on x i for all \(i\in\underline {k}\setminus\{j,l\}\) and on x l . We consider the cases as above again.
Case, S is commutative: Then f jl is induced by the term \(\prod_{i\in\underline{k}\setminus\{ j\}} x_{i}\) and f(a)=f jl (a)=t(a).
Case, S is left normal, not commutative: If \(i_{1}\not\in\{i,l\}\), then f jl is induced by \(x_{i_{1}} \prod_{i\in\underline{k}\setminus\{i_{1},j\}} x_{i}\) by (6.3). If i 1∈{i,l}, then similarly f jl is induced by \(x_{l} \prod_{i\in\underline{k}\setminus\{j,l\}} x_{i}\). In both cases f(a)=f jl (a)=t(a).
Case, S is left regular, not left normal: Assume that that f jl is induced by a term v in the following. Let \(i\in\underline{k}\setminus\{j,l\}\). We claim that
If i≺j and i≺l, then g(x i ,x l ,x l ,z) is induced by a term where x i occurs to the left of x l . Since g(x i ,x l ,x l ,z) arises from f jl by identifying all arguments distinct from x i and x l , we have that x i occurs to the left of x l in v as well. If j≺i or l≺i, then g(x i ,x l ,x l ,z) is induced by a term where x l occurs to the left of x i . Further x l is left of x i in v. Now (6.4) is proved. This yields that f jl =t jl . Hence f(a)=f jl (a)=t(a), and f is a term function. □
Lemma 6.1 has an obvious analogue for right regular bands. We will prove the more general result next.
Theorem 6.2
(See [12])
Finite regular bands are finitely related.
Proof
Let S be a finite regular band. Then Green’s \(\mathcal{L}\)- and \(\mathcal{R}\)-relations are congruences with \({\mathbf{S}}/\mathcal{R}\) left regular, \({\mathbf{S}}/\mathcal{L}\) right regular, and S is a subdirect product of \({\mathbf{S}}/\mathcal{R}\) and \({\mathbf{S}}/\mathcal{L}\) (see [27, Proposition V.1.3]). If \(|{\mathbf{S}}/\mathcal{J}| = 1\), then S is a rectangular band and the result follows from Corollary 2.4. So we assume \(|{\mathbf{S}}/\mathcal {J}| > 1\) in the following.
Let f be a k-ary operation on S such that f preserves \(\mathcal {R},\mathcal{L}\) and Clomax(4,|S|+1)(S). We claim that
Since \({\mathbf{S}}/\mathcal{R}\) is left regular, Lemma 6.1 yields that we have a term s such that \(f(x) \mathrel{\mathcal{R}}s^{\mathbf{S}}(x)\) for all x∈S k. Similarly we have a term t such that \(f(x) \mathrel{\mathcal{L}}t^{\mathbf{S}}(x)\) for all x∈S k. Assume that f depends on all its k arguments. Since \({\mathbf {S}}/\mathcal{J}\) is a non-trivial semilattice and f preserves Clo|S|+1(S), from Lemma 2.6 we obtain that the operation that f induces modulo \(\mathcal{J}\) depends on all arguments as well. \(\mathcal{J}\) contains \(\mathcal{L}\) and \(\mathcal{R}\). So f modulo \(\mathcal{L}\) depends on all k arguments, as does f modulo \(\mathcal{R}\). Thus both s and t contain all variables x 1,…,x k .
Let a∈S k. Since \({\mathbf{S}}/\mathcal{R}\) is left regular, we have \(s^{\mathbf{S}}(a)t^{\mathbf{S}} (a) \mathrel{\mathcal{R}}s^{\mathbf{S}}(a) \mathrel{\mathcal{R}}f(a)\). Similarly \(s^{\mathbf{S}}(a)t^{\mathbf{S}}(a) \mathrel{\mathcal {L}}t^{\mathbf{S}}(a) \mathrel{\mathcal{L}}f(a)\). Hence \(s^{\mathbf {S}}(a)t^{\mathbf{S}} (a) \mathrel{\mathcal{R}\wedge\mathcal{L}} f(a)\). As \(\mathcal{R}\wedge\mathcal{L}\) is the equality relation on S, this proves f=(st)S. □
Our proof of Theorem 6.2 made use of the particular form (up to equivalence) of terms on regular bands. Varieties of bands have been throughly investigated. Fennemore in [15] and Gerhard in [17] have proved that they are all finitely based. Still the clones of bands are less well studied. We propose the following question:
Problem 6.3
Is every finite band finitely related?
Note that bands are completely regular. Hence we may ask more generally:
Problem 6.4
Is every finite completely regular semigroup finitely related?
Finite simple semigroups are an important subclass of completely regular semigroups. As noted before they are essentially Rees matrix semigroups of the form M(G,I,Λ,P). The next problem may be a first step towards solving the previous one.
Problem 6.5
Is every finite simple semigroup finitely related?
7 Semigroups with a unique idempotent
That finite groups are finitely related follows from the much more general result that finite algebras with few subpowers are finitely related [1]. Every algebra with few subpowers generates a congruence modular variety [5]. From the classification of minimal varieties of semigroups [13] it follows that a finite semigroup S generates a congruence modular variety if and only if S is term equivalent to a group. Hence groups are the only semigroups that have few subpowers and the only semigroups to which the result in [1] applies directly.
Still we are able to use [1] for dealing with certain semigroups whose structure is close to that of groups. The next result applies to nilpotent semigroups and to groups likewise.
Theorem 7.1
Every finite semigroup with a unique idempotent is finitely related.
Proof
Let S be a finite semigroup with a unique idempotent e and kernel K. By Lemma 2.5 we have that K:=〈K,⋅〉 is isomorphic to some Rees matrix semigroup. Since K contains only one idempotent, it follows that K actually forms a group with identity e. Note that for any x∈S, we have ex,xe∈K. Hence
and e is central in S.
Since finite groups are finitely related by [1], we have m∈ℕ such that for every k>m, every g:K k→K is in Clo(K) whenever g ij ∈Clo(K) for all 1≤i<j≤k. Let n:=max(|S|2,m). Let k>n, and let f:S k→S such that f ij ∈Clo(S) for all 1≤i<j≤k. We will show that f∈Clo(S). For that we may assume that f depends on all its arguments.
Let ρ:={(x,ex):x∈S}. Then ρ is a subsemigroup of S 2 because e is central in S. Since f α is a term function on S for any equivalence relation α on \(\underline{k}\) with less than |S|2 blocks and |ρ|=|S|, we have that
Since k>m, we have a semigroup term t such that \(f|_{K^{k}}\) is induced by t. Since K forms a group, we may assume that t is of the form \(ux_{1}^{|K|\cdot|S|}\) for some term u. In particular the image of t S is contained in K. We claim that
For proving this, let a 1,…,a k ∈S be arbitrary. Since (a i ,ea i )∈ρ for all \(i\in\underline{k}\) and f preserves ρ, we have
Now ea 1,…,ea k ∈K yields f(ea 1,…,ea k )=t S(ea 1,…,ea k )=et S(a 1,…,a k ). Hence
By Lemma 2.7 the image of f is contained in K as is the image of t S. Since e is the identity for elements in K, we obtain f(a 1,…,a k )=t S(a 1,…,a k ). Thus (7.1) and the theorem are proved. □
8 A non-finitely related semigroup
The semigroup of the following 2×2 matrices under multiplication is often called the Brandt monoid \({\mathbf{B}}_{2}^{1} := \langle{B_{2}^{1}}, {\cdot} \rangle\) in the literature:
\({\mathbf{B}}_{2}^{1}\) is generated by the elements denoted by a and b. In this section we will give an elementary proof that \({\mathbf{B}}_{2}^{1}\) is not finitely related.
The Brandt monoid arises repeatedly in investigations: Perkins proved that it is not finitely based in [26]. Seif [33] and Klíma [22] showed that checking term equivalence for \({\mathbf{B}}_{2}^{1}\) is coNP-complete. None of these properties seem directly connected with the fact that \({\mathbf{B}}_{2}^{1}\) is not finitely related. For our proof we use the following combinatorial observation.
Lemma 8.1
For n≥2, let K n be the complete digraph with vertex set \(\underline{n}\) without loops. Then there exists a directed path w on K n with the following properties:
-
(1)
w starts and ends with (1,2,…,n).
-
(2)
w uses every edge of K n at least once.
-
(3)
For every i∈{1,…,n−1} the vertices i and i+1 occur in w in alternating order throughout.
-
(4)
For every \(i,j \in\underline{n}\) with |i−j|>1 there exist 2 occurences of i in w without j in between them.
Proof
We will prove the lemma by induction on n.
For n=2 consider w:=(1,2,1,2).
Now assume that n≥3 and that u is a path that has the desired properties on K n−1. For paths and vertices w 1,…,w l let (w 1,…,w l ) denote the path formed by the concatenation of w 1,…,w l . Let u 1,…,u r be paths that end in n−1 but do not pass through n−1 otherwise such that
For i∈{1,…,n−2}, let v i :=(1,…,i−1,n−1,i,n,i+1,…,n−2). Define
Then w clearly satisfies (1).
For (2), we note that the first part
of w is obtained from u simply by inserting n in several places. So by the induction assumption every edge of K n−1 occurs in w 1 except for (n−1,i) with i∈{1,…,n−2} which occur in v 1,…,v n−2. This leaves the edges to and from n. For i∈{1,…,n−2} we find (n,i) in w 1 and (i,n) in v i . The remaining edges (n−1,n) and (n,n−1) appear in (v n−2,n−1,n). Thus (2) is proved.
Next we show (3). Let
be the second part of w. Then w=(w 1,w 2). Let i∈{1,…,n−2}. By induction assumption, i and i+1 alternate in w 1 ending with i+1. In w 2 we have that i and i+1 alternate starting with i and ending with i+1 as well. It is easy to see that n−1 and n alternate throughout w. This proves (3).
For (4), let i,j∈{1,…,n−1} such that |i−j|>1. By the induction assumption there exist 2 occurrences of i in w 1 without j in between them. Note that (1,…,n−2,v 1) contains 2 occurrences of 1 without n in between. Further, for 2≤i≤n−2, the sequence (v i−1,v i ) contains two i that are not separated by n. Finally in (v n−2,n−1,n) we find the sequence (n,n−1,n), that is, two n without any of the vertices 1,…,n−2 in between. Thus (4) is shown, and the lemma is proved. □
Theorem 8.2
The Brandt monoid \({\mathbf{B}}_{2}^{1}\) is not finitely related.
Proof
Let n≥3 be arbitrary. We will exhibit an n-ary operation f on \({\mathbf{B}}_{2}^{1}\) which is not a term function but all f ij with 1≤i<j≤n are term functions. Thus \({\mathbf{B}}_{2}^{1}\) is not finitely related by Lemma 2.1.
Let and . Define \(f: (B_{2}^{1})^{n} \to B_{2}^{1}\) by
Note that f is not a term function. Suppose otherwise that f is induced by a term t. Since f is invariant under the cyclic permutation of its arguments, we may assume that t begins with x 1. Then f(b,1,…,1,a) is in \(bB_{2}^{1}\) which contradicts f(b,1,…,1,a)=ab.
Let 1≤i<j≤n. To show that
let w=(w 1,…,w l ) be a path on K n with \(w_{1},\dots,w_{l}\in \underline{n}\) that satisfies the assertions of Lemma 8.1. Consider the term function
From a 2=0,b 2=0 and the properties of w it is easy to see that
For \(x\in(B_{2}^{1})^{n}\) define
We claim that
Clearly \(f_{ij}|_{\{0,ab,ba,1\}^{n}} = h|_{\{0,ab,ba,1\}^{n}}\).
Let \(x\in(B_{2}^{1})^{n} \setminus\{0,ab,ba,1\}^{n}\). Assume f ij (x)≠0. Then we have \(k,k'\in\underline {n}\setminus\{i,j\}\) such that k+1≡k′modn, (x k ,x k′)∈{(a,b),(b,a)} and x u =1 for all u∈{1,…,n}∖{i,k,k′}. Further f ij (x)=x k x k′=h(x). Conversely, it is routine to show that h(x)≠0 implies h(x)=f ij (x). Hence f ij (x)=h(x) for all \(x\in(B_{2}^{1})^{n} \setminus\{0,ab,ba,1\}^{n}\), and (8.1) is proved. □
A semigroup S is inverse if for every x∈S there exists a unique element y∈S (an inverse) such that x=xyx and y=yxy. Note that the Brandt monoid \({\mathbf{B}}_{2}^{1}\), bands, and Clifford semigroups are examples of inverse semigroups.
In the literature inverse semigroup sometimes also denotes an expansion of a semigroup 〈S,⋅〉 with an additional unary operation −1 satisfying
(see [19, Chap. 5]). Although both concepts are essentially the same in many aspects of semigroup theory, for the inverse semigroup signature {⋅,−1} we may obtain more term operations than for {⋅}. In particular,
Therefore it makes sense to ask whether \(\langle{B_{2}^{1}}, {\cdot ,{}^{-1}} \rangle\) is finitely related or not.Footnote 1 We can answer this question using a straightforward generalization of the argument for Theorem 8.2.
Theorem 8.3
None of the following expansions of the Brandt monoid are finitely related:
-
(1)
the inverse Brandt monoid \(\langle{B_{2}^{1}}, {\cdot,{}^{-1}} \rangle\),
-
(2)
the Brandt monoid with constant operations \(\langle{B_{2}^{1}}, {\cdot ,a,b} \rangle\),
-
(3)
the inverse Brandt monoid with constant operations \(\langle{B_{2}^{1}}, {\cdot,{}^{-1},a,b} \rangle\).
By item (2), (3), respectively, we have that the clone of polynomial operations [9] of \({\mathbf{B}}_{2}^{1}\), \(\langle{B_{2}^{1}}, {\cdot,{}^{-1}} \rangle\), respectively, is also not finitely related.
Proof of Theorem 8.3
We note that
Let n≥3, and let f be the n-ary operation on B 1 that is defined in the proof of Theorem 8.2. Let 1≤i<j≤n. By (8.1), f ij is a term operation on any expansion of \({\mathbf{B}}_{2}^{1}\). We claim that
Suppose otherwise that f is induced by a term t in the signature of \(\langle{B_{2}^{1}}, {\cdot,{}^{-1},a,b} \rangle\). Since (x −1)−1=x and (xy)−1=y −1 x −1 in the variety of inverse semigroups, t can be written as a semigroup word in x 1,…,x n , their inverses \(x_{1}^{-1},\dots,x_{n}^{-1}\) and constants a,b. If t starts with the constant a, then f(a,1,…,1,b) is in \(aB_{2}^{1}\) which contradicts f(a,1,…,1,b)=ba. Similarly t cannot start with b. As noted in the proof of Theorem 8.2, f is invariant under cyclic permutation of arguments. Hence we may assume that t starts with x 1 or \(x_{1}^{-1}\). The argument for Theorem 8.2 yields that x 1 is not possible. But if t begins with \(x_{1}^{-1}\), then f(a,b,1,…,1) is in \(a^{-1}B_{2}^{1} = bB_{2}^{1}\) which contradicts f(a,b,1,…,1)=ab. This completes the proof of (8.2).
By (8.2) f is not a term operation for any reduct of \(\langle{B_{2}^{1}}, {\cdot,{}^{-1},a,b} \rangle\). Thus Lemma 2.1 yields that no algebra A on \(B_{2}^{1}\) with \(\mathrm{Clo}(\langle{B_{2}^{1}}, {\cdot} \rangle) \subseteq\mathrm {Clo}({\mathbf{A}}) \subseteq \mathrm{Clo} (\langle{B_{2}^{1}}, {\cdot,{}^{-1},a,b} \rangle)\) is finitely related. □
Showing that some algebra is not finitely related is usually done by the strategy employed in the proof of Theorem 8.2: it requires to come up with a family of operations f of arbitrary high arity that are not induced by terms but yield term operations whenever 2 arguments of their arguments are identified. Finding appropriate operations can be somehow difficult and depends heavily on the specific algebra. A more general approach that would cover a larger class of algebras at once is to show inherently non-finitely relatedness. We ask in particular:
Problem 8.4
Is every finite semigroup S such that \({\mathbf{B}}_{2}^{1}\) embeds into S not finitely related?
Note that \(B_{2} := B_{2}^{1} \setminus\{1\}\) forms a 5-element subsemigroup of \({\mathbf{B}}_{2}^{1}\). The following remains open:
Problem 8.5
Is the Brandt semigroup B 2:=〈B 2,⋅〉 finitely related?
By Theorem 8.2, a positive answer to the above question would also solve the next one in the affirmative.
Problem 8.6
Is there a finite semigroup S that is finitely related such that S 1 is not finitely related?
We have seen that some inverse semigroups are finitely related (Clifford semigroups, regular bands) while others are not (Brandt monoid) and ask for a complete classification.
Problem 8.7
Characterize the finite, finitely related inverse semigroups.
We conclude with two questions on transformation semigroups.
Problem 8.8
Let n∈ℕ.
-
(1)
Is the full transformation monoid on n letters finitely related?
-
(2)
Is the symmetric inverse semigroup on n letters finitely related?
Notes
After submitting the previous version of this paper, I presented the result for \({\mathbf{B}}_{2}^{1}\) at the Workshop on Semigroups 2012, CAUL, Lisbon. There Stuart Margolis asked about the expanded signature for the inverse Brandt monoid, which led to Theorem 8.3. I am grateful to him and to the anonymous referee, who then also pointed out that the argument for Theorem 8.2 can be generalized to \(\langle{B_{2}^{1}}, {\cdot,{}^{-1}} \rangle\).
References
Aichinger, E., Mayr, P., McKenzie, R.: On the number of finite algebraic structures. J. Eur. Math. Soc. (2011, to appear). Available from arXiv:1103.2265v1
Baker, K.A.: Finite equational bases for finite algebras in a congruence-distributive equational class. Adv. Math. 24(3), 207–243 (1977)
Baker, K.A., Pixley, A.F.: Polynomial interpolation and the Chinese remainder theorem for algebraic systems. Math. Z. 143(2), 165–174 (1975)
Barto, L.: Finitely related algebras in congruence distributive varieties have near unanimity terms. Can. J. Math.. Published electronically: 2011-12-24. doi:10.4153/CJM-2011-087-3
Berman, J., Idziak, P., Marković, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with few subalgebras of powers. Trans. Am. Math. Soc. 362(3), 1445–1473 (2010)
Bodnarčuk, V.G., Kalužnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras. I, II. Kibernetika 3, 1–10 (1969); ibid. 5, 1–9 (1969)
Bova, S., Chen, H., Valeriote, M.: Generic expression hardness results for primitive positive formula comparison. In: 38th International Colloquium on Automata, Languages, and Programming (ICALP), Zürich, Switzerland. Springer, Berlin (2011)
Bryant, R.M.: The laws of finite pointed groups. Bull. Lond. Math. Soc. 14(2), 119–123 (1982)
Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra. Springer, New York (1981)
Clifford, A.H., Preston, G.B.: The Algebraic Theory of Semigroups. Vol. I. Mathematical Surveys, vol. 7. Am. Math. Soc., Providence (1961)
Davey, B.A., Jackson, M.G., Pitkethly, J.G., Szabó, C.: Finite degree: algebras in general and semigroups in particular. Semigroup Forum 83(1), 89–122 (2011)
Dolinka, I.: Finite regular bands are finitely related. Bull. Aust. Math. Soc.. Published online: 15 May 2012, available on CJO 2012. doi:10.1017/S0004972712000263
Evans, T.: The lattice of semigroup varieties. Semigroup Forum 2(1), 1–43 (1971)
Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28(1), 57–104 (1999) (electronic)
Fennemore, C.: All varieties of bands. Semigroup Forum 1(2), 172–179 (1970)
Geiger, D.: Closed systems of functions and predicates. Pac. J. Math. 27, 95–100 (1968)
Gerhard, J.A.: The lattice of equational classes of idempotent semigroups. J. Algebra 15, 195–224 (1970)
Grillet, P.A.: Commutative Semigroups. Advances in Mathematics (Dordrecht), vol. 2. Kluwer Academic, Dordrecht (2001)
Howie, J.M.: Fundamentals of Semigroup Theory. London Mathematical Society Monographs. New Series, vol. 12. Clarendon/Oxford University Press, Oxford (1995). Oxford Science Publications
Jablonskiĭ, S.V.: The structure of the upper neighborhood for predicate-describable classes in P k . Dokl. Akad. Nauk SSSR 218, 304–307 (1974)
Kleitman, D.J., Rothschild, B.R., Spencer, J.H.: The number of semigroups of order n. Proc. Am. Math. Soc. 55(1), 227–232 (1976)
Klíma, O.: Complexity issues of checking identities in finite monoids. Semigroup Forum 79(3), 435–444 (2009)
Koubek, V., Rödl, V.: Note on the number of monoids of order n. Comment. Math. Univ. Carol. 26(2), 309–314 (1985)
Marković, P., Maróti, M., McKenzie, R.: Finitely related clones and algebras with cube terms. Order 29(2), 345–359 (2012)
Mel’nik, I.I.: Varieties and lattices of varieties of semigroups. In: Studies in Algebra, no. 2 (Russian), pp. 47–57. Izdat. Saratov Univ., Saratov (1970)
Perkins, P.: Bases for equational theories of semigroups. J. Algebra 11, 298–314 (1969)
Petrich, M., Reilly, N.R.: Completely Regular Semigroups. Canadian Mathematical Society Series of Monographs and Advanced Texts, vol. 23. Wiley, New York (1999). A Wiley-Interscience Publication
Pöschel, R., Kalužnin, L.A.: Funktionen- und Relationenalgebren. Mathematische Monographien [Mathematical Monographs], vol. 15. VEB Deutscher Verlag der Wissenschaften, Berlin (1979). Ein Kapitel der diskreten Mathematik. [A chapter in discrete mathematics]
Romov, B.A.: Local characteristics of Post algebras. I. Kibernetika 5, 38–45 (1976)
Rosenberg, I.G.: Completeness properties of multiple-valued logic algebras. In: Computer Science and Multiple-Valued Logic: Theory and Applications. North-Holland, Amsterdam (1977)
Rosenberg, I.G., Szendrei, Á.: Degrees of clones and relations. Houst. J. Math. 9(4), 545–580 (1983)
Saliĭ, V.N.: Equationally normal varieties of semigroups. Izv. Vysš. Učebn. Zaved., Mat. 5(84), 61–68 (1969)
Seif, S.: The Perkins semigroup has co-NP-complete term-equivalence problem. Int. J. Algebra Comput. 15(2), 317–326 (2005)
Willard, R.: Essential arities of term operations in finite algebras. Discrete Math. 149(1–3), 239–259 (1996)
Acknowledgements
I want to thank João Araújo, Andreas Distler, and Robert Gray from Centro de Álgebra da Universidade de Lisboa (CAUL) for patiently answering my questions about all aspects of semigroup theory.
I am particularly grateful to Igor Dolinka and the anonymous referee for their diligent reading of the manuscript and for numerous suggestions that led to its improvement.
Open Access
This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Mikhail Volkov.
The author acknowledges support from the Portuguese Project PEst-OE/MAT/UI0143/2011 of CAUL financed by FCT and FEDER, from the Fields Institute, where part of this work was obtained during the author’s stay at the 2011 (Summer) Thematic Program on the Mathematics of Constraint Satisfaction, and from grant P24285 of the Austrian Science Fund FWF.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Mayr, P. On finitely related semigroups. Semigroup Forum 86, 613–633 (2013). https://doi.org/10.1007/s00233-012-9455-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00233-012-9455-6