This lecture contains two basic pieces of information about the structure of finite monoids, namely the existence of an idempotent power, and the definitions of Green’s relations together with one basic lemma about them.

The reader will also observe that all of the material in this lecture, with the exception of Lemma 4, applies to the more general case of semigroups (a semigroup is like a monoid, except it does not need to have the identity element).

Idempotent power

An idempotent in a monoid is an element such that . Typically idempotents are denoted by . The identity is an idempotent. An idempotent power of an element of a monoid is an element of the form that is idempotent.  It is easy to see that the idempotent power, if it exists, is unique (in the sense that the monoid element is unique, not the exponent), because if and would be idempotent powers, then we would need to have

   

The following basic lemma shows that every element of a finite monoid has an idempotent power. This idempotent power will be denoted by here. A more standard notation would be instead of , but the will be used in later lectures on infinite words.

Lemma 1 (Idempotent Power Lemma). If is an element of a finite monoid of size , then is an idempotent.

 

---

 

Green’s relations.

For a monoid , define the following relations. We say that is a prefix of if there exists some such that . This is the same thing as saying that the right ideal of , i.e. the set , contains the right ideal .  Likewise we define the suffix and infix relations, using the left ideal and the two-sided ideal , respectively. It is easy to check that all three relations are quasi-orderings, in the sense that they are transitive and reflexive, but not necessarily anti-symmetric.

Traditionally in monoid theory, the prefix relationship is called the -ordering, standing for right, the suffix relationship is called the -ordering, standing for left, and the infix relationship is called the -ordering, standing for I do not know what. The appropriate equivalences are called -equivalence, etc. The orderings are traditionally written in what I would consider a counter-intuitive way, i.e. if is a prefix of , then one writes , this notation is motivated by the ideal inclusion. To avoid this notation, I will say that is -simpler than if is a prefix of , likewise for -simpler and -simpler. To say that the relationship is strict, we will say strictly -simpler, e.g. every element is -simpler than itself, but not strictly -simpler.

Clearly a prefix is a special case of an infix. Therefore, every -class, i.e. every equivalence class with respect to prefixes, is entirely included in some -class, i.e. some equivalence class with respect to infixes. A key property of finite monoids is that inside a single -class, the -classes form an antichain.

Lemma 2 (Eggbox Lemma). Consider elements of a finite monoid. If is a prefix of and they are both in the same -class, then also is a prefix of .

Proof. By the assumptions of the lemma, there exist in the monoid such that and . By iterating these equalities, we see that  

   

holds for every natural number .  If we choose to be the idempotent power of the monoid, which exists by the assumption on finiteness, we see that

   

thus proving that is a prefix of .

The above lemma, although simple, will be used very frequently in the following lectures, and one could say that it essentially contains the theory of finite monoids.

---

Call elements -equivalent if they have the same -class and the same -class. Therefore an -class is an intersection of an -class and an -class.

Lemma 3 (-Dichotomy Lemma). Let be an -class included in a -class . Then either
•   for every ; or
• is a group

Proof. Suppose that  there exist  such that . We will prove that is a group. (Note also that the alternative in the statement of the lemma is exclusive.)

First let us show that  holds for every . Since is in the same -class as , there is some such that . Likewise, since is in the same -class as , there is some such that . Therefore since it is an infix of some element of , namely .

Now let us show that is a monoid, i.e. holds for every .  Since is a prefix of , then by the Eggbox Lemma, is -equivalent to . Likewise, is -equivalent to , and therefore .

Finally let us show that is a group.

By the Idempotent Power Lemma, contains some idempotent, call it . We will show that this idempotent is the identity with respect to multiplication in , and is therefore unique. Let . Because and are in the same -class, there is some such that . Therefore . By a symmetric argument, holds for every , and therefore is the identity in .

Let us now show that has inverses. By the Idempotent Power Lemma, every has some idempotent power, call it . As mentioned in the previous paragraph, there can only be one idempotent in . Therefore is the inverse of .

This completes the proof of the lemma.

A corollary of the -dichotomy lemma is that an -class is a group if and only if it contains an idempotent.

Lemma 4. The -class of the identity is a group.

Proof. Since the identity is an idempotent, the  -Dichotomy Lemma implies that the -class of the identity is a group. We will now prove that the -class of the identity is the same thing as the -class of the identity. If is in the -class of the identity, then since the identity is a prefix of , the Eggbox Lemma can be used to conclude that the identity is -equivalent to . Likewise for -classes. Therefore, the -class of the identity is actually an -class.

 

 

COMMENTS