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\) iff 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\) iff 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\) iff 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 \iff 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 \iff 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}\).

A subgroup \(H\) of a semigroup \(S\) is called maximal if it is not properly contained in any other subgroup of \(S\). That is, \(H\) is maximal if for every subgroup \(K\) of \(S\) with \(H \subseteq K\), we have \(H = K\).

Let \(S\) be a semigroup. A subgroup of \(S\) is a subset \(H \subseteq S\) equipped with:

1. A carrier set \(H \subseteq S\);

2. Closure under multiplication: For all \(a, b \in H\), we have \(a \cdot b \in H\);

3. An identity element \(e \in H\) such that:

   • \(e \in H\) (the identity is in the carrier);

   • For all \(x \in H\), \(e \cdot x = x\) (left identity);

   • For all \(x \in H\), \(x \cdot e = x\) (right identity);

4. An inverse function \(\mathrm{inv} : S \to S\) such that:

   • For all \(x \in H\), \(\mathrm{inv}(x) \in H\) (closure under inverses);

   • For all \(x \in H\), \(\mathrm{inv}(x) \cdot x = e\) (left inverse);

   • For all \(x \in H\), \(x \cdot \mathrm{inv}(x) = e\) (right inverse).

With these properties, the carrier \(H\) forms a group under the multiplication inherited from \(S\).

Note that the identity element \(e\) is uniquely determined by the carrier set: if \(e_1\) and \(e_2\) are both identities for the same carrier \(H\), then \(e_1 = e_1 \cdot e_2 = e_2\). Similarly, the inverse function is uniquely determined by the carrier and identity.

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.

Let \(S\) be a semigroup and suppose \(x \mathcal{R} y\) with witnesses \(u, v \in S\) such that \(x \cdot v = y\) and \(y \cdot u = x\). Then:

1. The map \(\rho _v : w \mapsto w \cdot v\) is a bijection from the \(\mathcal{L}\)-class of \(x\) to the \(\mathcal{L}\)-class of \(y\).

2. The map \(\rho _u : w \mapsto w \cdot u\) is the inverse of \(\rho _v\).

3. These bijections preserve \(\mathcal{H}\)-classes: for any \(a, b\) in the \(\mathcal{L}\)-class of \(x\), we have \(a \mathcal{H} b\) if and only if \(a \cdot v \mathcal{H} b \cdot v\).

Dually, if \(x \mathcal{L} y\) with witnesses \(u, v\) such that \(v \cdot x = y\) and \(u \cdot y = x\), then left translation \(\lambda _v : w \mapsto v \cdot w\) is a bijection from the \(\mathcal{R}\)-class of \(x\) to the \(\mathcal{R}\)-class of \(y\), with inverse \(\lambda _u\), and these bijections preserve \(\mathcal{H}\)-classes.

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\).

Let \(S\) be a semigroup and let \(e \in S\) be an idempotent element. Then:

1. The \(\mathcal{H}\)-class \([e]_{\mathcal{H}}\) is closed under multiplication.

2. The element \(e\) acts as an identity on \([e]_{\mathcal{H}}\): for all \(x \in [e]_{\mathcal{H}}\), \(e \cdot x = x\) and \(x \cdot e = x\).

3. Every element \(x \in [e]_{\mathcal{H}}\) has an inverse \(y \in [e]_{\mathcal{H}}\) satisfying \(x \cdot y = e\) and \(y \cdot x = e\).

4. The \(\mathcal{H}\)-class \([e]_{\mathcal{H}}\) forms a subgroup of \(S\) with identity \(e\).

5. Every maximal subgroup of \(S\) is the \(\mathcal{H}\)-class of some idempotent.

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\).

Let \(S\) be a semigroup and let \(x, y \in S\). The following conditions are equivalent:

1. \(x \cdot y \in [x]_{\mathcal{R}} \cap [y]_{\mathcal{L}}\) (i.e., \(x \cdot y \mathcal{R} x\) and \(x \cdot y \mathcal{L} y\)).

2. There exists an idempotent \(e \in [y]_{\mathcal{R}} \cap [x]_{\mathcal{L}}\).

Moreover, in a finite semigroup, these conditions are equivalent to:

1. \(x \mathcal{D} y\) and \(x \cdot y \mathcal{D} x\).

Let \(S\) be a semigroup and let \(H\) and \(K\) be maximal subgroups of \(S\). If there exist \(x \in H\) and \(y \in K\) with \(x \mathcal{D} y\), then \(H\) and \(K\) are isomorphic as groups.

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 \iff \) 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.