In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951. John Mackintosh Howie, a prominent semigroup theorist, described this work as "so all-pervading that, on encountering a new semigroup, almost the first question one asks is 'What are the Green relations like?'" (Howie 2002). The relations are useful for understanding the nature of divisibility in a semigroup; they are also valid for groups, but in this case tell us nothing useful, because groups always have divisibility. (In the same way, the ideals of a field are a much less rich environment for study than the ideals of a ring.) Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations related to: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has media related to: Mathematics Inter. ... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ... In mathematics, a semigroup is a set with an associative binary operation on it. ... In Ring theory, a branch of abstract algebra, a principal ideal is an ideal I in a ring R that is generated by a single element a of R. More specifically: a left principal ideal of R is a subset of R of the form Ra := {ra : r in R... John Mackintosh Howie was a prominent semigroup theorist in the 20th century. ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ... In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have similar (but not identical) properties to those familiar from the integers. ...

Instead of working directly with a semigroup S, we define Green's relations over the monoid S¹. (S¹ is "S with an identity adjoined if necessary"; if S is not already a monoid, a new element is adjoined and defined to be an identity.) This ensures that principal ideals generated by some semigroup element do indeed contain that element. For an element a of S, the relevant ideals are: In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ...

• The principal left ideal generated by a: . This is the same as , which is .
• The principal right ideal generated by a: , or equivalently .
• The principal two-sided ideal generated by a: S¹aS¹, or .

The L, R, and J relations

For elements a and b of S, Green's relations L, R and J are defined by

• a L b if and only if S¹ a = S¹ b.
• a R b if and only if a S¹ = b S¹.
• a J b if and only if S¹ a S¹ = S¹ b S¹.

That is, a and b are L-related if they generate the same left ideal; R-related if they generate the same right ideal; and J-related if they generate the same two-sided ideal. These are equivalence relations on S, so each of them yields a partition of S into equivalence classes. The L-class of a is denoted L_a (and similarly for the other relations). ↔ ⇔ ≡ logical symbols representing iff. ...

Green used the lowercase blackletter , and for these relations, and wrote for a L b (and likewise for R and J). Mathematicians today tend to use script letters such as instead, and replace Green's modular arithmetic-style notation with the infix style used here. Ordinary letters are used for the equivalence classes. Blackletter in a Latin Bible of AD 1407, on display in Malmesbury Abbey, Wiltshire, England. ... Modular arithmetic is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

The L and R relations are left-right dual to one another; theorems concerning one can be translated into similar statements about the other. For example, L is right-compatible: if a L b and c is another element of S, then ac L bc. Dually, R is left-compatible: if a R b, then ca R cb.

If S is commutative, then L, R and J coincide.

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. An important theorem states 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. For example, in the transformation semigroup on n elements, T_n, the H-class of the identity map is the symmetric group S_n. In mathematics, an idempotent element is an element which, intuitively, leaves something unchanged. ... In mathematics, a transformation semigroup is a collection of mappings on a set X closed under composition. ... In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ...

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.

Finally, D is defined by

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.) The term lattice derives from the shape of the Hasse diagrams that result from depicting these orders. ...

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.

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.) Download high resolution version (1280x840, 107 KB)Photograph of an egg carton. ... In mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. ...

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.) Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. ... The following list in mathematics contains the finite groups of small order up to group isomorphism. ...

Example

The full transformation semigroup T₃ consists of all functions from the set {1, 2, 3} to itself; there are 27 of these. Write (a b c) for the function which sends 1 to a, 2 to b, and 3 to c. Since T₃ contains the identity map, (1 2 3), there is no need to adjoin an identity.

The egg-box diagram for T₃ has three D-classes. They are also J-classes, because these relations coincide for a finite semigroup.

In T₃, two functions are L-related if and only if they have the same image. Such functions appear in the same column of the table above. Likewise, the functions f and g are R-related if and only if In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. ...

f(x) = f(y) ⇔ g(x) = g(y)

