Dependencies

In a semigroup \(S\), Green’s relations are a set of five equivalence relations that characterize the elements of \(S\) in terms of the principal ideals they generate. These relations are fundamental to the study of semigroups.

First, we define four preorder relations: \(\leq _{\mathcal{R}}\), \(\leq _{\mathcal{L}}\), \(\leq _{\mathcal{J}}\), and \(\leq _{\mathcal{H}}\). Let \(S^1\) be the monoid obtained by adjoining an identity element to \(S\) if it does not already have one. For any two elements \(x, y \in S\):

• \(x \leq _{\mathcal{R}} y\) if and only if the principal right ideal generated by \(x\) is a subset of the principal right ideal generated by \(y\) (\(xS^1 \subseteq yS^1\)). In Lean, we use the equivalent definition that there must exist some \(z \in S^1\) such that \(x = yz\).

• \(x \leq _{\mathcal{L}} y\) if and only if the principal left ideal generated by \(x\) is a subset of the principal left ideal generated by \(y\) (\(S^1x \subseteq S^1y\)). In Lean, we use the equivalent definition that there must exist some \(z \in S^1\) such that \(x = zy\).

• \(x \leq _{\mathcal{J}} y\) if and only if the principal two-sided ideal generated by \(x\) is a subset of the principal two-sided ideal generated by \(y\) (\(S^1xS^1 \subseteq S^1yS^1\)). In Lean, we use the equivalent definition that there must exist some \(u, v \in S^1\) such that \(x = uyv\).

• \(x \leq _{\mathcal{H}} y\) if and only if \(x \leq _{\mathcal{R}} y\) and \(x \leq _{\mathcal{L}} y\).

These four relations are preorders (they are reflexive and transitive).

From these preorders, we define the equivalence relations \(\mathcal{R}\), \(\mathcal{L}\), \(\mathcal{J}\), and \(\mathcal{H}\) as the symmetric closures of their corresponding preorders. For example, \(x \mathcal{R} y\) if and only if \(x \leq _{\mathcal{R}} y\) and \(y \leq _{\mathcal{R}} x\). The equivalence classes are denoted by \([x]_{\mathcal{R}}\), \([x]_{\mathcal{L}}\), etc.

Finally, the \(\mathcal{D}\) relation is defined by composing \(\mathcal{R}\) and \(\mathcal{L}\): \(x \mathcal{D} y\) if there exists an element \(z \in S\) such that \(x \mathcal{R} z\) and \(z \mathcal{L} y\). It can be shown that \(\mathcal{D}\) is an equivalence relation and that it can also be defined by composing \(\mathcal{L}\) and \(\mathcal{R}\).

The \(\mathcal{D}\) relation is closed under composition with \(\mathcal{R}\) and \(\mathcal{L}\). If \(x \mathcal{D} y\) and \(y \mathcal{L} z\), then \(x \mathcal{D} z\). Similarly, if \(x \mathcal{D} y\) and \(y \mathcal{R} z\), then \(x \mathcal{D} z\). This property is used to prove the transitivity of \(\mathcal{D}\).

In a finite semigroup, the \(\mathcal{D}\) and \(\mathcal{J}\) relations are equivalent. That is, for any two elements \(x, y \in S\), \(x \mathcal{D} y\) if and only if \(x \mathcal{J} y\).

In a finite monoid \(M\), if an element \(a\) satisfies the property \(a = xay\) for some \(x, y \in M\), then there exist non-zero powers of \(x\) and \(y\), say \(n_1\) and \(n_2\), such that \(x^{n_1}a = a\) and \(ay^{n_2} = a\).

In a finite semigroup, for any element \(x\), there exists a positive integer \(m\) such that \(x^m\) is an idempotent. This idempotent power is unique. The existence is a consequence of the fact that in a finite semigroup, the sequence of powers of an element \(x, x^2, x^3, \dots \) must eventually repeat. From a repeating sequence, an idempotent can be constructed.

Green’s relations are preserved under semigroup morphisms. Let \(f: S \to T\) be a semigroup morphism. If two elements \(x, y \in S\) are related by any of Green’s preorders or equivalence relations, then their images \(f(x), f(y)\) are related by the same relation in \(T\).

The \(\mathcal{R}\) and \(\mathcal{L}\) relations exhibit compatibility with semigroup multiplication on one side. Specifically, the \(\mathcal{R}\)-preorder is compatible with left multiplication, and the \(\mathcal{L}\)-preorder is compatible with right multiplication. If \(x \leq _{\mathcal{R}} y\), then for any \(z \in S\), we have \(zx \leq _{\mathcal{R}} zy\). This property extends to the equivalence relation \(\mathcal{R}\). If \(x \mathcal{R} y\), then \(zx \mathcal{R} zy\). A similar argument holds for the \(\mathcal{L}\)-preorder and \(\mathcal{L}\)-equivalence, which are compatible with right multiplication. If \(x \leq _{\mathcal{L}} y\), then \(xz \leq _{\mathcal{L}} yz\) for any \(z \in S\).

In a finite semigroup, if an element \(x\) can be written as \(x = uxv\) for some \(u, v \in S\), then \(x\) is \(\mathcal{H}\)-equivalent to both \(ux\) and \(xv\).

In a finite semigroup, if two elements are \(\mathcal{J}\)-equivalent, then a one-sided preorder implies the corresponding one-sided equivalence. Specifically, if \(x \mathcal{J} y\) and \(x \leq _{\mathcal{R}} y\), then \(x \mathcal{R} y\). Similarly, if \(x \mathcal{J} y\) and \(x \leq _{\mathcal{L}} y\), then \(x \mathcal{L} y\).

Let \(e\) be an idempotent element in a semigroup \(S\). An element \(x \in S\) is \(\mathcal{R}\)-below \(e\) if and only if \(x = ex\). Similarly, \(x\) is \(\mathcal{L}\)-below \(e\) if and only if \(x = xe\). It follows that \(x\) is \(\mathcal{H}\)-below \(e\) if and only if both conditions hold, i.e., \(x = ex\) and \(x = xe\).

The composition of the relations \(\mathcal{R}\) and \(\mathcal{L}\) is commutative. That is, for any \(x, y \in S\), there exists a \(z\) such that \(x \mathcal{R} z\) and \(z \mathcal{L} y\) if and only if there exists a \(w\) such that \(x \mathcal{L} w\) and \(w \mathcal{R} y\). This can be written as \(\mathcal{R} \circ \mathcal{L} = \mathcal{L} \circ \mathcal{R}\). This property is crucial for proving that the relation \(\mathcal{D} = \mathcal{R} \circ \mathcal{L}\) is symmetric, and therefore an equivalence relation.