Green's Relations - The H and D Relations

The H and D Relations

The remaining relations are derived from L and R. Their intersection is H:

a H b if and only if a L b and a R b.

This is also an equivalence relation on S. The class H_a is the intersection of L_a and R_a. More generally, the intersection of any L-class with any R-class is either an H-class or the empty set.

Green's Theorem states that for any H-class H of a semigroup S either (i) or (ii) and H is a subgroup of S. An important corollary is that the equivalence class H_e, where e is an idempotent, is a subgroup of S (its identity is e, and all elements have inverses), and indeed is the largest subgroup of S containing e. No H-class can contain more than one idempotent, thus H is idempotent separating. In a monoid M, H₁ is traditionally called the group of units. (Beware that unit does not mean identity in this context, i.e. in general there are non-identity elements in H₁. The "unit" terminology comes from ring theory.) For example, in the transformation monoid on n elements, T_n, the group of units is the symmetric group S_n.

Finally, D is defined: a D b if and only if there exists a c in S such that a L c and c R b. In the language of lattices, D is the join of L and R. (The join for equivalence relations is normally more difficult to define, but is simplified in this case by the fact that a L c and c R b for some c if and only if a R d and d L b for some d.)

As D is the smallest equivalence relation containing both L and R, we know that a D b implies a J b — so J contains D. In a finite semigroup, D and J are the same. Furthermore they also coincide in any epigroup.

There is also a formulation of D in terms of equivalence classes, derived directly from the above definition:

a D b if and only if the intersection of R_a and L_b is not empty.

Consequently, the D-classes of a semigroup can be seen as unions of L-classes, as unions of R-classes, or as unions of H-classes. Clifford and Preston (1961) suggest thinking of this situation in terms of an "egg-box":

Each row of eggs represents an R-class, and each column an L-class; the eggs themselves are the H-classes. For a group, there is only one egg, because all five of Green's relations coincide, and make all group elements equivalent. The opposite case, found for example in the bicyclic semigroup, is where each element is in an H-class of its own. The egg-box for this semigroup would contain infinitely many eggs, but all eggs are in the same box because there is only one D-class. (A semigroup for which all elements are D-related is called bisimple.)

It can be shown that within a D-class, all H-classes are the same size. For example, the transformation semigroup T₄ contains four D-classes, within which the H-classes have 1, 2, 6, and 24 elements respectively.

Recent advances in the combinatorics of semigroups have used Green's relations to help enumerate semigroups with certain properties. A typical result (Satoh, Yama, and Tokizawa 1994) shows that there are exactly 1,843,120,128 non-equivalent semigroups of order 8, including 221,805 which are commutative; their work is based on a systematic exploration of possible D-classes. (By contrast, there are only five groups of order 8.)