Abstract
A finite semigroup is finitely related (has finite degree) if its term functions are determined by a finite set of finitary relations. For example, it is known that all nilpotent semigroups are finitely related. A nilpotent monoid is a nilpotent semigroup with adjoined identity. We show that every 4-nilpotent monoid is finitely related. We also give an example of a 5-nilpotent monoid that is not finitely related. To our knowledge, this is the first example of a finitely related semigroup where adjoining an identity yields a semigroup which is not finitely related. We also provide examples of finitely related semigroups which have subsemigroups, homomorphic images, and in particular Rees quotients, that are not finitely related.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The study of finitely related algebraic structures is an area of crucial interest in the field of universal algebra. Historically, finite relatedness has its roots in the general theory of clones [17]. However, its significance became more apparent in the study of the computational complexity of the constraint satisfaction problem (CSP). In particular, the so-called algebraic approach [6] associates with each finite relational constraint language a universal algebra, and (up to term equivalence), the finitely related algebras are precisely the class of algebras that arise in this way. The classification of finitely related algebras generating congruence distributive varieties [3] and eventually, congruence modular varieties [4], were landmark contributions in this regard. For semigroups, extensive characterizations of finite relatedness were presented in [8, 9, 13]. We build upon these foundational contributions in the present paper.
A clone C on a set A is a subset of \(\{ f {:}\,A^n \rightarrow A \mid n \in {\mathbb {N}} \}\) which contains all projections \(e_i^n {:}\,(x_1,\dotsc ,x_n) \mapsto x_i\) for \(1 \le i \le n\), and which is closed under composition, i.e., for n-ary \(f \in C\) and k-ary \(g_1,\dotsc ,g_n \in C\), the composition
is also in C. For a set A and \(k \in {\mathbb {N}}\), a subset \(R \subseteq A^k\) is a k-ary relation on A. We say \(f {:}\,A^n \rightarrow A\) preserves R if \(f(r_1,\dotsc ,r_n) \in R\) whenever \(r_1,\dotsc ,r_n \in R\), where f is applied componentwise. A clone C is finitely related if there are finitely many relations \(R_1,\dotsc ,R_m\) on A such that the elements of C are precisely the functions that preserve \(R_1,\dotsc ,R_m\). Note that every clone on a finite set A can be described by a (possibly infinite) set of finitary relations by a standard result from clone theory. An algebraic structure (or just algebra) \(\textbf{A} = \langle A,F \rangle \) is a nonempty set A together with a set F of finitary functions on A. For algebras and terms in general see [7]. In the case of semigroups, a term \(t(x_1,\dotsc ,x_n)\) is a word in the alphabet \(x_1,\dotsc ,x_n\). For a fixed algebra \(\textbf{A}\), a term \(t(x_1,\dotsc ,x_n)\) induces an n-ary term function \(t^{\textbf{A}} {:}\,A^n \rightarrow A\) by evaluation. The set of all finitary term functions on \(\textbf{A}\) forms the clone of term functions of \(\textbf{A}\) and is denoted by \({{\,\textrm{Clo}\,}}\textbf{A}\). An algebra \(\textbf{A}\) is finitely related if \({{\,\textrm{Clo}\,}}\textbf{A}\) is finitely related.
In [2], Aichinger showed that every finite algebra with few subpowers is finitely related. An algebra \(\textbf{A}\) is said to have few subpowers if there is a polynomial p such that \(\textbf{A}^n\) has at most \(2^{p(n)}\) subalgebras. This includes all finite Mal’cev algebras such as finite groups and rings. Conversely, Barto proved Valeriote’s conjecture [4]: Every finite, finitely related algebra which generates a congruence modular variety has few subpowers. In [14] Moore showed that the question whether a given finite algebra is finitely related is undecidable. As a result, characterizations based on finite relatedness gain greater significance. For further developments on finitely related algebras see also [1, 3, 5, 10, 12, 16].
The characterization of finitely related semigroups began in [8]. Davey et al. showed that nilpotent semigroups and commutative semigroups are finitely related. They also provided examples of finitely related algebras which have homomorphic images, subalgebras, and direct products, respectively, that are not finitely related. Mayr [13] proved that all Clifford semigroups, regular bands (a variety of idempotent semigroups), 3-nilpotent monoids, and semigroups with a single idempotent element are finitely related. He also gave the first known example of a semigroup that is not finitely related, the 6-element Brandt monoid. In [9] Dolinka showed that all finite bands are finitely related.
In this paper, we address the following questions.
-
Up to what \(n \in \mathbb {N}\) are all n-nilpotent monoids finitely related?
-
Are all subsemigroups, homomorphic images, and direct products of a finitely related semigroup also finitely related?
-
If we adjoin an identity to a finitely related semigroup, is the resulting monoid finitely related?
2 Results
For a set A, \(n \in {\mathbb {N}}\), and \(f {:}\,A^n \rightarrow A\), we define new functions by identifying arguments. For \(i,j \in \{1,\dots ,n\}\) with \(i < j\) let
The function \(f_{ij}\) is called an identification minor of f. For an algebraic structure \(\textbf{A}\) we say \(f {:}\,A^n \rightarrow A\) has IMT if every identification minor \(f_{ij}\) is a term function of \(\textbf{A}\).
The following lemma reduces the question whether a finite semigroup is finitely related to a syntactic condition. Instead of explicitly listing the relations describing the clone of term functions, it suffices to show that all functions with IMT above a certain arity are term functions.
Lemma 2.1
[11, 15]. For a finite algebra \(\textbf{A}\) the following are equivalent:
-
(1)
\(\textbf{A}\) is finitely related.
-
(2)
\({{\,\mathrm{\exists }\,}}k \in {\mathbb {N}} {{\,\mathrm{\forall }\,}}n > k:\) every \(f {:}\,A^n \rightarrow A\) with IMT is a term function of \(\textbf{A}\).
In [15] Rosenberg and Szendrei define the degree of \(\textbf{A}\) to be the least k that satisfies condition (2) of Lemma 2.1. The degree is finite if and only if \(\textbf{A}\) is finitely related.
For \(d \in {\mathbb {N}}\) a semigroup \(\textbf{S}\) is d-nilpotent if
\(\textbf{S}\) is nilpotent if it is d-nilpotent for some \(d \in {\mathbb {N}}\). Every nilpotent semigroup has a unique zero element, denoted by 0. Every finite nilpotent semigroup \(\textbf{S}\) is |S|-nilpotent by [8, Theorem 3.3]. The following is a consequence of a result by Willard [19, Lemma 1.2].
Theorem 2.2
[8, Theorem 3.4]. Every finite nilpotent semigroup \(\textbf{S}\) is finitely related with degree at most \(|S|+1\).
A d-nilpotent monoid is a d-nilpotent semigroup with adjoined identity. Mayr showed in [13] that every finite 3-nilpotent monoid \(\textbf{S}\) is finitely related with degree at most \(\max (|S|+1,4)\). We strengthen his result as follows.
Theorem 2.3
Every finite 4-nilpotent monoid \(\textbf{S}\) is finitely related with degree at most \(|S| + 1\).
A subsemigroup \(\textbf{I}\) is an ideal of \(\textbf{S}\) if for all \(i \in I\) and \(s \in S\), both \(s i \in I\) and \(i s \in I\). Every ideal \(\textbf{I}\) of \(\textbf{S}\) induces a congruence \(\theta = (I \times I) \cup \{(s,s) \mid s \in S\}\) which identifies the elements in I. We refer to the quotient \(\textbf{S} \mathbin {/} \theta \) as the Rees quotient of \(\textbf{S}\) by \(\textbf{I}\).
For a nonempty set A, the notation \(\textbf{A}^+\) denotes the free semigroup on A. For \(d \in {\mathbb {N}}\), we define the free d-nilpotent semigroup on A, denoted by \({{\,\mathrm{\textbf{FN}}\,}}_d A\), as the Rees quotient of \(\textbf{A}^+\) with respect to the ideal
If we adjoin an identity to a free nilpotent semigroup, then the resulting monoid is also finitely related:
Theorem 2.4
For a nonempty finite set A and \(d \in {\mathbb {N}}\), \(\textbf{S} := ({{\,\mathrm{\textbf{FN}}\,}}_d A)^1\) is finitely related with degree at most \(|S| + 1\).
The following nilpotent monoid is not finitely related.
Theorem 2.5
Let \(\textbf{S}:= ({{\,\mathrm{\textbf{FN}}\,}}_5 \{a,b\} \mathbin {/}\theta )^1\), where \(\theta \) is the congruence whose equivalence classes are \(\{ (ab)^2, (ba)^2 \}\), \(\{ a^2b^2, b^2a^2 \}\), and the rest singletons. Then \(\textbf{S}\) is not finitely related.
We can now answer the questions from the introduction. The 5-nilpotent semigroup \({{\,\mathrm{\textbf{FN}}\,}}_5 \{a,b\} \mathbin {/}\theta \) is finitely related. Adjoining an identity yields a 5-nilpotent monoid that is not finitely related. In addition, \(({{\,\mathrm{\textbf{FN}}\,}}_5 \{a,b\})^1\) is finitely related by Theorem 2.4. Its homomorphic image \(({{\,\mathrm{\textbf{FN}}\,}}_5 \{a,b\} \mathbin {/}\theta )^1\) is not finitely related. To the best of our knowledge, these are the first examples of such semigroups.
For a signature \({\mathcal {F}}\) and terms \(s(x_1,\dotsc ,x_n)\) and \(t(x_1,\dotsc ,x_n)\) over \({\mathcal {F}}\) an identity is an expression of the form \(s\approx t\). An algebra \(\textbf{A}\) over \({\mathcal {F}}\) satisfies the identity \(s \approx t\) if \(s^{\textbf{A}}(a_1,\dotsc ,a_n) = t^{\textbf{A}}(a_1,\dotsc ,a_n)\) for all \(a_1,\dotsc ,a_n \in A\). A class V of algebras over a signature \({\mathcal {F}}\) is called a variety if there is a set \(\Sigma \) of identities over \({\mathcal {F}}\) such that V contains precisely the algebras that satisfy all identities in \(\Sigma \). By Birkhoff’s HSP theorem a class of algebras is a variety if and only if it is closed under homomorphic images, subalgebras, and direct products. For a variety V, \(V_\text {fin}\) denotes the class that contains all finite members of V.
Theorem 2.6
For a variety V of semigroups, the following are equivalent:
-
(1)
\({{\,\mathrm{\forall }\,}}\textbf{S}, \textbf{T} \in V_\text {fin}\): if \(\textbf{S} \times \textbf{T}\) is finitely related (f.r.), then \(\textbf{S}\) is f.r.
-
(2)
\({{\,\mathrm{\forall }\,}}\textbf{S} \in V_\text {fin}\): if \(\textbf{S}\) is f.r., then every homomorphic image of \(\textbf{S}\) is f.r.
-
(3)
\({{\,\mathrm{\forall }\,}}\textbf{S} \in V_\text {fin}\): if \(\textbf{S}\) is f.r., then every subsemigroup of \(\textbf{S}\) is f.r.
-
(4)
\({{\,\mathrm{\forall }\,}}\textbf{S} \in V_\text {fin}\): if \(\textbf{S}\) is f.r., then every Rees quotient of \(\textbf{S}\) is f.r.
The varieties V that satisfy the conditions in Theorem 2.6 include those of commutative semigroups, bands, and d-nilpotent semigroups for a given \(d \in \mathbb {N}\). Conversely, the variety generated by \(({{\,\mathrm{\textbf{FN}}\,}}_5 \{a,b\})^1\) does not meet these conditions by Theorem 2.5. As a consequence of Theorem 2.6, there exist finitely related semigroups with subsemigroups and Rees quotients that are not finitely related. See Lemma 3.14 for an example.
3 Proofs
Theorem 3.1
[8, Theorem 3.6]. Every finite commutative monoid \(\textbf{S}\) is finitely related with degree at most \(\max (|S|,3)\).
Note that the original result in [8] only claims that the degree is at most \(\max (|S|, 4)\), but the proof actually yields the slightly stronger version given above.
A function \(f {:}\,A^n \rightarrow A\) depends on its i-th argument if there are \(a, b \in A^n\) such that \(a_j = b_j\) for all \(j \ne i\) and \(f(a) \ne f(b)\). For \(n \in {\mathbb {N}}\) we write \([n]\) instead of \(\{1,\dotsc ,n\}\). Now let \(m \le n\) in \({\mathbb {N}}\) and \(i_1< \cdots < i_m\) in \([n]\). Let \(y_1,\dotsc ,y_m\) be elements of a monoid \(\textbf{S}\). For a tuple \(x \in S^n\) with
we also write
The arity of x will be clear from the context. For a term \(t(x_1,\dotsc ,x_n)\),
denotes the term obtained when \(x_{i_k}\) is replaced by \(y_k\) for \(k \in [m]\) and the remaining \(x_j\) are removed.
Lemma 3.2
[13, Lemma 2.6]. Let A be a finite set, \(n>|A|+1\), and \(f{:}\,A^n \rightarrow \) A. If f depends on its ith argument for some \(i \in [n]\), then there exist \(\ell < m\) in \([n] \backslash \{i\}\) such that \(f_{\ell m}\) depends on its ith argument.
Note that the bound \(|A| + 1\) cannot be reduced to |A| in Lemma 3.2. Here is a simple counter example. Let \(A = \{0, 1\}\), \(n = 3\), and \(f {:}\,A^n \rightarrow A\) such that \(f_{12} = f_{13} = x_3\) and \(f_{23} = x_1\). Verify that f exists by creating the value table. Then f depends on \(x_2\) since \(f(0, 0, 1) = 1 \ne 0 = f(0, 1, 1)\). However, none of the identification minors depends on \(x_2\).
Lemma 3.3
Let \(\textbf{S}\) be a finite monoid. Let \(n > |S| + 1\) and let \(f {:}\,S^n \rightarrow S\) have IMT and depend on its ith argument. Then there exists \(e_i \in \mathbb {N}\) such that
We refer to the minimal such \(e_i\) as the variable exponent of \(x_i\) in f.
Proof
For \({\textbf{S}}\) of size 1, the lemma holds trivially. Assume \(|S| \ge 2\). By Lemma 3.2, there exist \(k < \ell \) in \([n]{\setminus }\{i\}\) such that \(f_{k \ell }\) depends on \(x_i\). Let t be a term that induces \(f_{k \ell }\). Since \(t^\textbf{S}\) depends on its ith argument, \(x_i\) occurs \(e_i \in \mathbb {N}\) times in \(t(x_1, \dots , x_n)\). We obtain
which proves the Lemma. \(\square \)
Lemma 3.4
Let \(\textbf{S}\) be a finite nilpotent monoid and \(c \in {\mathbb {N}}\) minimal such that \(S {\setminus } \{1\}\) satisfies \(x^c \approx 0\). Let \(n > |S| + 1\) and let \(f {:}\,S^n \rightarrow S\) have IMT and depend on all variables. Let \(e_1,\dotsc ,e_n\) be the variable exponents of f. Then each term t inducing an identification minor \(f_{ij}\) has the following properties:
-
(1)
\(x_i\) does not occur in t,
-
(2)
for \(k\in [n]{\setminus } \{i,j\}\), \(x_k\) occurs \(e_k\) times if \(e_k < c\), and at least c times otherwise,
-
(3)
\(x_j\) occurs \(e_i + e_j\) times if \(e_i + e_j < c\), and at least c times otherwise.
Proof
Let \(f_{ij}\) be an identification minor with \(i < j\) in \([n]\) induced by some term t. Since every nilpotent monoid has at least two elements by definition, we have \(n \ge |S| + 2 \ge 4\).
-
(1)
Suppose \(x_i\) occurs in t. Then we obtain the contradiction
$$\begin{aligned} 1 = f(1,\dotsc ,1) = f_{ij}({\bar{1}}, \underset{i}{0}, {\bar{1}}) = t^\textbf{S}({\bar{1}}, \underset{i}{0}, {\bar{1}}) = 0. \end{aligned}$$ -
(2)
Let \(k\in [n]{\setminus } \{i,j\}\). Then
$$\begin{aligned}t({\bar{1}}, \underset{k}{x_k}, {\bar{1}}) \,\text {induces}\, f({\bar{1}}, \underset{k}{x_k}, {\bar{1}}). \end{aligned}$$Note that \(x,x^2,\dotsc ,x^{c-1}\) are pairwise inequivalent terms in \(\textbf{S}\), while \(x^c,x^{c+1},\dotsc \) are all equivalent. Thus, if \(e_k < c\), then \(x_k\) occurs precisely \(e_k\) times in t. If \(e_k \ge c\), then \(x_k\) occurs at least c times in t.
-
(3)
Let \(k < \ell \) in \([n] {\setminus } \{i,j\}\) and s be a term that induces \(f_{k\ell }\). Then
$$\begin{aligned} t({\bar{1}}, \underset{j}{x_j}, {\bar{1}})\, \text {and}\, s({\bar{1}}, \underset{i}{x_j}, {\bar{1}}, \underset{j}{x_j}, {\bar{1}})\, \text {both induce}\, f({\bar{1}}, \underset{i}{x_j}, {\bar{1}}, \underset{j}{x_j}, {\bar{1}}). \end{aligned}$$
If \(e_i + e_j < c\), then by (2) \(x_i\) and \(x_j\) occur \(e_i\) and \(e_j\) times in s, respectively. Thus \(x_j\) occurs \(e_i + e_j\) times in t. If \(e_i + e_j \ge c\), then \(x_i\) and \(x_j\) occur at least \(\min (e_i, c)\) and \(\min (e_j, c)\) times in s, respectively, again by (2) Thus \(x_j\) occurs at least c times in t. \(\square \)
Lemma 3.5
Let \(\textbf{A}\) be a finite algebra, \(n \ge 2\), and let \(f {:}\,A^n \rightarrow A\) have IMT. If f does not depend on one of its variables, then f is a term function.
Proof
W.l.o.g. we can assume that f does not depend on \(x_1\). Then \(f = f_{12}\), which is a term function. \(\square \)
Lemma 3.6
Let \(d \ge 2\), let A be a finite set with \(|A| \ge 2\), and let \(\textbf{S}:= ({{\,\mathrm{\textbf{FN}}\,}}_d A)^1\). Let \(t(x_1,\dotsc ,x_n)\) be a term with \(e_i\) occurrences of \(x_i\) for \(i \in [n]\).
-
(1)
If \(e_1 + \cdots + e_n < d\), then t is the unique term inducing \(t^\textbf{S}\).
-
(2)
If \(n = 2\) and \(e_1 + e_2 \ge d\), then each permutation of t induces \(t^\textbf{S}\).
Proof
-
(1)
Assume \(e_1 + \cdots + e_n < d\) and let s be another term that induces \(t^\textbf{S}\). Our aim is to show that \(t = s\). If \(t \ne s\), then there exist terms u, v, w and distinct indices \(i,j \in [n]\) such that
$$\begin{aligned}\begin{aligned} t&= u(x_1, \dots , x_n) \, x_i \, v(x_1, \dots , x_n) \\ s&= u(x_1, \dots , x_n) \, x_j \, w(x_1, \dots , x_n). \end{aligned}\end{aligned}$$W.l.o.g. assume \(i < j\). Pick \(a \ne b\) from A. Then
$$\begin{aligned}\begin{aligned} t^{\textbf{S}}(\bar{1},\underset{i}{a},\bar{1},\underset{j}{b},\bar{1})&= u^{\textbf{S}}(\bar{1},\underset{i}{a},\bar{1},\underset{j}{b},\bar{1}) \, a \, v^{\textbf{S}}(\bar{1},\underset{i}{a},\bar{1},\underset{j}{b},\bar{1}) \\&\ne u^{\textbf{S}}(\bar{1},\underset{i}{a},\bar{1},\underset{j}{b},\bar{1}) \, b \, w^{\textbf{S}}(\bar{1},\underset{i}{a},\bar{1},\underset{j}{b},\bar{1}) \\&= s^{\textbf{S}}(\bar{1},\underset{i}{a},\bar{1},\underset{j}{b},\bar{1}) \end{aligned}\end{aligned}$$by the definition of \(({{\,\mathrm{\textbf{FN}}\,}}_d A)^1\) and since the left hand side of the inequality is \({} \ne 0\). This contradicts the fact that s induces \(t^{\textbf{S}}\). Thus \(t = s\).
-
(2)
Assume \(n = 2\) and \(e_1 + e_2 \ge d\). Let s be a permutation of t and \(u, v \in S\). If both u and v are distinct from 1, then \(t^\textbf{S}(u, v) = 0 = s^\textbf{S}(u, v)\) by d-nilpotence. If \(u = 1\), then \(t^\textbf{S}(u, v) = v^{e_2} = s^\textbf{S}(u, v)\). If \(v = 1\), the equation follows similarly. \(\square \)
Lemma 3.7
Let \(\langle V, \mathrel {E} \rangle \) be a finite, cycle-free digraph. Then there exists a linear order on V that includes \(\mathrel {E}\).
Proof
First observe that the reflexive transitive closure S of E is a partial order. By the Szpilrajn extension theorem [18], there exists a linear order that includes S. \(\square \)
Proof of Theorem 2.4
First assume \(d \le 2\) or \(|A| = 1\). Then \(\textbf{S}\) is commutative. By Theorem 3.1\(\textbf{S}\) is finitely related with degree at most \(\max (|S|,3)\). If \(|S|=1\), then \(\textbf{S}\) is finitely related with degree 1. Thus the degree is at most \(|S|+1\).
Now assume \(d \ge 3\) and \(|A| \ge 2\). Let \(n > |S| + 1\) and let \(f {:}\,S^n \rightarrow S\) have IMT. Note that \(|S| \ge d + 1\) and thus \(n \ge 6\). By Lemma 3.5 we can assume that f depends on all variables. Let \(e_1,\dotsc ,e_n\) be the variable exponents of f defined in Lemma 3.3. We will construct a term \(s(x_1,\dotsc ,x_n)\) that induces f with \(e_i\) occurrences of \(x_i\) for \(i \in [n]\). We enumerate the occurrences of \(x_i\) by a second index \(\alpha \in [e_i]\). To this end, let
Let \(i < j\) in \([n]\) with \(e_i + e_j < d\). By IMT and Lemma 3.6
By Lemma 3.4\(h_{ij}\) has \(e_i\) occurrences of \(x_i\) and \(e_j\) occurrences of \(x_j\). We define a strict linear order \(<_{ij}\) on the subset \(\{ x_{i \alpha } \mid \alpha \in [e_i] \} \cup \{ x_{j \beta } \mid \beta \in [e_j] \}\) of X. For \(k, \ell \in \{i, j\}\) let
if the \(\alpha \)th occurrence of \(x_k\) precedes the \(\beta \)th occurrence of \(x_\ell \) in \(h_{ij}\). Let \(\prec \) be the relation on X such that
We claim that
Suppose there is a cycle \(c = (x_{i_1\alpha _1}, \dotsc , x_{i_m\alpha _m}, x_{i_1\alpha _1})\) of minimal length m. We show that
Suppose \(i_u = i_v\) for \(u < v\) in \([m]\). If \(\alpha _u \le \alpha _v\), then \(x_{i_{u-1}\alpha _{u-1}} \prec x_{i_v\alpha _v}\) and
is a cycle shorter than c. If \(\alpha _v < \alpha _u\), then \(x_{i_{v-1}\alpha _{v-1}} \prec x_{i_u\alpha _u}\) and
is a cycle shorter than c. This proves (3.3). W.l.o.g. we can assume that \(i_1=1,\dotsc ,i_m=m\).
Let \(\oplus \) and \(\ominus \) be addition and subtraction modulo m on the set \([m]\), respectively. By the definition of \(\prec \) we have
Assume \(m \le n-2\). Then \(f(x_1,\dotsc ,x_m, {\bar{1}}) = f_{n-1, n}(x_1, \dotsc , x_m, {\bar{1}})\) is induced by some term t. For all \(i < j\) in \([m]\) we have
by (3.1). But then the order of the variables in \(t(x_1, \dots , x_m)\) prevents the cycle c.
Now assume \(m \ge n-1\). Pick i such that \(e_i = \max (e_1, \dotsc , e_m)\). By (3.4) we have \(e_{i \ominus 1} + e_i < d\) and \(e_i + e_{i\oplus 1} < d\). Thus \(e_{i \ominus 1} + e_{i \oplus 1} < 2d - 2e_i\). From the maximality of \(e_i\) we obtain \(e_{i \ominus 1} + e_{i \oplus 1} \le 2 e_i\). Adding these inequalities yields \(e_{i \ominus 1} + e_{i \oplus 1} < d\). Thus \(x_{i \ominus 1,\alpha _{i \ominus 1}}\) and \(x_{i \oplus 1,\alpha _{i \oplus 1}}\) are related by \(<_{i \ominus 1, i \oplus 1}\). From that and \(m \ge n-1 \ge 5\) it follows that we can reduce c to a shorter cycle. This contradicts the minimality of m. We proved (3.2).
By Lemma 3.7 there is a linear order < on X that includes \(\prec \). We order the elements of X by < and drop the second index. Let \(t(x_1,\dotsc ,x_n)\) be the resulting term. We claim that
Fix \(a \in S^n\). Let \(i_1< \cdots < i_k\) in \([n]\) be the positions where a is \({} \ne 1\). First assume \(e_{i_1} + \cdots + e_{i_k} \ge d\). Then \(t^\textbf{S}(a) = 0\) by d-nilpotence. Since \(n > |S|\), there are \(i < j\) in \([n]\) such that \(a_i = a_j\). Thus \(f(a) = f_{ij}(a)\). Note that \(d \in \mathbb {N}\) is minimal such that \(S {\setminus } \{1\}\) satisfies \(x^d \approx 0\). By Lemma 3.4 the product \(f_{ij}(a)\) has at least d factors \(\ne 1\). Hence \(f(a) = f_{ij}(a) = 0 = t^\textbf{S}(a)\).
Now assume \(e_{i_1} + \cdots + e_{i_k} < d\). Note that \(k< d< |S| < n\). Thus \(n-k \ge 2\) arguments are 1. By IMT
We have \(s({\bar{1}},\underset{i}{x_{i}},\bar{1},\underset{j}{x_{j}},{\bar{1}}) = h_{ij}\) for all \(i < j\) in \(\{i_1, \dots , i_k\}\). This means the variables of s are ordered by \({<_s} := \bigcup \{ {<_{ij}} \mid i < j \text { in }\{i_1, \dots , i_k\} \}\). Thus < includes \(<_s\), and the latter is also a linear order. Therefore
Hence \(t^\textbf{S}(a) = s^\textbf{S}(a) = f(a)\). This proves (3.5). By Lemma 2.1\(\textbf{S}\) is finitely related. \(\square \)
Lemma 3.8
Let \(\textbf{S}\) be a d-nilpotent monoid. Let \(n > |S| + 1\) and let \(f {:}\,S^n \rightarrow S\) have IMT and depend on all variables. Let \(e_1,\dotsc ,e_n\) be the variable exponents of f and assume that
for some \(r \in \{0,\dotsc ,n\}\). Then for all \(a_1, \dots , a_n \in S\),
Proof
Fix \(a \in S^n\). Let \(c \in \mathbb {N}\) be minimal such that \(S {\setminus } \{1\}\) satisfies \(x^c \approx 0\). By the minimality of \(e_i\), as defined in Lemma 3.3, we have \(e_i \le c\) for all i. If \(c \le d-2\), then \(e_i \le d-2\) for all i. Then \(r = n\) and there is nothing to prove. Thus assume
Let \(g(a_1,\dotsc ,a_n)\) be the right hand side of (3.7). If \(a_{r+1} = \cdots = a_n = 1\), then \(f(a) = g(a)\). Assume \(a_k \ne 1\) for some \(k \in \{r+1,\ldots ,n\}\). If \(a_\ell = 1\) for all \(\ell \in [n]{\setminus }\{k\}\), then \(f(a) = a_k^{e_k} = g(a)\). Assume \(a_\ell \ne 1\) for some \(\ell \in [n]{\setminus }\{k\}\). Then \(g(a) = 0\) since there are at least d factors \({}\ne 1\). Since \(n > |S|\), there are \(i < j\) in \([n]\) such that \(a_i = a_j\). Let t be a term inducing \(f_{ij}\). Then \(f(a) = t^\textbf{S}(a)\). We show that
For both \(k = i\) and \(k \ne i\), the factor \(a_k\) occurs at least \(c \ge d-1\) times in \(t^\textbf{S}(a)\) by (3.8) and Lemma 3.4. Since \(a_\ell \ne 1\), there are at least d factors \(\ne 1\) in \(t^\textbf{S}(a)\), and (3.9) follows. Hence \(f(a) = g(a)\), and (3.7) is proved. \(\square \)
Proof of Theorem 2.3
First assume \(\textbf{S}\) is commutative. By Theorem 3.1\(\textbf{S}\) is finitely related with degree at most \(\max (|S|,3)\). Since \(|S| \ge 2\), the degree is at most \(|S|+1\).
Assume \(\textbf{S}\) is noncommutative. Let \(d \in \mathbb {N}\) be minimal such that \(S {\setminus } \{1\}\) is d-nilpotent. Let \(c \in {\mathbb {N}}\) be minimal such that \(S{\setminus } \{1\}\) satisfies \(x^c \approx 0\). Let \(n > |S| + 1\) and let \(f {:}\,S^n \rightarrow S\) have IMT. The minimality of c and d and the noncommutativity of \(\textbf{S}\) yield \(d \le |S {\setminus } \{1\}|\) and
By Lemma 3.5 we can assume that f depends on all variables. Let \(e_1,\dotsc ,e_n\) be the variable exponents of f defined in Lemma 3.3. By reordering variables we assume there are \(r\le s\) in \(\{0,\dotsc ,n\}\) such that
We claim the following.
Since \(n > |S|\) there are \(i < j\) in \([n]\) with \(a_i = a_j\). Assume \(a_i = a_j = 1\) if \(m \le n - 2\) and \(a_i = a_j \ne 1\) otherwise. In both cases we obtain \(f(a) = f_{ij}(a) = 0\) by Lemma 3.4 and d-nilpotence. This proves (3.10).
For \(r \ge 1\), we construct a term that induces \(f(x_1,\dotsc ,x_r,{\bar{1}})\). If \(r = 1\), this term is \(x_1^{e_1}\). For \(r \ge 2\) and \(i < j\) in \([r]\), we can identify two 1’s in
since \(n \ge 6\). Thus (3.11) is a term function. By Lemma 3.4\(x_i\) and \(x_j\) each occur once in each term inducing (3.11). Since \(\textbf{S}\) is noncommutative, (3.11) is induced by either \(x_ix_j\) or \(x_jx_i\). This motivates a relation < on \(\{x_1,\dotsc ,x_r\}\). Let
We show that < is transitive. Assume \(x_i < x_j\) and \(x_j < x_k\) for \(i,j,k \in [r]\). We can identify two 1’s in the expression
Thus (3.12) is a term function induced by some term t. By Lemma 3.4\(x_i\), \(x_j\), and \(x_k\) each occur once in t. We have \(t(x_i,x_j,1) = x_i x_j\) and \(t(1,x_j,x_k) = x_j x_k\). Thus \(t = x_i x_j x_k\), which implies \(x_i < x_k\). Now < is a strict linear order on \(x_1, \dots , x_r\). By reordering variables we can assume that \(x_1< \cdots < x_r\). Now we claim that
Fix \(a:= (a_1,\dotsc ,a_r,{\bar{1}}) \in S^n\). Let \(i_1< \cdots < i_m\) in \([r]\) be the positions where a is \({} \ne 1\). If \(m \ge d\), then \(f(a) = 0 = a_1 \cdots a_r\) by (3.10) and d-nilpotence. If \(m < d\), then we can identify two 1’s. By IMT there is a term \(t(x_{i_1},\dotsc ,x_{i_m})\) such that
Since \(e_1 = \cdots = e_r = 1\) and by Lemma 3.4, each of the variables \(x_{i_1}, \dots , x_{i_m}\) occurs exactly once in t. Now \(x_{i_1}< \cdots < x_{i_m}\) implies \(t = x_{i_1} \cdots x_{i_m}\). Thus \(f(a) = a_{i_1} \cdots a_{i_m} = a_1 \cdots a_r\). This proves (3.13).
If \(d=3\), then Lemma 3.8 implies
which is a term function by (3.13).
For the rest of the proof assume \(d=4\). Lemma 3.8 implies
We claim that
If \(s \le n-2\), then (3.15) holds since we can identify two 1’s. Thus assume \(s \ge n-1\) for the rest of the proof.
First assume \(r = 0\). Let \(t := x_1^2 \cdots x_s^2\) and \(a = (a_1,\dotsc ,a_s,{\bar{1}}) \in S^n\). We claim that
Let \(i_1< \cdots < i_m\) in \([s]\) be the positions where a is \({} \ne 1\). If \(m \ge 2\), then \(f(a) = 0 = t^\textbf{S}(a)\) by (3.10) and 4-nilpotence. If \(m = 1\), then \(f(a) = a_{i_1}^2 = t^\textbf{S}(a)\) since \(e_{i_1} = 2\). If \(m = 0\), then \(f(a) = 1 = t^\textbf{S}(a)\). This proves (3.16) and (3.15) for \(r = 0\).
Next assume \(r > 0\). For each \(i\in [r]\) and \(m \in \{r+1,\dotsc ,s\}\) we pick a term \(w_{im}(x_i,x_m)\) such that
By Lemma 3.4\(x_i\) occurs once and \(x_m\) twice in \(w_{im}\). Thus
Later in the proof, we will extend the term \(x_1 \cdots x_r\) by adding two occurrences of \(x_m\) for each \(m \in \{r+1,\dotsc ,s\}\).
Now we claim that for each \(m \in \{r + 1, \dots , s\}\) there exist \(\alpha < \beta \) in \(\{ 0,\dotsc ,r+1 \}\) such that
We consider two cases, one where \(\textbf{S}\) satisfies \(x y^2 \approx y^2 x\) and another where it does not.
Case 1,
For \(i < j\) in \([r]\) and \(m \in \{r+1,\dotsc ,s\}\) we claim that
To prove (3.19) assume that \(w_{im} \approx x_m^2 x_i\). By IMT there is some term \(v(x_i, x_j, x_m)\) such that
By the definition of \(w_{im}\) and (3.18) we have
Since \(x_i < x_j\) we have
By Lemma 3.4 the variables \(x_i,x_j\) occur once and \(x_m\) twice in v. From (3.21) and (3.22) it follows that
If \(v = x_m x_i x_j x_m\), then
and thus \(\textbf{S}\) satisfies \(x^2 y \approx xyx\). Then
On the other hand, if v is one of the last two terms in (3.23), we directly get
This proves (3.19). The proof of (3.20) follows from a symmetric argument.
To prove (3.17), let \(m \in \{r + 1, \dots , s\}\). Let \(\alpha \in [r]\) be maximal such that \(w_{\alpha m} \approx x_\alpha x_m^2\) and set \(\alpha =0\) if no such \(\alpha \in [r]\) exists. Then \(w_{i m} \approx x_i x_m^2\) for all \(i \le \alpha \) by (3.20). Let \(\beta \in [r]\) be minimal such that \(w_{\beta m} \approx x_m^2 x_\beta \) and set \(\beta =r+1\) if no such \(\beta \in [r]\) exists. Then \(w_{i m} \approx x_m^2 x_i\) for \(\beta \le i \le r\) by (3.19). Since \(x y^2 \not \approx y^2 x\) in \({\textbf{S}}\), we have \(\alpha <\beta \) and \(w_{i m} \approx x_m x_i x_m\) for \(\alpha<i<\beta \). This proves (3.17) for case 1.
Case 2,
For \(i< j < k\) in \([r]\) and \(m \in \{r+1,\dotsc ,s\}\) we claim that
Assume \(w_{im} \approx x_m x_i x_m\) and \(w_{km} \approx x_m x_k x_m\). Since \(n \ge 6\) we can identify two 1’s in
By IMT there is a term \(v(x_i,x_j,x_k,x_m)\) which induces (3.26). By Lemma 3.4 the variables \(x_i,x_j,x_k\) occur once and \(x_m\) twice in v. Since \(x_i< x_j < x_k\), it follows that \(x_i\) occurs before \(x_j\) and \(x_j\) before \(x_k\) in v. Observe that
If \(xyx \not \approx x^2y \approx yx^2\) in \(\textbf{S}\), then \(v = x_m x_i x_j x_k x_m\). If \(xyx \approx x^2y \approx yx^2\), then the \(x_m\) can be moved to any position in (3.27). Both scenarios yield \(v \approx x_m x_i x_j x_k x_m\). We obtain
which proves (3.25).
To prove (3.17), let \(m \in \{r + 1, \dots , s\}\). If \(w_{im} \not \approx x_m x_i x_m\) for all \(i \in [r]\), set \(\alpha =0\) and \(\beta = 1\). Then (3.24) implies (3.17). If \(w_{im} \approx x_m x_i x_m\) for some \(i \in [r]\), let \(\alpha \in \{0, \dots , r-1\}\) be minimal such that \(w_{\alpha +1, m} \approx x_m x_{\alpha +1} x_m\) and let \(\beta \in \{2, \dots , r+1\}\) be maximal such that \(w_{\beta -1, m} \approx x_m x_{\beta -1} x_m\). Then (3.25) yields \(w_{i m} \approx x_m x_i x_m\) for \(\alpha<i<\beta \). This and (3.24) yield (3.17).
Using (3.17) we construct a term t that induces \(f(x_1,\dotsc ,x_s,{\bar{1}})\). For each \( m \in \{r + 1, \dots , s\} \), we insert two occurrences of \( x_m \) into \( x_1 \cdots x_r \) to get
We repeat this procedure for all such m and denote the final term by t. Note that for different m the new variables can be inserted independently from each other since all permutations of \(x_{r+1}^2 \cdots x_s^2\) are equivalent terms in \(\textbf{S}\) by 4-nilpotence. For \(i \in [r]\) and \(m \in \{r+1,\dotsc ,s\}\) we obtain
from (3.17). For \(a = (a_1,\dotsc ,a_s,\bar{1}) \in S^n\), we claim that
Let \(i_1< \cdots < i_\ell \) in \([s]\) be the positions where a is \({} \ne 1\). If \(e_{i_1} + \cdots + e_{i_\ell } \ge 4\), then \(f(a) = 0 = t^\textbf{S}(a)\) by (3.10) and 4-nilpotence. If \(a_{r+1} = \dots = a_s = 1\), then \(f(a) = a_1 \dots a_r = t^\textbf{S}(a)\) by (3.13). If \(e_{i_1} + \cdots + e_{i_\ell } < 4\) and \(a_m \ne 1\) for some \(m \in \{r + 1, \dots , s\}\), then a is of the form
Now (3.28) yields \(t^\textbf{S}(a) = w_{im}^\textbf{S}(a_i,a_m) = f(a)\). This proves (3.29) and (3.15). By (3.14) f is a term function. By Lemma 2.1\(\textbf{S}\) is finitely related with degree at most \(|S| + 1\). \(\square \)
Proof of Theorem 2.5
The relation \(\theta \) is a congruence on \({{\,\mathrm{\textbf{FN}}\,}}_5 \{a,b\}\) since the elements in the nontrivial equivalence classes have 4 factors and \({{\,\mathrm{\textbf{FN}}\,}}_5 \{a,b\}\) is 5-nilpotent. Furthermore,
For \(n \ge 4\) we define \(f {:}\,S^n \rightarrow S\) as follows. Let
and for \(i < j\) in \([n]\) let
First we show that
For \(i,j \in [n]\) let \(\ell := (j - i \mod n) + 1\). We define a term \(g_{ij}\) of length \(2 \ell \). Let \(\oplus \) and \(\ominus \) be addition and subtraction modulo n on the set \([n]\), respectively. Let
For \(i \ne j\) let \(g_{ij}^{(k)}\) denote the variable in the k-th position of \(g_{ij}\) and
Note that if \(i < j\), then \(g_{ij}\) contains all variables in \(\{x_i, \dots , x_j\}\) exactly twice. Conversely, if \(i > j\), then \(g_{ij}\) contains all variables in \(\{x_i, \dots , x_n, x_1, \dots , x_j\}\) exactly twice. For example, for \(n=5\) we have \(g_{42} = x_4 x_5 x_4 x_1 x_5 x_2 x_1 x_2\).
Now let \(i < j\) in \([n]\) and
We claim that
Note that \(x_k\) occurs twice in h for \(k \in [n] {\setminus } \{i,j\}\), whereas \(x_i\) and \(x_j\) do not occur. Fix \(i < j\) in \([n]\) and \(c \in S^n\).
Case, \(c_j \ne 1\) and \(c_k = 1\) for all \(k \in [n]{\setminus }\{i,j\}\). Then \(h(c) = 1\) and \(r(c) = c_j^4 = f_{ij}(c)\).
Case, \(c_j \ne 1\) and \(c_k \ne 1\) for some \(k \in [n]{\setminus }\{i,j\}\). Then \(h(c) \ne 1\) and \(r(c) = c_j^4 \, h(c) = 0 = f_{ij}(c)\) by 5-nilpotence.
Case, \(c_j = 1\) and at least 3 positions of c among \([n] {\setminus } \{i,j\}\) are \({} \ne 1\). Then \(h(c) = 0\) by 5-nilpotence. Thus \(r(c) = 0 = f_{ij}(c)\).
Case, \(c_j = 1\) and at most 2 positions of c among \([n] {\setminus } \{i,j\}\) are \({} \ne 1\). Pick \(k < \ell \) in \([n] {\setminus } \{i,j\}\) such that all positions of c among \([n] {\setminus } \{i,j,k,\ell \}\) are 1. Let \(A := \{i+1, \dots , j-1\}\) and \(B := \{1, \dots , i - 1, j + 1, \dots , n\}\). If \(k, \ell \in A\), then \(h(c) = g_{i + 1, j - 1}(c)\). If \(k, \ell \in B\), then \(h(c) = g_{j \oplus 1, i \ominus 1}(c)\). If \(k \in A\) and \(\ell \in B\), then \(g_{j \oplus 1, i \ominus 1}(c) = c_\ell ^2\) and \(g_{i + 1, j - 1}(c) = c_k^2\), and thus \(h(c) = c_\ell ^2 c_k^2\). If \(k \in B\) and \(\ell \in A\), then similarly \(h(c) = c_k^2 c_\ell ^2\). By the identities (3.30) we have
By definition,
is also equal to (3.33). Thus \(f_{ij}(c) = r(c)\). This proves (3.32). Thus every \(f_{ij}\) is a term function, and (3.31) follows.
Next we claim that
Suppose f is induced by some term t. Recall that \(a \in S\). Every variable \(x_i\) occurs twice in t since
By (3.30) and the definition of f, we have \(t^{\textbf{S}}(x_1,\dotsc ,x_n) = t^{\textbf{S}}(x_2,\dotsc ,x_n,x_1)\). Thus we can assume that t starts with \(x_2\). By the definition of f, the following equivalences hold in \(\textbf{S}\).
Thus \(x_1\) and \(x_3\) each occur once between the two occurrences of \(x_2\) in t, whereas \(x_4,\dotsc ,x_n\) do not occur between the two \(x_2\)’s. So t starts either with \(x_2 x_1 x_3 x_2\) or with \(x_2 x_3 x_1 x_2\). Hence
So \(t(x_1,1,x_3,{\bar{1}})\) and \(x_1^2 x_3^2\) cannot be equivalent. Since \(n \ge 4\), this contradicts the definition of f. We proved (3.34). By (3.31), (3.34), and Lemma 2.1, \(\textbf{S}\) is not finitely related. \(\square \)
The following was proved independently by the authors of [8] and Marković et al. [12].
Theorem 3.9
[8, Theorem 2.11], [12, Corollary 4.3]. Let \(\textbf{A},\textbf{B}\) be finite algebras that generate the same variety. Then \(\textbf{A}\) is finitely related if and only if \(\textbf{B}\) is.
Lemma 3.10
For a variety V, the following two conditions are equivalent:
-
(1)
\({{\,\mathrm{\forall }\,}}\textbf{A}, \textbf{B} \in V_\text {fin}\): if \(\textbf{A} \times \textbf{B}\) is finitely related (f.r.), then \(\textbf{A}\) is f.r.
-
(2)
\({{\,\mathrm{\forall }\,}}\textbf{A} \in V_\text {fin}\): if \(\textbf{A}\) is f.r., then every homomorphic image of \(\textbf{A}\) is f.r.
These conditions imply the following:
-
(3)
\({{\,\mathrm{\forall }\,}}\textbf{A} \in V_\text {fin}\): if \(\textbf{A}\) is f.r., then every subalgebra of \(\textbf{A}\) is f.r.
Proof
Clearly (2) implies (1). Assume (1) holds. Let \(\textbf{B}\) be a homomorphic image of \(\textbf{A}\). Then \(\textbf{A}\) and \(\textbf{A} \times \textbf{B}\) generate the same variety. By Theorem 3.9\(\textbf{A} \times \textbf{B}\) is also finitely related. By (1) \(\textbf{B}\) is finitely related. This proves (2). The fact that (1) implies (3) is proved similarly. \(\square \)
For a semigroup \(\textbf{S}\) let \(\textbf{S} \sqcup \{0\}\) denote the semigroup obtained when we adjoin a (possibly additional) zero element, where we extend the multiplication by \(s \cdot 0 := 0 \cdot s := 0 \cdot 0 := 0\) for all \(s \in S\).
Theorem 3.11
[13, Theorem 4.1]. A finite semigroup \(\textbf{S}\) is finitely related if and only if \(\textbf{S} \sqcup \{0\}\) is finitely related.
Let \(\textbf{S}^0\) denote the semigroup
For two semigroups \(\textbf{S}\) and \(\textbf{T}\) with \(S^0 \cap T^0 = \{0\}\), we define the 0-direct union \(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\) to be the semigroup with universe \(S^0 \cup T^0\) and multiplication
The variety generated by an algebra \(\textbf{A}\) is denoted by \({{\,\textrm{Var}\,}}\textbf{A}\).
Lemma 3.12
For finite semigroups \(\textbf{S}\) and \(\textbf{T}\) we have \( {{\,\textrm{Var}\,}}(\textbf{S} \times \textbf{T})^0 = {{\,\textrm{Var}\,}}\textbf{S}^0 \times \textbf{T}^0 = {{\,\textrm{Var}\,}}\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}. \)
Proof
Since \(\textbf{S}\) and \(\textbf{T}\) are finite, both have an idempotent element. For the first equality observe that both \(\textbf{S}^0\) and \(\textbf{T}^0\) embed into \((\textbf{S} \times \textbf{T})^0\). Conversely \((\textbf{S} \times \textbf{T})^0\) is a subsemigroup of \(\textbf{S}^0 \times \textbf{T}^0\).
We show the second equality. Both \(\textbf{S}^0\) and \(\textbf{T}^0\) are subsemigroups of \(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\). Conversely \(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\) embeds into \(\textbf{S}^0 \times \textbf{T}^0\) via \(S \rightarrow S \times \{0\}\), \(T \rightarrow \{0\} \times T\), and \(0 \mapsto (0,0)\). \(\square \)
Lemma 3.13
For finite semigroups \(\textbf{S}\) and \(\textbf{T}\), \(\textbf{S} \times \textbf{T}\) is finitely related if and only if \(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\) is finitely related.
Proof
By Theorem 3.11\(\textbf{S} \times \textbf{T}\) is finitely related if and only if \((\textbf{S} \times \textbf{T})^0\) is finitely related. Now the result is immediate from Theorem 3.9 and Lemma 3.12. \(\square \)
Proof of Theorem 2.6
By Lemma 3.10 it suffices to show that (3) implies (1) and that (4) implies (3). First assume (3) holds and \(\textbf{S} \times \textbf{T}\) is finitely related. Since \(\textbf{T}\) is finite, it contains an idempotent element e. Thus \(\textbf{S} \cong \textbf{S} \times \{e\}\) embeds into \(\textbf{S} \times \textbf{T}\). So \(\textbf{S}\) is finitely related.
Now assume (4) holds. Let \(\textbf{T}\) be a subsemigroup of a finitely related semigroup \(\textbf{S}\). Since \(\textbf{S}\) and \(\textbf{S} \times \textbf{T}\) generate the same variety, \(\textbf{S} \times \textbf{T}\) is also finitely related by Theorem 3.9. By Lemma 3.13\(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\) is finitely related. Now \(\textbf{S}^0\) is an ideal of \(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\). The corresponding Rees quotient is isomorphic to \(\textbf{T}^0\) and finitely related by (4). By Theorem 3.11\(\textbf{T}\) is finitely related. \(\square \)
Lemma 3.14
Let \(\textbf{S}:= ({{\,\mathrm{\textbf{FN}}\,}}_5 \{a,b\} \mathbin {/}\theta )^1\) be as in Theorem 2.5 and \(\textbf{T} \cong ({{\,\mathrm{\textbf{FN}}\,}}_5 \{a, b\})^{1}\) with S and T disjoint. Then
-
(1)
\(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\) is finitely related.
-
(2)
\(\textbf{S}\) is a subsemigroup and a Rees quotient of \(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\) but not finitely related.
Proof
By Lemma 3.12\(\textbf{T}\) and \(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\) generate the same variety. Thus \(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\) is finitely related by Theorem 2.4 and Theorem 3.9. Since \(\textbf{T}\) forms an ideal in \(\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}\) we have \(\textbf{S} \cong (\textbf{S} \mathbin {\mathring{\cup }}\textbf{T}) \mathbin {/} \textbf{T}\). By Theorem 2.5\(\textbf{S}\) is not finitely related. \(\square \)
Data availability
Data sharing not applicable to this article as datasets were neither generated nor analysed.
References
Aichinger, E.: Constantive Mal’cev clones on finite sets are finitely related. Proc. Am. Math. Soc. 138(10), 3501–3507 (2010)
Aichinger, E., Mayr, P., McKenzie, R.: On the number of finite algebraic structures. J. Eur. Math. Soc. (JEMS) 16(8), 1673–1686 (2014)
Barto, L.: Finitely related algebras in congruence distributive varieties have near unanimity terms. Canad. J. Math. 65(1), 3–21 (2013)
Barto, L.: Finitely related algebras in congruence modular varieties have few subpowers. J. Eur. Math. Soc. (JEMS) 20(6), 1439–1471 (2018)
Barto, L., Bulín, J.: Deciding absorption in relational structures. Algebra Univers. 78(1), 3–18 (2017)
Bulatov, A.A., Valeriote, M.A.: Recent results on the algebraic approach to the CSP. In: Complexity of Constraints: An Overview of Current Research Themes, pp. 68–92. Springer, Berlin (2008)
Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78. Springer, New York (1981)
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–110 (2011)
Dolinka, I.: Finite bands are finitely related. Semigroup Forum 97(1), 115–130 (2018)
Goldstein, M.: Finitely related algebras. Master’s thesis, Charles University in Prague, Czech Republic (2017)
Jablonskiĭ, S.V.: The structure of the upper neighborhood for predicate-describable classes in \(P_{k}\). Dokl. Akad. Nauk SSSR 218, 304–307 (1974)
Marković, P., Maróti, M., McKenzie, R.: Finitely related clones and algebras with cube terms. Order 29(2), 345–359 (2012)
Mayr, P.: On finitely related semigroups. Semigroup Forum 86(3), 613–633 (2013)
Moore, M.: Finite degree clones are undecidable. Theoret. Comput. Sci. 796, 237–271 (2019)
Rosenberg, I.G., Szendrei, A.: Degrees of clones and relations. Houst. J. Math. 9(4), 545–580 (1983)
Sparks, A.: On the number of clonoids. Algebra Univers. 80(4), Paper No. 53, 10 (2019)
Szendrei, Á.: Clones in universal algebra. Les presses de L’universite de Montreal (1986)
Szpilrajn, E.: Sur l’extension de l’ordre partiel. Fund. Math. 1(16), 386–389 (1930)
Willard, R.: Essential arities of term operations in finite algebras. Discrete Math. 149(1–3), 239–259 (1996)
Funding
Open access funding provided by Johannes Kepler University Linz.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The author declares that he has no conflict of interest.
Additional information
Presented by B. A. Davey.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supported by the University of Colorado Boulder and the Austrian Science Fund (FWF) under Grant No. P27600.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Steindl, M. Not all nilpotent monoids are finitely related. Algebra Univers. 85, 13 (2024). https://doi.org/10.1007/s00012-023-00841-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00012-023-00841-5