Finite subsemigroups of free left regular bands
Artem N. Shevlyakov

arXiv:1406.3429v6 [math.AG] 29 Feb 2016

December 26, 2017
Abstract
We describe all finite subsemigroups of free left regular bands. Moreover, we
show applications of this result in algebraic geometry and model theory.

1

Introduction

A semigroup is a left regular band if it satisfies the identities x2 = x, xyx = xy.
Left regular bands have important applications in hyperplane arrangements, random
walks and matroid theory, see e.g. [1, 2, 3, 4, 5, 6, 7, 8]. In the current paper we
describe all finite subsemigroups of free left regular bands (Theorems 6.1 and 6.2).
Actually, our proof is not short and easy. For example, we had to introduce
about six partial orders over left regular bands (remark that all our orders are not
compatible with the multiplication over left regular bands).
Let us give the plan of our paper. The first tree sections contain all necessary
definitions and simple statements devoted to left regular bands and semilattices.
In particular, we give here the important definitions of local linear order and right
hereditary property. In Section 5 we prove (Theorem 5.4) that any finite subband
of a free left regular band has a local linear order. Thus, the local linear order is
the necessary condition of the embeddability into free left regular bands.
In Section 6 we prove that any right hereditary left regular band S with a local
linear order is embeddable into a free left regular band of an appropriate rank.
Firstly, we define a map h : S → F, where F is a free left regular band of infinite
rank, and prove (Lemma 6.9) that h is a homomorphism. However, h may be not
injective. Therefore, in Subsection 6.2 we define a procedure which takes h and
obtains an embedding h′ after a finite number of iterations. Thus, the embedding
h′ proves the main result of our paper (Theorem 6.1).
In the last section of our paper we talk about open problems and possible applications of Theorem 6.1. Moreover, we discuss how to simplify the proof of Theorem 6.1
and why we do not do it.

2

Semilattices

Below we shall consider join semilattices, and denote multiplication by ∪. Elements
of semilattices are denoted below by bold letters x, y, z, . . .
One can define a partial order over any join semilattice by
x ⊆ y ⇔ y ∪ x = y.

(1)

Let M be a set, and FM be the family of all finite subsets (including ∅) of M .
Let us define over FM a multiplication as a set union. Obviously, FM is isomorphic

1

