2. Green’s relations

Mikołaj Bojańczyk

zajęcia / courses

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 $e$ such that $ee=e$ . Typically idempotents are denoted by $e,f$ . The identity is an idempotent. An idempotent power of an element $m$ of a monoid is an element of the form $m^i$ 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 $m^i$ and $m^j$ would be idempotent powers, then we would need to have

$m^i = m^{ij} = m^j$

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

Lemma 1 (Idempotent Power Lemma). If $m$ is an element of a finite monoid of size $n$ , then $m^{n!}$ is an idempotent.

Green’s relations.

For a monoid $M$ , define the following relations. We say that $m \in M$ is a prefix of $n \in M$ if there exists some $x \in M$ such that $n = mx$ . This is the same thing as saying that the right ideal of $m$ , i.e. the set $mM$ , contains the right ideal $nM$ . Likewise we define the suffix and infix relations, using the left ideal $Mm$ and the two-sided ideal $MmM$ , 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 $\Rr$ -ordering, standing for right, the suffix relationship is called the $\Ll$ -ordering, standing for left, and the infix relationship is called the $\Jj$ -ordering, standing for I do not know what. The appropriate equivalences are called $\Rr$ -equivalence, etc. The orderings are traditionally written in what I would consider a counter-intuitive way, i.e. if $m$ is a prefix of $n$ , then one writes $m \ge_\Rr n$ , this notation is motivated by the ideal inclusion. To avoid this notation, I will say that $m$ is $\Ll$ -simpler than $n$ if $m$ is a prefix of $n$ , likewise for $\Rr$ -simpler and $\Jj$ -simpler. To say that the relationship is strict, we will say strictly $\Ll$ -simpler, e.g. every element is $\Ll$ -simpler than itself, but not strictly $\Ll$ -simpler.

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

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

Proof. By the assumptions of the lemma, there exist $x,y,z$ in the monoid such that $n=mx$ and $m=ynz$ . By iterating these equalities, we see that

$m=y^i m (xz)^i$

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

$m = y^i m (xz)^i = y^i m (xz)^i (xz)^i = m (xz)^i = n (zx)^{i-1}z$

thus proving that $n$ is a prefix of $m$ . $\Box$

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 $\Hh$ -equivalent if they have the same $\Rr$ -class and the same $\Ll$ -class. Therefore an $\Hh$ -class is an intersection of an $\Rr$ -class and an $\Ll$ -class.

Lemma 3 ( $\Hh$ -Dichotomy Lemma). Let $H$ be an $\Hh$ -class included in a $\Jj$ -class $J$ . Then either
• $mn \not \in J$ for every $m,m \in H$ ; or
• $H$ is a group

Proof. Suppose that there exist $m_0,n_0 \in H$ such that $m_0n_0 \in J$ . We will prove that $H$ is a group. (Note also that the alternative in the statement of the lemma is exclusive.)

First let us show that $mn \in J$ holds for every $m,n \in H$ . Since $m$ is in the same $\Ll$ -class as $m_0$ , there is some $x$ such that $m_0=xm$ . Likewise, since $n$ is in the same $\Rr$ -class as $n_0$ , there is some $y$ such that $n_0=ny$ . Therefore $mn \in J$ since it is an infix of some element of $J$ , namely $mn=xm_0n_0y$ .

Now let us show that $H$ is a monoid, i.e. $mn \in H$ holds for every $m,n \in H$ . Since $m$ is a prefix of $mn$ , then by the Eggbox Lemma, $m$ is $\Rr$ -equivalent to $mn$ . Likewise, $n$ is $\Ll$ -equivalent to $mn$ , and therefore $mn \in H$ .

Finally let us show that $H$ is a group.

By the Idempotent Power Lemma, $H$ contains some idempotent, call it $e$ . We will show that this idempotent is the identity with respect to multiplication in $H$ , and is therefore unique. Let $m \in H$ . Because $m$ and $e$ are in the same $\Ll$ -class, there is some $x$ such that $m=xe$ . Therefore $me=xee=xe=m$ . By a symmetric argument, $em=m$ holds for every $m \in H$ , and therefore $e$ is the identity in $H$ .

Let us now show that $H$ has inverses. By the Idempotent Power Lemma, every $m \in H$ has some idempotent power, call it $m^k$ . As mentioned in the previous paragraph, there can only be one idempotent in $H$ . Therefore $m^{k-1}$ is the inverse of $m$ .

This completes the proof of the lemma. $\Box$

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

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

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

zajęcia / courses

2. Green’s relations

Leave a Reply