for x and y in {1, 2, 3}; such functions are in the same table row. Consequently, two functions are D-related if and only if their images are the same size.

The elements in bold are the idempotents. Any H-class containing one of these is a (maximal) subgroup. In particular, the third D-class is isomorphic to the symmetric group S₃. There are also six subgroups of order 2, and three of order 1 (as well as subgroups of these subgroups). Six elements of T₃ are not in any subgroup.

Generalisations

There are essentially two ways of generalising an algebraic theory. One is to change its definitions so that it covers more or different objects; the other, more subtle way, is to find some desirable outcome of the theory and consider alternative ways of reaching that conclusion.

Following the first route, analogous versions of Green's relations have been defined for semirings (Grillet 1970) and rings (Petro 2002). Some, but not all, of the properties associated with the relations in semigroups carry over to these cases. Staying within the world of semigroups, Green's relations can be extended to cover relative ideals, which are subsets that are only ideals with respect to a subsemigroup (Wallace 1963). In abstract algebra, a semiring is an algebraic structure, similar to a ring, but without additive inverses. ...

For the second kind of generalisation, researchers have concentrated on properties of bijections between L- and R- classes. If x R y, then it is always possible to find bijections between L_x and L_y that are R-class-preserving. (That is, if two elements of an L-class are in the same R-class, then their images under a bijection will still be in the same R-class.) The dual statement for x L y also holds. These bijections are right and left translations, restricted to the appropriate equivalence classes. The question that arises is: how else could there be such bijections? In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one-to-one and onto. ...

Suppose that Λ and Ρ are semigroups of partial transformations of some semigroup S. Under certain conditions, it can be shown that if x Ρ = y Ρ, with x ρ₁ = y and y ρ₂ = x, then the restrictions

ρ₁ : Λ x → Λ y

ρ₂ : Λ y → Λ x

are mutually inverse bijections. (Conventionally, arguments are written on the right for Λ, and on the left for Ρ.) Then the L and R relations can be defined by

x L y if and only if Λ x = Λ y

x R y if and only if x Ρ = y Ρ

and D and H follow as normal. Generalisation of J is not part of this system, as it plays no part in the desired property.

We call (Λ, Ρ) a Green's pair. There are several choices of partial transformation semigroup that yield the original relations. One example would be to take Λ to be the semigroup of all left translations on S¹, restricted to S, and Ρ the corresponding semigroup of restricted right translations.

These definitions are due to Clark and Carruth (1980). They subsume Wallace's work, as well as various other generalised definitions proposed in the mid-1970s. The full axioms are fairly lengthy to state; informally, the most important requirements are that both Λ and Ρ should contain the identity transformation, and that elements of Λ should commute with elements of Ρ.

References

• Generalized Green's theories, C. E. Clark and J. H. Carruth. Semigroup Forum 20(2) 1980, p95-127.
• The algebraic theory of semigroups, A. H. Clifford and G. B. Preston. American Mathematical Society, 1961 (volume 1), 1967 (volume 2). Green's relations are introduced in Chapter 2 of the first volume.
• On the structure of semigroups, J. A. Green. Annals of Mathematics (second series) 54(1), July 1951, pages 163-172.
• Green's relations in a semiring, Mireille P. Grillet. Portugal. Math. 29, 1970, p181-195.
• An introduction to semigroup theory, J. M. Howie. Academic Press, 1976. ISBN 0-12-356950-8. An updated version is available as Fundamentals of semigroup theory, Oxford University Press, 1995. ISBN 0-19-851194-9.
• Semigroups, Past, Present and Future, J. M. Howie. Proceedings of the International Conference on Algebra and its Applications, 2002.
• Green's relations and minimal quasi-ideals in rings, Petraq Petro. Comm. Algebra 30(10), 2002, p4677-4686.
• Semigroups of order 8, S. Satoh, K. Yama, and M. Tokizawa. Semigroup Forum 49, 1994, pages 7-29.