Green's relations
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, Green's relations are five
equivalence relation 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. Each equivalence relatio ...
s that characterise the elements of a
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
in terms of the
principal ideal In mathematics, specifically ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R. The term also has another, similar meaning in order theory, where ...
s they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951.
John Mackintosh Howie John Mackintosh Howie (23 May 1936 – 26 December 2011) was a Scottish mathematician and prominent semigroup theorist. Biography Howie was educated at Robert Gordon's College, Aberdeen, the University of Aberdeen and Balliol College, Oxfor ...
, 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 A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
, but in this case tell us nothing useful, because groups always have divisibility. Instead of working directly with a semigroup ''S'', it is convenient to define Green's relations over the
monoid 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. Monoid ...
''S''1. (''S''1 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 ''principal left ideal'' generated by ''a'': S^1 a = \. This is the same as \ \cup \, which is Sa \cup \. * The ''principal right ideal'' generated by ''a'': a S^1 = \, or equivalently aS \cup \. * The ''principal two-sided ideal'' generated by ''a'': S^1 a S^1, or SaS \cup aS \cup Sa \cup \.


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 In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
''S''1 ''a'' = ''S''1 ''b''. * ''a'' ''R'' ''b'' if and only if ''a'' ''S''1 = ''b'' ''S''1. * ''a'' ''J'' ''b'' if and only if ''S''1 ''a'' ''S''1 = ''S''1 ''b'' ''S''1. 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). The ''L''-classes and ''R''-classes can be equivalently understood as the
strongly connected component In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that ...
s of the left and right
Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...
s of ''S''1. Further, the ''L'', ''R'', and ''J'' relations define three
preorder In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cas ...
s ≤''L'', ≤''R'', and ≤''J'', where ''a'' ≤''J'' ''b'' holds for two elements ''a'' and ''b'' of ''S'' if the ideal generated by ''a'' is included in that of ''b'', i.e., ''S''1 ''a'' ''S''1 ⊆ ''S''1 ''b'' ''S''1, and ≤''L'' and ≤''R'' are defined analogously. Green used the lowercase
blackletter Blackletter (sometimes black letter), also known as Gothic script, Gothic minuscule, or Textura, was a script used throughout Western Europe from approximately 1150 until the 17th century. It continued to be commonly used for the Danish, Norwe ...
\mathfrak, \mathfrak and \mathfrak for these relations, and wrote a \equiv b (\mathfrak) for ''a'' ''L'' ''b'' (and likewise for ''R'' and ''J''). Mathematicians today tend to use script letters such as \mathcal instead, and replace Green's
modular arithmetic In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his boo ...
-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 ''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''. 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 \mathcal H-class ''H'' of a semigroup S either (i) H^2 \cap H = \emptyset or (ii) H^2 \subseteq H and ''H'' is a subgroup of ''S''. An important corollary is that the equivalence class ''H''''e'', where ''e'' is an
idempotent Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
, 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 \mathcal H-class can contain more than one idempotent, thus \mathcal H is ''idempotent separating''. In a monoid ''M'', the class ''H''1 is traditionally called the
group of units In algebra, a unit of a ring is an invertible element for the multiplication of the ring. That is, an element of a ring is a unit if there exists in such that vu = uv = 1, where is the multiplicative identity; the element is unique for thi ...
. (Beware that unit does not mean identity in this context, i.e. in general there are non-identity elements in ''H''1. 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 In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite 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, as also in a rational monoid. Furthermore they also coincide in any
epigroup 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 ''x'n'' b ...
. There is also a formulation of ''D'' in terms of equivalence classes, derived directly from the above definition:Lawson (2004) p. 219 : ''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 Preston is a place name, surname and given name that may refer to: Places England *Preston, Lancashire, an urban settlement **The City of Preston, Lancashire, a borough and non-metropolitan district which contains the settlement **County Boro ...
(1961) suggest thinking of this situation in terms of an "egg-box":Lawson (2004) p. 220 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 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 ...
, 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''4 contains four ''D''-classes, within which the ''H''-classes have 1, 2, 6, and 24 elements respectively. Recent advances in the
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
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 ''T''3 consists of all functions from the set to itself; there are 27 of these. Write (''a'' ''b'' ''c'') for the function that sends 1 to ''a'', 2 to ''b'', and 3 to ''c''. Since ''T''3 contains the identity map, (1 2 3), there is no need to adjoin an identity. The egg-box diagram for ''T''3 has three ''D''-classes. They are also ''J''-classes, because these relations coincide for a finite semigroup. In ''T''3, two functions are ''L''-related if and only if they have the same
image An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensio ...
. 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 ; 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''3. There are also six subgroups of order 2, and three of order 1 (as well as subgroups of these subgroups). Six elements of ''T''3 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
semiring In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse. The term rig is also used occasionally—this originated as a joke, suggesting that rigs ar ...
s (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
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
s 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? 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 : ''x'' ''L'' ''y'' if and only if Λ ''x'' = Λ ''y'' : ''x'' ''R'' ''y'' 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 ''S''1, 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

* Schutzenberger group


References

* C. E. Clark and J. H. Carruth (1980) ''Generalized Green's theories'',
Semigroup Forum Semigroup Forum (print , electronic ) is a mathematics research journal published by Springer. The journal serves as a platform for the speedy and efficient transmission of information on current research in semigroup theory. Coverage in the jou ...
20(2);  95–127. * A. H. Clifford and G. B. Preston (1961) ''The Algebraic Theory of Semigroups'', volume 1, (1967) volume 2,
American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meeting ...
, Green's relations are introduced in Chapter 2 of the first volume. * J. A. Green (July 1951) "On the structure of semigroups",
Annals of Mathematics The ''Annals of Mathematics'' is a mathematical journal published every two months by Princeton University and the Institute for Advanced Study. History The journal was established as ''The Analyst'' in 1874 and with Joel E. Hendricks as th ...
(second series) 54(1): 163–172. * * John M. Howie (1976) ''An introduction to Semigroup Theory'',
Academic Press Academic Press (AP) is an academic book publisher founded in 1941. It was acquired by Harcourt, Brace & World in 1969. Reed Elsevier bought Harcourt in 2000, and Academic Press is now an imprint of Elsevier. Academic Press publishes refer ...
. An updated version is available as ''Fundamentals of Semigroup Theory'',
Oxford University Press Oxford University Press (OUP) is the university press of the University of Oxford. It is the largest university press in the world, and its printing history dates back to the 1480s. Having been officially granted the legal right to print book ...
, 1995. . * John M. Howie (2002) "Semigroups, Past, Present and Future", ''Proceedings of the International Conference on Algebra and its Applications'', Chulalongkorn University, Thailand * * Petraq Petro (2002) ''Green's relations and minimal quasi-ideals in rings'',
Communications in Algebra ''Communications in Algebra'' is a monthly peer-reviewed scientific journal covering algebra, including commutative algebra, ring theory, module theory, non-associative algebra (including Lie algebras and Jordan algebras), group theory, and al ...
30(10): 4677–4686. * S. Satoh, K. Yama, and M. Tokizawa (1994) "Semigroups of order 8",
Semigroup Forum Semigroup Forum (print , electronic ) is a mathematics research journal published by Springer. The journal serves as a platform for the speedy and efficient transmission of information on current research in semigroup theory. Coverage in the jou ...
49: 7–29. * {{DEFAULTSORT:Green's Relations Semigroup theory