Green's relations

Last updated

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.

Contents

Instead of working directly with a semigroup S, it is convenient to define Green's relations over the monoid S1. (S1 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:

The L, R, and J relations

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

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 La (and similarly for the other relations). The L-classes and R-classes can be equivalently understood as the strongly connected components of the left and right Cayley graphs of S1. [1] Further, the L, R, and J relations define three preordersL, ≤R, and ≤J, where aJb holds for two elements a and b of S if the ideal generated by a is included in that of b, i.e., S1aS1S1bS1, and ≤L and ≤R are defined analogously. [2]

Green used the lowercase blackletter , and for these relations, and wrote for aLb (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.

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 aLb and c is another element of S, then acLbc. Dually, R is left-compatible: if aRb, then caRcb.

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:

aHb if and only if aLb and aRb.

This is also an equivalence relation on S. The class Ha is the intersection of La and Ra. 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 -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 He, 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 -class can contain more than one idempotent, thus is idempotent separating. In a monoid M, the class H1 is traditionally called the group of units . [3] (Beware that unit does not mean identity in this context, i.e. in general there are non-identity elements in H1. The "unit" terminology comes from ring theory.) For example, in the transformation monoid on n elements, Tn, the group of units is the symmetric group Sn.

Finally, D is defined: aDb if and only if there exists a c in S such that aLc and cRb. 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 aLc and cRb for some c if and only if aRd and dLb for some d.)

As D is the smallest equivalence relation containing both L and R, we know that aDb implies aJbso J contains D. In a finite semigroup, D and J are the same, [4] as also in a rational monoid. [5] [ clarification needed ] Furthermore they also coincide in any epigroup. [6]

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

aDb if and only if the intersection of Ra and Lb 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": [8]

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 T4 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 that are commutative; their work is based on a systematic exploration of possible D-classes. (By contrast, there are only five groups of order 8.)

Example

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

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

(1 1 1)(2 2 2)(3 3 3)
(1 2 2),
(2 1 1)
(1 3 3),
(3 1 1)
(2 3 3),
(3 2 2)
(2 1 2),
(1 2 1)
(3 1 3),
(1 3 1)
(3 2 3),
(2 3 2)
(2 2 1),
(1 1 2)
(3 3 1),
(1 1 3)
(3 3 2),
(2 2 3)
(1 2 3), (2 3 1),
(3 1 2), (1 3 2),
(3 2 1), (2 1 3)

In T3, 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

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 S3. There are also six subgroups of order 2, and three of order 1 (as well as subgroups of these subgroups). Six elements of T3 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).

For the second kind of generalisation, researchers have concentrated on properties of bijections between L- and R- classes. If xRy, then it is always possible to find bijections between Lx and Ly 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 xLy 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?

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ρ1 = y and yρ2 = x, then the restrictions

ρ1 : ΛxΛy
ρ2 : Λ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

xLy if and only if Λx = Λy
xRy if and only if xΡ = yΡ

and D and H follow as usual. 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 S1, 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 Ρ.

See also

Related Research Articles

<span class="mw-page-title-main">Equivalence relation</span> Mathematical concept for comparing objects

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.

<span class="mw-page-title-main">Monoid</span> Algebraic structure with an associative operation and an identity element

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.

In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that "division" is always possible. Quasigroups differ from groups mainly in that they need not be associative and need not have an identity element.

<span class="mw-page-title-main">Semigroup</span> Algebraic structure consisting of a set with an associative binary operation

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

In mathematics, the concept of an inverse element generalises the concepts of opposite and reciprocal of numbers.

In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure in the sense that algebraic operations done with equivalent elements will yield equivalent elements. Every congruence relation has a corresponding quotient structure, whose elements are the equivalence classes for the relation.

<span class="mw-page-title-main">Generating set of a group</span> Abstract algebra concept

In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.

Ring theory is the branch of mathematics in which rings are studied: that is, structures supporting both an addition and a multiplication operation. This is a glossary of some terms of the subject.

<span class="mw-page-title-main">Semiring</span> Algebraic ring that need not have additive negative elements

In abstract algebra, a semiring is an algebraic structure. It is a generalization of a ring, dropping the requirement that each element must have an additive inverse. At the same time, it is a generalization of bounded distributive lattices.

In mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. Although it is in fact a monoid, it is usually referred to as simply a semigroup. It is perhaps most easily understood as the syntactic monoid describing the Dyck language of balanced pairs of parentheses. Thus, it finds common applications in combinatorics, such as describing binary trees and associative algebras.

In group theory, an inverse semigroupS is a semigroup in which every element x in S has a unique inversey in S in the sense that x = xyx and y = yxy, i.e. a regular semigroup in which every element has a unique inverse. Inverse semigroups appear in a range of contexts; for example, they can be employed in the study of partial symmetries.

In mathematics, a GCD domain is an integral domain R with the property that any two elements have a greatest common divisor (GCD); i.e., there is a unique minimal principal ideal containing the ideal generated by two given elements. Equivalently, any two elements of R have a least common multiple (LCM).

In abstract algebra, a semiheap is an algebraic structure consisting of a non-empty set H with a ternary operation denoted that satisfies a modified associativity property:

In algebra, a presentation of a monoid is a description of a monoid in terms of a set Σ of generators and a set of relations on the free monoid Σ generated by Σ. The monoid is then presented as the quotient of the free monoid by these relations. This is an analogue of a group presentation in group theory.

In mathematics, a regular semigroup is a semigroup S in which every element is regular, i.e., for each element a in S there exists an element x in S such that axa = a. Regular semigroups are one of the most-studied classes of semigroups, and their structure is particularly amenable to study via Green's relations.

A biordered set is a mathematical object that occurs in the description of the structure of the set of idempotents in a semigroup.

In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered as unary operator, exhibits certain fundamental properties of the operation of taking the inverse in a group: uniqueness, double application "cancelling itself out", and the same interaction law with the binary operation as in the case of the group inverse. It is thus not a surprise that any group is a semigroup with involution. However, there are significant natural examples of semigroups with involution that are not groups.

In abstract algebra, in semigroup theory, a Schützenberger group is a certain group associated with a Green H-class of a semigroup. The Schützenberger groups associated with different H-classes are different. However, the groups associated with two different H-classes contained in the same D-class of a semigroup are isomorphic. Moreover, if the H-class itself were a group, the Schützenberger group of the H-class would be isomorphic to the H-class. In fact, there are two Schützenberger groups associated with a given H-class and each is antiisomorphic to the other.

In abstract algebra, an epigroup is a semigroup in which every element has a power that belongs to a subgroup. Formally, for all x in a semigroup S, there exists a positive integer n and a subgroup G of S such that xn belongs to G.

References

  1. "How can you use Green's relations to learn about a monoid?". Stack Exchange . November 19, 2015.
  2. Johnson, Marianne; Kambites, Mark (2011). "Green's J-order and the rank of tropical matrices". arXiv: 1102.2707 [math.RA].
  3. Howie, p. 171
  4. Gomes, Pin & Silva (2002), p. 94
  5. Sakarovitch, Jacques (September 1987). "Easy multiplications I. The realm of Kleene's theorem". Information and Computation. 74 (3): 173–197. doi: 10.1016/0890-5401(87)90020-4 . Zbl   0642.20043.
  6. Peter M. Higgins (1992). Techniques of semigroup theory. Oxford University Press. p. 28. ISBN   978-0-19-853577-5.
  7. Lawson (2004) p. 219
  8. Lawson (2004) p. 220