to the join free semilattice of rank |M | with the adjoined identity. We denote the
free basis of FM by {am |m ∈ M }. Sometimes elements of FM (free generators am )
will be called words (respectively, letters). By am ∈ c we shall denote that a letter
am belongs to a word c ∈ FM .
For any b, c ∈ FM one can define c\b ∈ FM as the set difference. The length |a|
of a ∈ FM is the length of a word representing a. Let F denote the free semilattice
generated by an infinite set of generators {ai |i ∈ I}.
Take a finite join semilattice L. According to semilattice theory, L is embeddable
into a free semilattice of an appropriate rank. The following embedding will play a
crucial role in our study.
Let us define a map ν : L → FL by
[
ν(x) =
at .
x*t

Lemma 2.1. ν is an embedding of L into FL .
Proof. First, we prove that ν is a homomorphism of L. Let us take x, y and z = x∪y.
We have
[
[
ν(x) =
at , ν(y) =
ar ,
x*t

y*r

ν(z) =

[

ap .

z*p

It is sufficient to prove
{t|x * t} ∪ {r|y * r} = {p|z * p}.
The relation x * t (y * r) implies z * t (respectively, z * r). Hence,
{t|x * t} ∪ {r|y * r} ⊆ {p|z * p}.
Let z * p. If x ⊆ p and y ⊆ p then z = x ∪ y ⊆ p, a contradiction. Therefore,
either x * p or y * p. Thus, we obtained
{t|x * t} ∪ {r|y * r} ⊇ {p|z * p}.
Second, we prove that ν is an embedding.
Suppose that Fx = Fy for some distinct x, y, where
Fx = {t|x * t}, Fy = {r|y * r}.
Since x ∈
/ Fx , y ∈
/ Fy , we have x ∈
/ Fy , y ∈
/ Fx . It follows that x ⊆ y and y ⊆ x,
hence x = y.
By the definition of ν, we have the next statement.
Lemma 2.2. If ν(x) does not contain a letter ay , then x ⊆ y in L.
Lemma 2.3. Let x, x′ , y, y′ ∈ L, x ⊂ x′ , y ⊂ y′ and
d(x′ ) = ν(x′ ) \ ν(x) ⊆ ν(y′ ) \ ν(y) = d(y′ ).
Then y ⊆ x.
Moreover, the equality d(x′ ) = d(y′ ) implies x = y and x′ = y′ .

2

Proof. By the definition of ν, ν(x) does not contain ax . However x ⊂ x′ implies
ax ∈ ν(x′ ). Hence,
ax ∈ d(x′ ) ⇒ ax ∈ d(y′ ) ⇒ ax ∈
/ ν(y).
By Lemma 2.2, the last expression gives y ⊆ x.
Suppose d(x′ ) = d(y′ ). By above, it follows x = y and therefore x′ = y′ .

3

Left regular bands

A semigroup S is a left regular band if the next identities
x2 = x, xyx = xy
hold in S.
Remark that we always consider left regular bands with the identity ε adjoined.
By F we denote the free left regular of infinite rank. The elements of F are all
words w in an infinite alphabet {ai |i ∈ I} such that any letter ai occurs at most
one time in w. The product of two elements w1 , w2 ∈ F is defined as follows:
w1 w2 = w1 ◦ (w2 )∃ ,
where ◦ is the word concatenation and the operator ∃ is the deletion of all letters
which occur earlier. For example, (a1 a2 a3 )(a2 a3 a4 ) = a1 a2 a3 a4 .
Below elements of F (free generators ai ) are called words (respectively, letters),
and we shall use the denotation ai ∈ w if a letter ai belongs to a word w ∈ F.
Remark that in our denotations free generators of the semilattice F and the left
regular band F are indexed by the common set I.
For elements x, y of a left regular band S one can define a relation
x ≤ y ⇔ xy = y.
It is easy to check that ≤ is a partial order over S. Remark that in some papers
(e.g. see [4]) ≤ defines the contrary relation: yx = x.
For elements x, y ∈ F the relation x ≤ y means that the word x is a prefix of y.
The next lemma contains simple statements about the structure of free left
regular bands F.
Lemma 3.1.
1. The Hasse diagram of the order ≤ is a tree for F. The root of this tree is
the identity ε. For example, the Hasse diagram for the free left regular band
generated by three elements a1 , a2 , a2 is

a1 a2 a3 a1 a3 a2
a2 a1 a3 a2 a3 a1
a1 a2

❆
❆

✁
✁

a1 a3

a2 a1

❆
❆

✁
✁

a3 a1 a2 a3 a2 a1

a2 a3

❆

a3 a1

✁

❆
✁
❆ ✁
❆ ✁
❆ ✁
❆✁a1
❅
❆✁a2
❆✁a3
✏✏
✁
✏
❅
✏✏
✁
❅
✏✏
✏
❅ ✁ ✏✏
ε❅✁✏✏

Fig. 1

3

a3 a2

2. Let x1 , x2 , y1 , y2 ∈ F, xi ≤ yi and x1 , x2 are not ≤-comparable. Then y1 , y2
are not ≤-comparable.
Define the another relation on elements of a left regular band S by
x  y ⇔ yx = y.
This relation is reflexive and transitive, but not necessarily antisymmetric.
For a free left regular band F the relation x  y means that the word y contains
all letters of a word x. For example, a1 a2  a2 a1 , a2  a1 a2 a3 . Obviously, the
relation x ≤ y implies x  y in any left regular band.
We shall write x ≈ y iff x  y and y  x. One can get a join semilattice L by
identifying x and y if x ≈ y. Let σ : S → L denote the quotient map. L is called
the support semilattice of S and for all x, y ∈ S we have
σ(xy) = σ(x) ∪ σ(y).
It is easy to see that for any s ∈ F the map σ(s) gets the set of all letters
occurring in s. Thus, we obtain
σ(F) = F,
where σ(ai ) = ai (i ∈ I).
F
Let
S∞us define a linear order < over the semilattice F as follows. We have
F = n=0 Ln , where Ln = {a ∈ F | |σ(a)| = n} and each set Ln has a linear order
<Ln . Thus, we put
a <F b ⇔ |σ(a)| < |σ(b)| or a <Ln b for a, b ∈ Ln .
Notice that x ≺ y implies x <F y for all x, y ∈ F.
→
−
Let us define a map () : F → F as follows. Let {ai1 , ai2 , . . . , ain } be the set
of all letters of a word a ∈ F. The letters of a correspond to free generators
{ai1 , ai2 , . . . , ain } ⊆ F and the order <F is given by
ai1 <F ai2 <F . . . <F ain .
−→
Then the word (a) ∈ F is the product
ai1 ai2 . . . ain .
−→
Roughly speaking, (a) replaces the letters of a to the corresponding generators
of F and sorts them in the given order <F .
Following [4], a left regular band S is called right hereditary if the Hasse diagram
of ≤ is a tree with the root element ε. By Lemma 3.1, any free left regular band is
right hereditary.
Let x, y, z be elements of a left regular band S, and the equivalence relation ∼z
be as follows:
x ∼z y ⇔ xz = yz.
Clearly, the relation x ≤ y is equivalent to x ∼y y.
Lemma 3.2. Let S, T be left regular bands. Suppose a map h : S → T preserves
the relations , ∼c for each c ∈ S, i.e. for any a, b, c ∈ S we have:
a  b ⇒ h(a)  h(b),
a ∼c b ⇒ h(a) ∼h(c) h(b).
Then h is a homomorphism.

4

Proof. Let us prove h(xy) = h(x)h(y) for all x, y ∈ S. Denote z = xy, hence
zy = xy and z ∼y x. By the condition, h(z)h(y) = h(x)h(y). Since y  z, we have
h(y)  h(z) and obtain h(z) = h(x)h(y).
Example 3.3. Let us define a right hereditary band B = {x1 , x2 , x3 , y0 , y1 , y2 }
defined by the following multiplication table (the identity ε is omitted):
x1 x2 x3 y 0 y 1 y 2
x1 x1 y 0 y 1 y 0 y 1 y 1
x2 x2 x2 y 2 x2 y 2 y 2
x3 x3 x3 x3 x3 x3 x3
y0 y0 y0 y1 y0 y1 y1
y1 y1 y1 y1 y1 y1 y1
y2 y2 y2 y2 y2 y2 y2
The order ≤ over B is defined by the following Hasse diagram:
y2

y1
y0

x

2
✑
✁
✑
✁ ✑
❅
❅ ✁✑✑
ε❅✁✑

x1

x3

Fig. 2
The support semilattice of B is a linear ordered semilattice 1 < 2 < 3 < 4, where
σ(ε) = 1, σ(x1 ) = 2, σ(x2 ) = σ(y0 ) = 3, σ(x3 ) = σ(y1 ) = σ(y2 ) = 4.
The embedding ν gives:
ν(σ(x1 )) = a1 , ν(σ(x2 )) = ν(σ(y0 )) = a1 a2 , ν(σ(x3 )) = ν(σ(y1 )) = ν(σ(y2 )) = a1 a2 a3 .
Thus, ν embeds σ(B) into F.
The multiplication over B generates the following equivalence classes:
x
Equivalence classes of ∼x
x1 {ε, x1 }, {x2 }, {y2 }, {y0 }, {y1 }, {x3 }
x2
{ε, x2 }, {x1 , y0 }, {x3 }, {y1 }, {y2 }
x3
{ε, x3 }, {x2 , y2 }, {x1 , y0 , y1 }
y0
{ε, x1 , y0 }, {x2 }, {x3 }, {y2 }, {y1 }
y1
{ε, x1 , y0 , y1 }, {x2 , y2 }, {x3 }
y2
{ε, x2 , y2 }, {x3 }, {x1 , y0 , y1 }


4

Properties of right hereditary bands

Below S is a right hereditary band and L = σ(S). The following lemma describes
the main property of left regular bands.
Lemma 4.1. The equality x1 x2 = x3 x4 (xi ∈ S) implies x1 ≤ x3 or x3 ≤ x1 .
Proof. Let x = x1 x2 = x3 x4 and we have x1 ≤ x, x3 ≤ x. Since the Hasse diagram
of the order ≤ is a tree, the elements x1 , x3 should be ≤-comparable.

5

Lemma 4.2. Let S be a right hereditary band and x, y, z ∈ S. Then x ≤ y ≤ xz
or y ≤ x ≤ yz iff x ∼z y.
Proof. Let us prove the “only if” part of the lemma. Let x ≤ y ≤ xz. By the
definition of the order ≤ we have:
xy = y, yxz = xz.
Therefore,
(xy)xz = xz ⇔ (xy)z = xz ⇔ yz = xz ⇔ x ∼z y.
Let us prove the “if” part of the lemma. Since S is right hereditary, the relation
xz = yz implies either x ≤ y or y ≤ x. So
x ≤ y ≤ yz = xz or y ≤ x ≤ xz = yz.

Since the Hasse diagram of the order ≤ is a tree with the root ε, it allows us to
define the ancestor α(s) ∈ S for any s 6= ε as follows:
α(s) = max{x ∈ S|x < s}.
An element s′ with α(s′ ) = s is called a descendant of s.
For any c 6= ε let us define a set Sc ⊆ S by
Sc = {s ∈ S \ {ε}|s ∼c α(s), s ≁c′ α(s) for any c′ < c}

(2)

Notice that Sc 6= ∅, since c ∈ Sc .
Example 4.3. For the left regular band B we have: Sx1 = {x1 }, Sx2 = {x2 , y0 },
Sx3 = {x3 , y0 , y1 , y2 }, Sy0 = {y0 }, Sy1 = {y1 , y2 }, Sy2 = {y1 , y2 }. 
Lemma 4.4. For any x ∈ Sb , a < b we have a  α(x).
Proof. By the condition, a ≤ α(b) < b.
By Lemma 4.2 we have
α(x) ≤ x ≤ α(x)b.
Also we have
α(x) ≤ α(x)a ≤ α(x)ab = α(x)b.
Since the Hasse diagram of ≤ is a tree, the first chain above should contain
α(x)a.
If α(x) ≤ x ≤ α(x)a Lemma 4.2 gives α(x) ∼a x that contradicts the definition
of the set Sb . Thus,
α(x) ≤ α(x)a < x.
By the definition of the ancestor, it holds α(x) = α(x)a, hence a  α(x).

Lemma 4.5.
comparable.

For all x, y ∈ Sc the elements α(x)α(y)x, α(x)α(y)y are ≤-

6

Proof. By the definition of Sc , we have α(x)c = xc, α(y)c = yc. Let us multiply
both equalities by α(x)α(y) and obtain
α(x)α(y)c = α(x)α(y)xc, α(x)α(y)c = α(x)α(y)yc.
Therefore,
α(x)α(y)xc = α(x)α(y)yc.
Since S is right hereditary, the prefixes α(x)α(y)x, α(x)α(y)y are ≤-comparable.
Let s ∈ S \ {ε} and denote
δν (s) = ν(σ(s)) \ ν(σ(α(s))) ∈ FL .

(3)

A band S has a local linear order if for each b the set Sb admits a linear order
⊏b such that for all x, y ∈ Sb it holds:
1.
δν (x) ⊂ δν (y) ⇒ x ⊏b y;

(4)

σ(x) ⊆ σ(α(y)) ⇒ x ⊏b y.

(5)

2.
3. for arbitrary Sc ⊇ Sb we have:
x ⊏b y ⇒ x ⊏c y.

(6)

Finite subbands of F

5

Below in this section we assume S ⊆ F, |S| < ∞, L = σ(S) ⊆ F and ν embeds L
into FL . Let {w} denote the set of all letters of a word w ∈ F. By the properties of
F, for each x ∈ S \ {ε} ⊆ F there exists a unique ∆(x) ∈ F such that x = α(x)∆(x)
and {α(x)} ∩ {∆(x)} = ∅.
Lemma 5.1. The following correspondences between δν and ∆ hold:
1.
δν (x) ⊆ δν (y) ⇒ ∆(x)  ∆(y)

(7)

δν (x) ⊂ δν (y) and ∆(x) ≈ ∆(y) ⇒ y ≺ x.

(8)

2.
Proof.

1. By Lemma 2.3, we have α(y)  α(x). Let
s1 = α(x)α(y)x = α(x)x = α(x)∆(x),
s2 = α(x)α(y)y = α(x)y = α(x)α(y)∆(y) = α(x)∆(y).

The images of the support mapping are:
ν(σ(s1 )) = ν(σ(α(x))) ∪ ν(σ(α(y)) ∪ ν(σ(x)) = ν(σ(α(x))) ∪ ν(σ(α(y)) ∪ δν (x)
ν(σ(s2 )) = ν(σ(α(x))) ∪ ν(σ(α(y)) ∪ ν(σ(y)) = ν(σ(α(x))) ∪ ν(σ(α(y)) ∪ δν (y)
Since δν (x) ⊆ δν (y), we have ν(σ(s1 )) ⊆ ν(σ(s2 )), and therefore s1  s2 . By
Lemma 4.5 s1 , s2 are ≤-comparable, hence s1 ≤ s2 and
α(x)∆(x) ≤ α(x)∆(y).
Let a be a letter form ∆(x). Since a ∈
/ α(x), we have a ∈ ∆(y). Thus,
∆(x)  ∆(y).

7

2. According to Lemma 2.3, we have
α(y)  α(x).

(9)

By ∆(x) ≈ ∆(y) we obtain y = α(y)∆(y)  α(x)∆(x) = x. Thus, y  x.
Assume
x ≈ y,
(10)
then
yx = y ⇒ α(y)∆(y)α(x)∆(x) = α(y)∆(y) ⇒
α(y)∆(y)α(x) = α(y)∆(y) ⇒ α(x)  α(y)∆(y).
By ∆(x) ≈ ∆(y), the words α(x) and ∆(y) have no common letters, therefore,
α(x)  α(y).
By (9), it follows α(x) ≈ α(y). Using (10), we obtain δν (x) = δν (y) that
contradicts the condition.
Let us define relations ⊏= , ⊏6=
b over a set Sb as follows:
x ⊏= y ⇔ ∆(x) ≈ ∆(y), and y <F x,
where the linear order <F over F was defined above.
Define x ⊏6=
b y iff b contains a letter a ∈ {∆(y)} \ {∆(x)} and there is not any
letter a′ ∈ {∆(x)} \ {∆(y)} occurring after a in the word b. The letter a with such
property is called the (x, y)-separator if b does not contain any letter with the same
property after a.
Example 5.2.
If ∆(x) = a1 a2 a3 a5 , ∆(y) = a2 a4 a5 for some x, y ∈ Sb , b =
a1 a2 a3 a4 a5 then x ⊏6=
b y and a4 is the (x, y)-separator. 
Obviously, ⊏6=
b is defined for all x, y ∈ Sb with distinct sets {∆(x)}, {∆(y)}.
The relation x ⊏b y holds iff
1. x ⊏6=
b y or
2. x ⊏= y for undefined x ⊏6=
b y.
Clearly, ⊏b is defined for any pair (x, y) ∈ Sb2 .
Lemma 5.3. If x ∈ Sb then ∆(x)  ∆(b).
Proof. We have α(x)b = xb and Lemma 4.4 gives α(b)  α(x). Therefore,
α(x)b = xb ⇔ α(x)∆(b) = α(x)∆(x)∆(b).
Let a be a letter from the word ∆(x). Hence, a should occur in the left part of the
last equality. Since α(x), ∆(x) have no common letters, we obtain a ∈ ∆(b). Thus,
∆(x)  ∆(b).
Theorem 5.4. Any finite subband S ⊆ F has a local linear order.
Proof. By the definition of the local linear order, one should prove the following.
Let us prove that ⊏b satisfies all conditions of a local linear order.

8

1. ⊏b is a linear order. By the definition, ⊏b is irreflexive and asymmetric and
it is defined for any pair (x, y) ∈ Sb2 . Let us prove the transitivity and take
x ⊏b y, y ⊏b z. We have the following cases.
6=
6=
(a) x ⊏6=
b y, y ⊏b z. Let us prove x ⊏b z.
It follows there exist the (x, y)-separator a and the (y, z)-separator a′ .
By the definition of a separator, we have a ∈ {∆(y)} \ {∆(x)}, a′ ∈
{∆(z)} \ {∆(y)}.
Suppose a is before a′ in the word b (or a = a′ ). It follows that a′ ∈
/ ∆(x).
′
′′
Let us prove that a is the (x, z)-separator. Take an arbitrary a ∈ {∆(x)}
6=
′′
′′
after a′ in the word b. By x ⊏6=
b y, a ∈ {∆(y)}. Since y ⊏b z, a should
belong to {∆(z)}. Thus, a′ is the (x, z)-separator and x ⊏6=
b z.
6=
′
Suppose a is after a in the word b. Since y ⊏b z, then a ∈ {∆(z)}. Let
us prove that a is the (x, z)-separator. Take an arbitrary a′′ ∈ {∆(x)}
6=
′′
after a in the word b. By x ⊏6=
b y, we have a ∈ ∆(y). Since y ⊏b z
′′
′′
and a occurs in b after a, a should belong to {∆(z)}. Thus, a is the
(x, z)-separator, and therefore x ⊏6=
b z.
=
=
(b) x ⊏ y, y ⊏ z. It easily follows ∆(x) ≈ ∆(z), z <F y <F x. Thus,
x ⊏= z.
=
(c) x ⊏6=
b y, y ⊏ z. We have ∆(y) ≈ ∆(z). Let a be the (x, y)-separator.
Hence, there is not any a′ ∈ {∆(x)} \ {∆(y)} = {∆(x)} \ {∆(z)} after a
in the word b. Thus, a is the (x, z)-separator, and x ⊏6=
b z.

(d) x ⊏= y, y ⊏6=
b z. This case is similar to the previous one.
2. Prove (4). Take x, y with δν (x) ⊂ δν (y). By (7), we have ∆(x)  ∆(y).
Assume ∆(x) ≺ ∆(y). By Lemma 5.3, all letters of ∆(y) belong to the word b.
Thus, the last letter a ∈ {∆(y)} \ {∆(x)} in the word b is the (x, y)-separator,
and x ⊏6=
b y.
If ∆(x) ≈ ∆(y) then (8) gives
y ≺ x ⇒ y <F x ⇒ x ⊏= y.
3. Prove (5). By Lemma 5.3, all letters of ∆(x), ∆(y) belong to the word b. Since
x  α(y), the sets of letters {x}, {∆(y)} do not intersect. Let a (a′ ) be the last
letter from {∆(x)} (respectively, {∆(y)}) in the word b. If a is before a′ in b
we immediately obtain x ⊏b y. Let us assume the converse: ∆(b) = d1 a′ d2 ad3
for some di ∈ F. Using Lemma 4.4, we have α(b)  α(x) and
α(x)b = xb ⇒ α(x)∆(b) = x∆(b) ⇒ α(x)d1 a′ d2 ad3 = xd1 a′ d2 ad3 .
The word α(x)d1 a′ does not contain a, and x does not contain a′ . Therefore,
the words α(x)d1 a′ , x are not ≤-comparable, and the last equality does not
hold.
4. Prove (6). Suppose x ⊏= y. Since the relation ⊏= does not depend on b, we
immediately obtain x ⊏c y. Let us put x ⊏6=
b y, and a is the (x, y)-separator.
By Lemma 4.4, α(b)  α(x), α(b)  α(y), and α(c)  α(b) (since b ∈ Sb ⊆ Sc ).
Hence, {∆(x)} ∩ {α(b)} = {∆(y)} ∩ {α(b)} = ∅ and a ∈
/ {α(b)}. The equality
α(b)c = bc gives
α(b)∆(c) = α(b)∆(b)∆(c).
By Lemma 5.3, ∆(y)  ∆(y) and therefore a ∈ ∆(b). Therefore, the left part
of the last equality should contain a, hence, a ∈ {∆(c)}. The relation x ⊏6=
c y
fails if there exists a letter a′ ∈ {∆(x)} \ {∆(y)} and a′ occurs after a in ∆(c).

9

′
By Lemma 5.3, a′ ∈ {∆(x)} ⊆ {∆(b)}. Since x ⊏6=
b y, a occurs before a in
the word b.
Thus, ∆(c) = c1 ac2 a′ c3 and ∆(b) = b1 a′ b2 ab3 for some ci , bi ∈ F and we have

α(b) ∼c b ⇔ α(b)c1 ac2 a′ c3 = α(b)b1 a′ b2 ab3 c1 c2 c3 .
The prefixes s1 = α(b)c1 a, s2 = α(b)b1 a′ are not ≤-comparable (s1 does not
contain a′ , s2 does not contain a), a contradiction.
Thus, we proved x ⊏c y.

6

Main result

Recall that F = {ai |i ∈ I} is the free left regular band of infinite rank with the
identity adjoined. The aim of this paper is to prove the next theorem.
Theorem 6.1.
equivalent:

For any finite left regular band S the following conditions are

1. S is embeddable into F;
2. S is right hereditary and has a local linear order.
Obviously, Theorem 6.1 immediately gives the following result for free left regular
bands of finite ranks.
Theorem 6.2.
equivalent:

For any finite left regular band S the following conditions are

1. S is embeddable into a free left regular band Fn of an appropriate rank n;
2. S is right hereditary and has a local linear order.
Let us come back to the proof of Theorem 6.1. The implication (1) ⇒ (2) follows
from Theorem 5.4. The implication (2) ⇒ (1) is quite complicated, so its proof is
divided into two parts. Below S is a finite right hereditary band with a local linear
order.

6.1

Orderings and homomorphisms

Let L = σ(S). One can initially assume that L is a subsemilattice of F. Thus,
below we consider elements of L as words of F. Let s ∈ S \ {ε} and
δ(s) = σ(s) \ σ(α(s)) ∈ F
(obviously, δ(s) coincides with δν (s) defined in (3) if we embed L into F via the
embedding ν).
For any c ∈ S we define a vector
χ(c) = (χ(α(c)), y1 , y2 , . . . , ync )
such that
1. χ(c) is a recursive structure, since it contains a subvector χ(α(c));
2. Sc = {y1 , y2 , . . . , ync };
3. yi ⊏c yi+1 ;

10

(11)

4. χ(ε) is the empty vector.
Example 6.3.
Let us show that the left regular band B from the previous
examples has a local linear order and compute the vectors χ(c) for each c ∈ Sc .
For elements of B we have δ(x1 ) = a1 , δ(x2 ) = a1 a2 , δ(x3 ) = a1 a2 a3 , δ(y0 ) = a2 ,
δ(y1 ) = a3 , δ(y2 ) = a3 (since ν embeds σ(B) into F we have δ(s) = δν (s) for each
s ∈ B).
One of the possible definitions of ⊏b is in the following table (if a set Sb consists
of a unique element the definition of ⊏b is omitted). Using the definition of ⊏b , one
can define vectors χ(b).
x
⊏x over Sx
χ(x)
x1
—
(x1 )
x2
y 0 ⊏ x2
(y0 , x2 )
x3 y0 ⊏ y1 ⊏ y2 ⊏ x3 (y0 , y1 , y2 , x3 )
y0
—
(χ(x1 ), y0 )
y1
y1 ⊏ y2
(χ(y0 ), y1 , y2 )
y2
y1 ⊏ y2
(χ(x2 ), y1 , y2 )

One can recursively apply (11) to α(c) and obtain a new vector
χ(c) = (χ(α(α(c))), x1 , x2 , . . . , xnα(c) , y1 , y2 , . . . , ync ).
It allows us to descend to any element a ≤ c obtaining the vector:
χ(c) = (χ(a), . . . , y1 , y2 , . . . , ync ).

(12)

We shall say y ∈ χ(c) if y ∈ Sc or y ∈ χ(α(c)).
Lemma 6.4. Let χ(c) be the vector (11). Then any element y with y ∼c α(y)
belongs to χ(c).
Proof. Let c′ ≤ c be the maximal element such that α(y) ≁α(c′ ) y and α(y) ∼c′ y
(such element always exists in the set {s ∈ S|ε < s ≤ c}). Therefore, y ∈ Sc′ and
y ∈ χ(c′ ) ⊆ χ(c).
Now we are able to define a map h : S → F of a right hereditary band S.
(
ε, if c = ε,
h(c) =
,
(13)
h(α(c))c1 c2 . . . cn , otherwise
−−→
−
→
where χ(c) = (χ(α(c)), y1 , y2 , . . . , yn ) and ci = δ(yi ) (the operator () was defined in
Section 3).
Example 6.5. Let us compute the images of h for elements of the left regular
band B defined in examples above. Let us fix an order over the free generators
a1 <F a2 <F a3 and obtain
−−→
δ(x)
x
h(x)
x1
a1
a1
x2
a1 a2
(a2 ) · (a1 a2 ) = a2 a1
x3 a1 a2 a3 (a2 ) · (a3 ) · (a3 )(a1 a2 a3 ) = a2 a3 a1
y0
a2
h(x1 ) · (a2 ) = a1 a2
y1
a3
h(y0 ) · (a3 ) · (a3 ) = a1 a2 a3
y2
a3
h(x2 ) · (a3 ) · (a3 ) = a2 a1 a3

11

One can directly check that h embeds B into F. 
Since h(c) is recursively defined by the image h(α(c)) and h(α(c)) ≤ h(c), we
obtain the next simple statement.
Lemma 6.6. The map h preserves the order ≤: if a ≤ b then h(a) ≤ h(b).
Lemma 6.7. For any c ∈ S it holds σ(h(c)) = σ(c) (recall that both elements
σ(s), σ(h(s)) belong to F).
Proof. If c = ε the equality obviously holds. Assume the equality holds for the
ancestor α(c):
σ(h(α(c))) = σ(α(c))
Let χ(c) be the vector (11), and the image h(c) is defined by (13). Since c ∈ Sc ,
there exists an index i such that yi = c, hence
σ(h(c)) ⊇ σ(h(α(c))) ∪ δ(c) = σ(α(c)) ∪ δ(c) = σ(c).
Let us prove the contrary inclusion. By the choice of the elements yi , we have
yi c = α(yi )c, hence σ(yi ) ∪ σ(c) = σ(α(yi )) ∪ σ(c) and it follows
δ(yi ) ⊆ σ(c).
Thus,
σ(h(c)) = σ(h(α(c)))

[

δ(yi ) ⊆ σ(α(c)) ∪ σ(c) = σ(c).

i

We need the next auxiliary lemma.
Lemma 6.8.
chain

Let y, z, c ∈ S \ {ε}, z ∼c α(z), s = α(z)yz, s 6= α(z)y and in the
s = s0 > s1 > . . . > sk−1 > sk = α(z)y

each si is the ancestor of si−1 (1 ≤ i ≤ k). Then
1. si ∼c si−1 ;
2. σ(s) \ σ(α(z)y) ⊆ δ(z);
3. δ(si ) ⊆ σ(s) \ σ(α(z)y);
4. δ(si ) ⊆ δ(z);
5.

k
[

δ(si ) = σ(s) \ σ(α(z)α(b));

(14)

i=0

6. the equality δ(si ) = δ(z) implies k = 1;
7. suppose z ∈ Sc′ (it follows c′ ≤ c). Then si ∈ Sci for some ci ≤ c′ ;
8. if δν (si ) ⊂ δν (z) then si occurs before z in the vector χ(c).
Proof.

1. We have the chain
α(z)y = sk < sk−1 < . . . < s0 = α(z)yz ≤ α(z)yzc = α(z)yα(z)c = α(z)yc.

By Lemma 4.2, si ∼c α(z)y and therefore si ∼c si−1 .

12

2. Suppose a letter a belongs to σ(α(z)yz) \ σ(α(z)y) ∈ F. Then a ∈ σ(z) but
a∈
/ σ(α(z)). Thus, a ∈ δ(z).
3. Consider a letter a ∈ δ(si ). Hence, a ∈ σ(si ) ⊆ σ(s), a ∈
/ σ(si+1 ). Since
si+1 ≥ α(z)y, we have a ∈
/ σ(α(z)y). Thus, a ∈ σ(s) \ σ(α(z)y).
4. The statement immediately follows from the previous ones.
5. We have σ(si−1 ) = δ(si−1 ) ⊔ σ(si ) (x ⊔ y is the join of words x, y ∈ F which
do not have common letters). Thus,
σ(s0 ) = δ(s0 ) ⊔ σ(s1 ) = δ(s0 ) ⊔ δ(s1 ) ⊔ σ(s2 ) = . . . =

k
[

δ(si ) ⊔ σ(α(z)y)

i=0

and we obtain (14).
6. Immediately follows from (14) and previous statements of the lemma.
7. We have z ∼c′ α(z). One can repeat the proof of the first statement of the
lemma for c′ instead of c and obtain si ∼c′ si−1 . Therefore, si ∈ Sci for some
ci ≤ c′ ≤ c
8. By the previous statement of the lemma, each si belongs to Sci for some ci ≤ c′ .
Therefore, the element si (z) belongs to the vector χ(ci ) (respectively, χ(c′ )).
If ci < c′ , then the contents of χ(ci ) occur before the contents of χ(c′ ) in the
vector χ(c), and therefore si occur before z in the vector χ(c). If ci = c′ then,
according to (4), the condition δν (si ) ⊂ δν (z) implies si ⊏c′ z. Therefore, si
occurs before z in the vector χ(c′ ). Since the vector χ(c′ ) is included in χ(c),
si occurs before z in χ(c).
Recall that Lemma 6.8 holds for any embedding of σ(S) into F. If we replace all
occurrences of δ to δν we obtain true statements about the embedding ν.
Lemma 6.9.
S.

The map h : S → F is a homomorphism of a right hereditary band

Proof. Using Lemmas 3.2, 6.7, it is sufficient to prove the implication
a ∼c b ⇒ h(a) ∼h(c) h(b).

(15)

α(b) ∼c b ⇒ h(α(b)) ∼h(c) h(b).

(16)

First, we prove
By the definition of h, one can write
h(b) = h(α(b))b1 b2 . . . bn ,
h(c) = c1 c2 . . . cm
(in the last expression we iterate the definition of h(c) to the identity ε), and there
exist vectors
χ(b) = (χ(α(b)), y1 , y2 , . . . , yn ),
χ(c) = (z1 , z2 , . . . , zm ),
−−→
−−−→
such that bi = δ(yi ), cj = δ(zj ).
Lemma 6.4 states zj ∼c α(zj ) (1 ≤ j ≤ m), yi ∼b α(yi ) (1 ≤ i ≤ n). Using
Lemmas 4.2, 4.4, we have the following chain
α(yi ) ≤ yi ≤ α(yi )b ≤ α(yi )bc = (α(yi )α(b))c = α(yi )c.

13

By Lemma 4.2, it follows α(yi ) ∼c yi . Thus, the vector χ(c) contains all yi . In
other words, there exists a function f : {1, 2, . . . , n} → {1, 2, . . . , m} which embeds
{y1 , y2 , . . . , yn } into χ(c) (yi = zf (i) ). By (6), the function f is monotone: i1 < i2 →
f (i1 ) < f (i2 ).
Let z ∈ χ(c) and below we prove that one of the following holds:
1.
δ(z) ⊆

[

δ(zj ) ∪ σ(α(b)),

(17)

j

where elements zj occur in χ(c) before z;
2. z is after b in χ(c);
3. z belongs to χ(b), i.e. z = yi or z ∈ χ(α(b)).
Assume for some z ∈ χ(c) all conditions above fail. Let s = α(z)α(b)z. If
s = α(z)α(b) then δ(z) ⊆ σ(α(b)), and (17) holds. Therefore, we assume below
s > α(z)α(b), and we have a nontrivial chain
s = s0 > s1 > . . . > sk > α(z)α(b),
where each si is the ancestor of the previous one. By Lemma 6.8 we have si ∼c α(si ),
and all si belong to the vector χ(c) (Lemma 6.4).
We have the following cases.
1. Let s = z and denote s′ = α(z)b (we use z ∼c α(z) below):
α(z)α(b)z = z ⇒ α(z)α(b)zc = zc ⇒ α(z)α(b)α(z)c = zc ⇒ α(z)(α(b)c) = zc
⇒ α(z)bc = zc ⇒ s′ c = zc.
Since S is right hereditary, the elements z, s′ are ≤-comparable. Thus, we have
the following cases.
(a) If z ≤ s′ then
α(z) ≤ z ≤ α(z)b
and Lemma 4.2 gives α(z) ∼b z. Thus, z should occur in the χ(b), a
contradiction.
(b) Let s′ = α(z)b < z. By the definition of the ancestor (there are not
elements between α(z) and z), we obtain s′ = α(z). Thus, b  α(z).
By (5), we have b ⊏c z, therefore z occurs after b in χ(c), a contradiction
with the choice of z.
2. Let s 6= z and Lemma 6.8 gives δν (s) ⊆ δν (z). If we assume δν (s) = δν (z) then
α(z) ≈ α(s)  α(z)α(b) (Lemma 2.3) and we have α(b)  α(z). Therefore
s = (α(z)α(b))z = α(z)z = z,
a contradiction.
Thus, δν (s) ⊂ δν (z), and Lemma 6.8 provides δν (si ) ⊂ δν (z). By the last
statement of Lemma 6.8, all si occur before z in χ(c). Let
c = σ(α(b)) ∪

k
[

i=0

By (14), c = σ(α(b)) ∪ (σ(s) \ σ(α(z)α(b))).

14

δ(si ).

Let us prove c ⊇ δ(z). Suppose a letter a belongs to the word δ(z). Therefore,
a ∈ σ(z), a ∈
/ σ(α(z)). If a ∈ σ(α(b)) we immediately obtain a ∈ c. Otherwise
(a ∈
/ σ(α(b))), we have
a ∈ σ(z) \ σ(α(z)α(b)) ⇒ a ∈ c.
Thus, we have proved (17) that contradicts the choice of z.
Let us come back to the equality (16). One should prove
h(α(b))c1 c2 . . . cm = h(α(b))b1 b2 . . . bn c1 c2 . . . cm .

(18)

−−→ −−−−→
Since b ∈ χ(b) and b ∈ χ(c), there exists an index i such that δ(yi ) = δ(zf (i) ) =
−−→
δ(b). For each zk , k < f (i) we have one of the following
1. zk ∈ χ(b) (probably, zk ∈ χ(α(b)));
2. zk satisfies (17).
In the second case all letters of ck are eliminated by letters of previous elements
and one can remove such ck from (18). If zk ∈ χ(α(b)) then all letters of ck occur
in h(α(b)) (Lemma 6.7) and ck can be removed from (18).
Thus one can reduce (18) to
−−→
h(α(b))b1 b2 . . . bi−1 δ(b)cf (i)+1 cf (i)+2 . . . cm =
−−→
−−→
h(α(b))b1 b2 . . . bi−1 δ(b)bi+1 . . . bn b1 b2 . . . bi−1 δ(b)cf (i)+1 cf (i)+2 . . . cm ⇔
−−→
−−→
h(α(b))b1 b2 . . . bi−1 δ(b)cf (i)+1 cf (i)+2 . . . cm = h(α(b))b1 b2 . . . bi−1 δ(b)bi+1 . . . bn cf (i)+1 cf (i)+2 . . . cm .
(19)
Relations α(yi ) ∼b yi implies
σ(yi ) ∪ σ(b) = σ(α(yi )) ∪ σ(b) ⇒ δ(yj ) ⊆ σ(b) = σ(α(b)) ∪ δ(b) = σ(h(α(b))) ∪ δ(b).
Therefore, the elements bi+1 , bi+2 , . . . , bn in (19) are eliminated by letters of
−−→
h(α(b)), δ(b), and (19) becomes a true equality:
−−→
−−→
h(α(b))b1 b2 . . . bi−1 δ(b)cf (i)+1 cf (i)+2 . . . cm = h(α(b))b1 b2 . . . bi−1 δ(b)cf (i)+1 cf (i)+2 . . . cm .
Thus, we have proved (16).
Let us prove (15) using (16). Since S is right hereditary, a < b (similarly, one
can assume b < a). Therefore, there exists a chain
b = b0 > b1 > . . . > br = a,
where bi = α(bi−1 ). Since a ≤ bi ≤ b ≤ ac, Lemma 4.2 gives a ∼c bi . The
transitivity of ∼c provides bi+1 ∼c bi . Above we proved h(bi+1 ) ∼h(c) h(bi ), and the
transitivity of ∼h(c) gives h(a) ∼h(c) h(b).

15

6.2

Improving the homomorphism

The homomorphism h : S → F defined above is not necessarily an embedding of S
into F. In other words, it is possible
ker(h) = {(s1 , s2 )|s1 6= s2 , h(s1 ) = h(s2 )} =
6 ∅.
Example 6.10. Let us define a right hereditary band B ′ = {x1 , x2 , x3 , y1 , y2 , y3 }
by the following multiplication table (the identity ε is omitted):
x1 x2 x3 y 1 y 2 y 3
x1 x1 x1 y 1 y 1 y 2 y 3
x2 x2 x2 y 3 y 3 y 3 y 3
x3 x3 x3 x3 x3 x3 x3
y1 y1 y1 y1 y1 y1 y1
y2 y2 y2 y2 y2 y2 y2
y3 y3 y3 y3 y3 y3 y3
The order ≤ over B ′ is defined by:
y3

y1

y2
x

2
✑
✁
✑
✁ ✑
❅
❅ ✁✑✑
ε❅✁✑

x1

x3

Fig. 3
The support semilattice of B ′ is a linear ordered semilattice 1 < 2 < 3, where
σ(ε) = 1, σ(x1 ) = σ(x2 ) = 2, σ(x3 ) = σ(y1 ) = σ(y2 ) = σ(y3 ) = 3.
The embedding ν gives:
σ(x1 ) = σ(x2 ) = a1 , σ(x3 ) = σ(y1 ) = σ(y2 ) = σ(y3 ) = a1 a2 .
−−→
Thus, the embedding ν embeds σ(B ′ ) into F. We have (computing δ(x), we use
a1 <F a2 ):
−−→
x
Sx
⊏x
χ(x)
h(x)
δ(x)
x1
{x1 }
—
a1
(x1 )
a1
x2
{x2 }
—
a1
(x2 )
a1
x3 {x3 , y1 , y3 } y1 ⊏ y2 ⊏ x3 a1 a2
(y1 , y2 , x3 )
a2 a1
y1
{y1 , y3 }
y1 ⊏ y3
a2
(χ(x1 ), y1 , y3 ) a1 a2
y2
{y2 , y3 }
y2 ⊏ y3
a2
(χ(x1 ), y2 , y3 ) a1 a2
y3
{y2 , y3 }
y2 ⊏ y3
a2
(χ(x2 ), y2 , y3 ) a1 a2
Thus, we have a nonempty kernel
ker(h) = {(x1 , x2 ), (y1 , y2 ), (y1 , y3 ), (y2 , y3 )}.

Below we define a series of homomorphisms h1 , h2 , . . . , hm such that
ker(h) ⊃ ker(h1 ) ⊃ ker(h2 ) ⊃ . . . ⊃ ker(hm ) = ∅.
using the next algorithm.

16

Embedding algorithm
INPUT: a homomorphism h : S → F.
OUTPUT: an embedding h′ : S → F.
1. Put h′ = h, and F ′ is the free left regular band generated by letters {ai | ∃s ∈
S, ai ∈ h(s)}.
2. Take c ∈ S such that b1 , b2 , . . . , bk are all descendants of c (α(bi ) = c), and
h′ (bi ) ≤ h′ (bj ) for some distinct i, j;
Apply Modification(h′ , F ′ , c, b1 , b2 , . . . , bk ) (see below) and obtain a new homomorphism h′ and a new free left regular band F ′ .
3. If there is not any c ∈ S from the previous step, we terminate the algorithm.

Modification(h, F, c, b1 , b2 , . . . , bk )
INPUT: a homomorphism h : S → F , free left regular band F , c ∈ S, and all descendants b1 , b2 , . . . , bk of c.
OUTPUT: a homomorphism h′ : S → F ′ , where F ′ ⊇ F is a free left regular band, and h′
is defined as follows.
Let C ⊆ F be the set of all letters a ∈
/ h(c). Let F ′ be the free left regular band
generated by F and new free generators
{t∅c , tbc1 , tbc2 , . . . , tbck }.
Let
t′c = t∅c tbc1 tbc2 . . . tbck ,
Hc = {s ∈ S | h(s) contains a letter from C},
Scbi = {s | ∃y ≥ bi cs = ys},
!
[
Scbi .
Sc∅ = Hc \
i

First, one should prove the following statement.

Lemma 6.11. For all i 6= j Scbi ∩ Scbj = ∅ and Scbi ⊆ Hc .
Proof. Assume s ∈ Scbi ∩ Scbj . It follows that there exist yi , yj such that bi ≤ yi ,
bj ≤ yj , cs = yi s, cs = yi s. Therefore, yi s = yj s and yi , yj should be ≤-comparable.
However it is impossible, since S is right hereditary.
Let us prove Scbi ⊆ Hc . Any s ∈ Scbi satisfies h(c)h(s) = h(y)h(s) for some
y ≥ bi > c. If assume s ∈
/ Hc then h(s)  h(c) ≤ h(y) and the last equality becomes
h(c) = h(y), a contradiction.
Now we are ready to define a new mapping h′ by the following substitutions in
images of h:
(
h(s), if s ∈
/ Hc ,
h′ (s) =
h(s)|a:=atxc t′c , for all a ∈ C if s ∈ Scx (x ∈ {b1 , b2 , . . . , bk , ∅})

17

After the definition of h′ Modification algorithm stops.
Example 6.12. Let us explain the work of Embedding and Modification algorithms at the semigroup B ′ .
First, we take c = ε. Then C = {a1 , a2 }, b1 = x1 , b2 = x2 , b3 = x3 , Sεx1 =
{x1 , y1 , y2 }, Sεx2 = {x2 , y3 }, Sεx3 = {x3 }, Sε∅ = ∅.
By the Modification algorithm, we obtain t′ε = t∅ε txε 1 txε 2 txε 3 . Thus, h′ (x1 ) =
x
a1 tε 1 t∅ε txε 2 txε 3 , h′ (x2 ) = a1 txε 2 t∅ε txε 1 txε 3 ,
h′ (x3 ) = a2 txε 3 t∅ε txε 1 txε 2 a1 txε 3 t∅ε txε 1 txε 2 = a2 txε 3 t∅ε txε 1 txε 2 a1 ,
h′ (y1 ) = h′ (y2 ) = a1 txε 1 t∅ε txε 2 txε 3 a2 txε 1 t∅ε txε 2 txε 3 = a1 txε 1 t∅ε txε 2 txε 3 a2 ,
h′ (y3 ) = a1 txε 2 t∅ε txε 1 txε 3 a2 txε 2 t∅ε txε 1 txε 3 = a1 txε 2 t∅ε txε 1 txε 3 a2 .
We have ker(h′ ) = {(y1 , y2 )}, so one should repeat an iteration of Embedding
algorithm. We take c = x1 and obtain C = a2 b1 = y1 , b2 = y2 , Sx1 y1 = {y1 , x3 }
(since x1 x3 = y1 x3 ), Sx1 y2 = {y2 }, Sx1 ∅ = {y3 }.
Modification algorithm now gives: t′x1 = t∅x1 tyx11 tyx21 , h′′ (x1 ) = h′ (x1 ), h′′ (x2 ) =
h′ (x2 ), h′′ (x3 ) = a2 tyx11 t∅x1 tyx21 txε 3 t∅ε txε 1 txε 2 a1 , h′′ (y1 ) = a1 txε 1 t∅ε txε 2 txε 3 a2 tyx11 t∅x1 tyx21 ,
h′′ (y2 ) = a1 txε 1 t∅ε txε 2 txε 3 a2 tyx21 t∅x1 tyx11 , h′′ (y3 ) = a1 txε 2 t∅ε txε 1 tεx3 a2 t∅x1 tyx11 tyx21 .
Thus, we obtained an embedding h′′ : S → F after two iterations of Embedding
algorithm. 
Lemma 6.13. Let B = {b1 , b2 , . . . , bk , ∅}.
1. Let us consider x, y ∈ S such that x ∈ Scd for some d ∈ B. Then
h′ (x)h′ (y) = h(x)|a:=atdc t′c h(y),

(20)

where a is the first letter of h(x) from the set C.
2. Suppose x, y ∈ S satisfy h(x) < h(y). The inequality h′ (x) < h′ (y) fails only
if x ∈ Scd , y ∈ Sce for distinct e, d ∈ B.
3. Suppose x, y, z ∈ S satisfy h(x) ∼h(z) h(y), h(x) ≤ h(y) and h′ (x) ≤ h′ (y).
The relation h′ (x) ∼h′ (z) h′ (y) fails only if y ∈ Scd , z ∈ Sce for distinct e, d ∈ B
and x ∈
/ Hc .
Proof.
1. Let a′ ∈ C be a letter of the word h(x)h(y) which occurs after a. By
the definition of the map h′ , the letter a (a′ ) will be replaced to the expression
a′ tdc t′c for some d ∈ B (respectively, a′ tec t′c for some e ∈ B). However the
subword tec t′c is eliminated by tdc t′c which occurs earlier. Thus, t-letters will be
occur only after a in h′ (x)h′ (y) and we immediately obtain (20).
2. If y ∈
/ Hc then x ∈
/ Hc (since h(x) < h(y)) and h′ (x) = h(x), h′ (y) = h(y). In
this case the inequality h′ (x) < h′ (y) holds.
Since the case x ∈
/ Hc , y ∈ Hc is impossible, it is sufficient to consider the case
x ∈ Hc , i.e. x ∈ Scd for some d ∈ B. Since h(x) < h(y), we have y ∈ Hc and
x ∈ Sce for some e ∈ B. If d = e then the inequality h′ (x) < h′ (y) remains
true. Thus, d 6= e.
3. If x ∈ Hc then x ∈ Scf for some f ∈ B. Since h′ (x) ≤ h′ (y), y belongs to the
same set Scf . Let a be the first letter from h(x) with a ∈ C (since h(x) ≤ h(y),
a is the first letter from C in the word h(y) = h(x)w). By (20) we have
h′ (x)h′ (z) = h(x)|a:=atf t′ h(z),
c c

18

h′ (y)h′ (z) = h(y)|a:=atf t′ h(z) = h(x)|a:=atf t′ wh(z),
c c

c c

and the equality
h(x)|a:=atf t′ h(z) = h(x)|a:=atf t′ wh(z)
c c

c c

obviously holds, since we have the condition h(x)h(z) = h(x)wh(z).
Thus, below we assume x ∈
/ Hc , i.e. h(x) does not contain letters from C and
′
hence h (x) = h(x). Suppose y ∈ Hc , i.e. y ∈ Scd for some d ∈ B. We have
that the right part of the equality h(x)h(z) = h(y)h(z) contains letters from
C. Therefore, h(z) should contain a letter from C, i.e. z ∈ Sce for some e ∈ B.
Let a ∈ C (a′ ∈ C) be the first letter in the word h(y) (respectively, h(z)).
By (20), we have
h′ (y)h′ (z) = h(y)|a:=atdc t′c h(z),
h′ (x)h′ (z) = h(x)h(z)|a′ :=a′ tec t′c .
It is easy to see that for d = e the equality h′ (x)h′ (z) = h′ (y)h′ (z) holds, and
we came to the contradiction. Thus, d 6= e.
It is sufficient to consider the case x, y ∈
/ Hc , i.e. h′ (x) = h(x), h′ (y) = h(y).
′
If assume z ∈
/ Hc then h (z) = h(z), and the equality h′ (x)h′ (z) = h′ (y)h′ (z)
holds. Thus, we put z ∈ Hc , i.e. z ∈ Sce for some e ∈ B. Therefore,
h′ (x)h′ (z) = h(x)h(z)|a:=atec t′c ,
h′ (y)h′ (z) = h(y)h(z)|a:=atec t′c
for some letter a ∈ C of the word h(z). Obviously, we obtain the equality
h′ (x)h′ (z) = h′ (y)h′ (z) (since h(x)h(z) = h(y)h(z)), a contradiction.
Let us prove that the map h′ defined in Modification procedure is a homomorphism.
Lemma 6.14. If x < y (x, y ∈ S) then
h′ (x) < h′ (y)

(21)

Proof. Since h is a homomorphism and h satisfies Lemma 6.7, we have
h(x) < h(y)

(22)

According to Lemma 6.13, the relation (21) fails only if x ∈ Scd , y ∈ Sce , where
e, d ∈ {b1 , b2 , . . . , bk , ∅} and e 6= d.
1. Let x ∈ Scbi , i.e. there exists x′ ≥ bi such that
cx = x′ x.
Let us multiply the last equality by y and obtain cy = x′ y. Thus, y ∈ Scbi .
2. Suppose y ∈ Scbi . There exists y ′ ≥ bi such that cy = y ′ y. Since x ≤ y, we
have cxy = y ′ xy and the elements cx, y ′ x are ≤-comparable.
For the inequality cx ≥ y ′ x we have
y ′ xcx = cx ⇔ y ′ x = cx (we use y ′ ≥ c) ⇒ x ∈ Scbi .
The relation cx ≤ y ′ x implies (we use α(bi ) = c and y ′ x ≥ bi ) either cx = c or
cx ≥ bi . We have:

19

(a) cx ≥ bi , therefore bi x = cx and x ∈ Scbi ;
(b) cx = c (x  c), then the word h(x) does not contain any letter from
C. Hence, x ∈
/ Hc that gives a contradiction with x ∈ Scd (Lemma 6.11
provides x ∈ Hc ).

Lemma 6.15. h′ is a homomorphism.
Proof. Following Lemma 3.2, it is sufficient to check that h′ preserves the relations
, ∼x .
Actually h′ is a substitution of letters in images of h. Hence, it obviously preserves -relation. Let us prove
h′ (x) ∼h′ (z) h′ (y)

(23)

if x ∼z y. Below we assume x ≤ y. Since h is a homomorphism, we have
h(x) ∼h(z) h(y),

(24)

h′ (x) ≤ h′ (y).

(25)

where h(x) ≤ h(y).
By Lemma 6.14, we have
According to Lemma 6.13, the relation (23) fails only if the word h(x) does not
contain letters from C, but y ∈ Scd , z ∈ Sce for distinct d, e ∈ {∅, b1 , b2 , . . . , bk }.
By the definition of C, we have
x  c.
Suppose y ∈ Scbi . It follows there exist y ′ ≥ bi such that cy = y ′ y. Multiplying
the last equality by z, we obtain
cyz = y ′ yz.
Applying x ∼y z and x  c ≤ y ′ , we have
cyz = y ′ yz ⇒ cxz = y ′ xz ⇒ cz = y ′ z.
The last equality states that z ∈ Scbi and (23) holds.
Suppose now z ∈ Scbi . There exists z ′ ≥ bi such that cz = z ′ z. Since x  c ≤ z ′ ,
we have
cz = z ′ z ⇒ cxz = z ′ xz ⇒ cyz = z ′ yz.
Since S is right hereditary, the elements cy, z ′ y are ≤-comparable.
1. If z ′ y ≤ cy, then (below we use c  z ′ )
z ′ y ≤ cy ⇒ z ′ yc = cy ⇒ z ′ y = cy.
The last equality gives y ∈ Scbi , and (23) holds.
2. If z ′ y ≥ cy, then (we use z ′ y ≥ bi ) either cy = c or cy ≥ bi . The first alternative
gives y  c. It follows that h(y) does not contain new letters t∅c , tbc1 , tbc2 , . . . , tbck ,
and (23) holds.
Let us put cy ≥ bi then
cy ≥ bi ⇔ (bi c)y = cy ⇔ bi y = cy ⇒ y ∈ Scbi
and (23) holds.

20

Lemma 6.16.
Let bi , bj ∈ S (i =
6 j) be elements from Modification procedure.
′
′
Then the elements h (bi ), h (bj ) are not ≤-comparable.
Proof. Clearly, we have bi ∈ Scbi , bj ∈ Scbj , and the words h(bi ), h(bj ) are h(bi ) =
h(c)awi , h(bj ) = h(c)a′ wj for some wi , wj ∈ F and some letters a, a′ (probably,
a = a′ ). The images h′ (bi ), h′ (bj ) are
b

h′ (bi ) = h(c)atbci t′c h′ (wi ), h′ (bj ) = h(c)a′ tcj t′c h′ (wj ),
b

and h′ (bi ), h′ (bj ) have ≤-incomparable prefixes h(c)atbci , h(c)atcj . Thus, the words
h′ (bi ), h′ (bj ) are ≤-incomparable.
By the definition of h′ it immediately follows the next statement.
Lemma 6.17. If h(x), h(y) are not ≤-comparable, so are h′ (x), h′ (y).
By Lemmas 6.16, 6.17, it follows
ker(h) ⊃ ker(h′ ).

(26)

Let us come back to the definition of Embedding Algorithm.
Let h′i be the homomorphism defined by the Modification algorithm at i-th
iteration of Embedding algorithm. By (26), we have
ker(h) ⊃ ker(h′1 ) ⊃ ker(h′2 ) ⊃ . . .

(27)

Since the left regular band S is finite, the chain (27) terminates after finite steps.
It means that Embedding algorithm terminates after finite number of iterations.
Lemma 6.18. Let m be the last iteration of Embedding algorithm, then ker(h′m ) =
∅, i.e. h′m is an embedding of S into F ′ .
Proof. Let us take distinct s1 , s2 with s1 < s2 . Lemma 6.7 gives h(s1 ) < h(s2 ), and
Lemma 6.14 provides h′m (s1 ) < h′m (s2 ) .
Let us take two ≤-incomparable elements s1 , s2 . Therefore, there exist the maximal element c with c < si , and distinct b1 , b2 such that bi ≤ si , α(bi ) = c.
By the termination condition of Embedding algorithm, we have that the words
′
hm (b1 ), h′m (b2 ) are not ≤-comparable. Thus, the words h′m (s1 ), h′m (s2 ) have incomparable prefixes h′m (b1 ), h′m (b2 ), therefore h′m (s1 ) 6= h′m (s2 ).

7

Open problems and further research

7.1 Algebraic geometry: equations with no constants.
How to simplify our proof
Theorem 6.1 has a natural application in the study of equations over F. Let us
remind main definitions of universal algebraic geometry (for more details see [9, 10,
11]).
Let X = {x1 , x2 , . . . , xn } be a finite set of variables, and F(X) be the free left
regular band generated by the set X. The elements of F(X) are called terms.

21

An equality of two terms t(X) = s(X) is called an equation. For example, the
next expressions are equations x1 x2 = x2 x1 , x1 x2 x3 = x3 x4 .
A set Y ⊆ F n is called algebraic if there exists a system of equations in variables
X with the solution set Y . An algebraic set is irreducible if it is not a proper finite
union of algebraic sets.
For any algebraic set Y one can define a left regular band Γ(Y ) which is called
the coordinate band of Y (see [9] for more details). Coordinate bands are analogues
of coordinate rings in commutative algebra, so the description of all algebraic sets
over F may be approximated by the description of their coordinate bands. Notice
that any coordinate band Γ(Y ) is always finitely generated, so all Γ(Y ) over F are
finite (the variety of left regular bands is locally finite).
In [3] submonoids of face monoids were studied. However, applying results of [9]
to [3], one can easily obtain the description of all coordinate bands over F.
Theorem 7.1.
band S:

The following conditions are equivalent for a finite left regular

1. S is a coordinate band of an algebraic set over F;
2. S ∈ Qvar(F);
3. S satisfies the formulas Qn (see [4]);
4. S is embedded into a direct power of the semigroup H = {+, −, 0} defined by:
+ − 0
+ + + +
− − − −
0 + − 0
Actually Theorem 7.1 was proved in [3] with the second condition S ∈ Qvar(H),
but one can prove Qvar(F) = Qvar(H) and obtain the theorem above.
A coordinate band which corresponds to an irreducible algebraic set is called
irreducible. The study of irreducible coordinate bands is important, since any algebraic set over F is a finite union of algebraic ones (it follows from the Noetherian
property of F, see [9] for details).
Theorem 7.1 describes all coordinate bands over F, but the class of irreducible
coordinate bands is described by the following theorem.
Theorem 7.2.
band S:

The following conditions are equivalent for a finite left regular

1. S is a coordinate band of an irreducible algebraic set over F;
2. S is discriminated by F;
3. S ∈ Ucl(F);
4. S is right hereditary and has a local linear order;
5. S is embedded into F.
Proof. The implications (1) ⇔ (2) ⇔ (3) follows from the general results of [9]. The
implication (4) ⇔ (5) is the statement of Theorem 6.1.
Let us prove (2) ⇒ (5). By the definition, a band S is discriminated by F if
for any finite set {s1 , s2 , . . . , sn } ⊆ S there exists a homomorphism h : S → F such
that h(si ) 6= h(sj ) for all i 6= j.
Since any finitely generated left regular band is finite, we have S =
{s1 , s2 , . . . , sn }. By the condition, there exists a homomorphism h : S → F which
is injective on S, i.e. h is an embedding.

22

The implication (5) ⇒ (2) clearly follows from the definition of the discrimination. Thus, the theorem is proved.
Let us explain the class Ucl(F). Let ϕ be a first-order sentence (formula) of the
multiplicative language L = {·}. A formula ϕ is universal if it is equivalent to
∀x1 ∀x2 . . . ∀xn ϕ′ (x1 , x2 , . . . , xn ),
where ϕ′ is quantifier-free. The universal closure of F consists of all left regular
bands S such that S |= ϕ for any universal formula ϕ with F |= ϕ.
According to Theorem 7.2, the embedability of a finite band into F can be
defined by a set of universal formulas. Therefore, the right hereditary and local
linear order properties can be written as universal formulas. A universal formula
defining the right hereditary property is simple:
∀x1 , x2 , x3 (x1 ≤ x3 )&(x2 ≤ x3 ) → (x1 ≤ x2 ∨ x2 ≤ x1 ).
Problem 7.3. Find a set Σ of universal formulas in the language L = {·} such
that the following holds: a finite right hereditary band has a local linear order iff it
satisfies Σ.
We guess the positive solution of Problem 7.3 allows to simplify the proof of
Theorem 6.1. In particular, we will be able to prove it with no the properties of the
embedding ν.

7.2 Algebraic geometry: equations with constants. Advantages of the complicated proof
The current proof of Theorem 6.1 is complicated but it has an advantage. In
Lemma 6.9 we found a homomorphism h : S → F with σ(h(s)) = σ(s), where
σ(s), σ(h(s)) ∈ F. Let us show that this homomorphism property is useful in the
study of equations with constants.
Let X = {x1 , x2 , . . . , xn } be a finite set of variables, and F[X] be the free left
regular band generated by F and X. Elements of F[X] are called F-terms.
An equality of two F-terms t(X) = s(X) is called an F-equation. For example,
the next expressions are F-equations x1 a1 x2 a2 a3 = a3 x2 a4 a1 x1 a2 , x1 x2 a1 x3 a2 a3 =
x3 a4 x4 , x1 x2 = a1 a2 a3 .
One can naturally define algebraic sets and coordinate bands for systems of
equations with constants. Following [9], any coordinate band of such algebraic set
contains a subband isomorphic to F (subband of constants), and any homomorphism
between coordinate bands Γ1 , Γ2 should map F ⊆ Γ1 onto F ⊆ Γ2 (constants are
mapped into constants).
Thus, we need homomorphisms which act trivially on F. Fortunately, the homomorphism h has the required property, and we hope h will play a crucial role in
the solution of the next problem.
Problem 7.4.
Describe coordinate bands of irreducible algebraic sets over F
defined by equations with constants.

7.3

“Almost free” left regular bands

Following Theorem 7.2, the universal closure Ucl(F) consists of right hereditary
bands with a local linear order. According to model theory, Ucl(F) is the “logical

23

neighbourhood” of F, i.e. a structure of each S ∈ Ucl(F) is highly close to F. So
we formulate
Problem 7.5. Prove theorems about the structure of bands from Ucl(F) (right
hereditary bands with a local linear order) and solve uniformly algorithmic problems
(e.g. the word problem) for each band from Ucl(F).
We hope this problem should be solved, since we have a similar result in group
theory. In [12] it was proved the analogue of Theorem 7.2 for a free non-abelian
group F .
Theorem 7.6.
group G:

The following conditions are equivalent for a finitely generated

1. G is a coordinate group of an irreducible algebraic set over F ;
2. G is fully residually free;
3. G ∈ Ucl(F );
4. G is embedded into Lyndon group F Z[t] .
There are results about the structure and algorithms for fully residually groups
(see [13, 14]), and it follows that all groups from Ucl(F ) inherits many properties
of the free group F . Thus, we hope all semigroups from Ucl(F) have many nice
properties.

7.4

Approximation with left regular bands

Many objects (e.g. hyperplane arrangements, matroids) are approximated by left
regular bands (see [1]). In other words, any hyperplane arrangement H (matroid
M ) admits a multiplication such that H (respectively, M ) becomes a left regular
band. Below we shall talk only about matroids, but one can easily reformulate the
following problem for hyperplane arrangements and other objects.
Let S(M ) be the left regular band corresponding to a matroid M . Following [1],
S(M ) of a free matroid of rank n is the free left regular band of the same rank.
Free matroids have a simple structure (the free matroid Mn of rank n is isomorphic
to all subsets of n linearly independent vectors). Thus, it is interesting to describe
matroids which are “almost free”.
Problem 7.7. What can we say about a matroid M with S(M ) ∈ Ucl(F) (i.e.
S(M ) is right hereditary with a local linear order)?

References
[1] K. S. Brown, Semigroups, rings, and Markov chains, J. Theoret. Probab., 13(3),
2000, 871-938.
[2] S. Margolis, F. Saliola, B. Steinberg, Poset topology and homological invariants
of algebras arising in algebraic combinatorics, arXiv:1311.6680.
[3] S. Margolis, F. Saliola, B. Steinberg, Semigroups embeddable in hyperplane
monoids, Semigroup Forum, August 2014, Volume 89, Issue 1, pp 236-248.
[4] S. Margolis, F. Saliola, B. Steinberg, Combinatorial topology and the global
dimension of algebras arising in combinatorics, J. Eur. Math. Soc., to appear.

24

[5] F. Saliola, The quiver of the semigroup algebra of a left regular band, Internat.
J. Algebra Comput., 17(8), 2007, 1593–1610.
[6] F. Saliola, The face semigroup algebra of a hyperplane arrangement, Canad. J.
Math., 61(4), 2009, 904–929.
[7] F. Saliola, The quiver of the semigroup algebra of a left regular band, Int. J.
Algebra Comput., 17(8), 2007, 1593–1610.
[8] F. Saliola, The face semigroup algebra of a hyperplane arrangement, Can. J.
Math. 61(4), 2009, 904–929.
[9] E. Daniyarova, A. Miasnikov, V. Remeslennikov, Unification theorems in algebraic geometry, Algebra and Discrete Mathematics, 1, 2008, 80–111.
[10] E. Yu. Daniyarova, A. G. Myasnikov, V. N. Remeslennikov, Algebraic geometry
over algebraic structures. II. Foundations, Fundam. Prikl. Mat., 17:1, 2012, 65–
106
[11] E. Daniyarova, A. Miasnikov, V. Remeslennikov, Algebraic geometry over algebraic structures III: equationally Noetherian property and compactness, Southeast Asian Bulletin of Mathematics, 2011, 35:1, 35-68
[12] O. Kharlampovich, A. Myasnikov, Irreducible affine varieties over free group
II: Systems in trangular quasi-quadratic form and description of residually free
groups, J. Algebra, 200(2), 1998, 517-570.
[13] O. Kharlampovich, A. Myasnikov, V. Remeslennikov, D. Serbin, Subgroups of
fully residually free groups: algorithmic problems, Contemp. Math. series of
the AMS, Group theory, Statistics and Cryptography, 360, 2004, 63–101.
[14] I. Bumagin,O. Kharlampovich, A. Miasnikov, Isomorphism problem for fully
residually free groups , J. Pure and Applied Algebra, 208 (3), 2007, 961–977.
The information of the author:
Artem N. Shevlyakov
Sobolev Institute of Mathematics
644099 Russia, Omsk, Pevtsova st. 13
Phone: +7-3812-23-25-51.
e-mail: a shevl@mail.ru

25

