Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Green's relations
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
In [[mathematics]], '''Green's relations''' are five [[equivalence relation]]s that characterise the elements of a [[semigroup]] in terms of the [[principal ideal]]s 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 [[Group (mathematics)|groups]], 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]] ''S''<sup>1</sup>. (''S''<sup>1</sup> 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'': <math>S^1 a = \{sa \mid s \in S^1\}</math>. This is the same as <math>\{sa \mid s \in S\} \cup \{a\}</math>, which is <math>Sa \cup \{a\}</math>. * The ''principal right ideal'' generated by ''a'': <math>a S^1 = \{as \mid s \in S^1\}</math>, or equivalently <math>aS \cup \{a\}</math>. * The ''principal two-sided ideal'' generated by ''a'': <math>S^1 a S^1</math>, or <math>SaS \cup aS \cup Sa \cup \{a\}</math>. ==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''<sup>1</sup> ''a'' = ''S''<sup>1</sup> ''b''. * ''a'' ''R'' ''b'' if and only if ''a'' ''S''<sup>1</sup> = ''b'' ''S''<sup>1</sup>. * ''a'' ''J'' ''b'' if and only if ''S''<sup>1</sup> ''a'' ''S''<sup>1</sup> = ''S''<sup>1</sup> ''b'' ''S''<sup>1</sup>. 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''<sub>''a''</sub> (and similarly for the other relations). The ''L''-classes and ''R''-classes can be equivalently understood as the [[strongly connected component]]s of the left and right [[Cayley graph]]s of ''S''<sup>1</sup>.<ref>{{cite web |title=How can you use Green's relations to learn about a monoid? |date=November 19, 2015 |work=[[Stack Exchange]] |url=https://math.stackexchange.com/q/1536699 }}</ref> Further, the ''L'', ''R'', and ''J'' relations define three [[preorder]]s β€<sub>''L''</sub>, β€<sub>''R''</sub>, and β€<sub>''J''</sub>, where ''a'' β€<sub>''J''</sub> ''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''<sup>1</sup> ''a'' ''S''<sup>1</sup> β ''S''<sup>1</sup> ''b'' ''S''<sup>1</sup>, and β€<sub>''L''</sub> and β€<sub>''R''</sub> are defined analogously.<ref>{{cite arXiv |eprint=1102.2707 |last1=Johnson |first1=Marianne |title=Green's J-order and the rank of tropical matrices |last2=Kambites |first2=Mark |class=math.RA |year=2011 }}</ref> Green used the lowercase [[blackletter]] <math>\mathfrak{l}</math>, <math>\mathfrak{r}</math> and <math>\mathfrak{f}</math> for these relations, and wrote <math>a \equiv b (\mathfrak{l})</math> for ''a'' ''L'' ''b'' (and likewise for ''R'' and ''J'').<ref>{{cite journal | last=Green | first= James A. | title=On the structure of semigroups | zbl=0043.25601 | journal=[[Annals of Mathematics]] |series=2 | volume=54 | pages=163β172 | year=1951 | issue= 1 | doi=10.2307/1969317 | jstor= 1969317 | hdl= 10338.dmlcz/100067}}</ref> Mathematicians today tend to use script letters such as <math>\mathcal{R}</math> 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 ''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''<sub>''a''</sub> is the intersection of ''L''<sub>''a''</sub> and ''R''<sub>''a''</sub>. 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 <math>\mathcal H</math>-class ''H'' of a semigroup S either (i) <math>H^2 \cap H = \emptyset</math> or (ii) <math>H^2 \subseteq H</math> and ''H'' is a subgroup of ''S''. An important corollary is that the equivalence class ''H''<sub>''e''</sub>, 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 <math>\mathcal H</math>-class can contain more than one idempotent, thus <math>\mathcal H</math> is ''idempotent separating''. In a [[monoid]] ''M'', the class ''H''<sub>1</sub> is traditionally called the '''[[group of units]]'''.<ref>Howie, p. 171</ref> (Beware that unit does not mean identity in this context, i.e. in general there are non-identity elements in ''H''<sub>1</sub>. The "unit" terminology [[Unit (ring theory)|comes from ring theory]].) For example, in the [[transformation monoid]] on ''n'' elements, ''T''<sub>''n''</sub>, the group of units is the [[symmetric group]] ''S''<sub>''n''</sub>. 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 [[Lattice (order)|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;<ref>Gomes, Pin & Silva (2002), [{{Google books|plainurl=y|id=IL58mAsfXOgC|page=94|text=in a finite semigroup}} p. 94]</ref> this is also the case in a [[rational monoid]]<ref>{{cite journal | title=Easy multiplications I. The realm of Kleene's theorem | first=Jacques | last=Sakarovitch | journal=Information and Computation | volume=74| number=3 | date=September 1987 | pages=173β197 | doi=10.1016/0890-5401(87)90020-4 | zbl=0642.20043 | doi-access= }} </ref> or in an [[epigroup]].<ref>{{cite book|author=Peter M. Higgins|title=Techniques of semigroup theory|year=1992|publisher=Oxford University Press|isbn=978-0-19-853577-5|page=28}}</ref> There is also a formulation of ''D'' in terms of equivalence classes, derived directly from the above definition:<ref name=Law219>Lawson (2004) p. 219</ref> : ''a'' ''D'' ''b'' if and only if the intersection of ''R''<sub>''a''</sub> and ''L''<sub>''b''</sub> 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. [[A. H. Clifford|Clifford]] and [[Gordon Preston|Preston]] (1961) suggest thinking of this situation in terms of an "egg-box":<ref name=Law220>Lawson (2004) p. 220</ref> 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''<sub>4</sub> 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 [[equivalent (semigroup theory)|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 [[List of small groups|five groups of order 8]].) ==Example== The full transformation semigroup ''T''<sub>3</sub> consists of all functions from the set {1, 2, 3} 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''<sub>3</sub> contains the identity map, (1 2 3), there is no need to adjoin an identity. The egg-box diagram for ''T''<sub>3</sub> has three ''D''-classes. They are also ''J''-classes, because these relations coincide for a finite semigroup. {| cellspacing="0" cellpadding="0" | {| border="1" cellpadding="6" cellspacing="0" | '''(1 1 1)''' || '''(2 2 2)''' || '''(3 3 3)''' |} |- | | {| border="1" cellpadding="6" cellspacing="0" | '''(1 2 2)''',<br/>(2 1 1) || '''(1 3 3)''',<br/>(3 1 1) || (2 3 3),<br/>(3 2 2) |- | (2 1 2),<br/>'''(1 2 1)''' || (3 1 3),<br/>(1 3 1) || '''(3 2 3)''',<br/>(2 3 2) |- | (2 2 1),<br/>(1 1 2) || (3 3 1),<br/>'''(1 1 3)''' || (3 3 2),<br/>'''(2 2 3)''' |} |- | | | {| border="1" cellpadding="6" cellspacing="0" | '''(1 2 3)''', (2 3 1),<br/>(3 1 2), (1 3 2),<br/>(3 2 1), (2 1 3) |} |} In ''T''<sub>3</sub>, two functions are ''R''-related if and only if they have the same [[Image (mathematics)|image]]. Such functions appear in the same row of the table above. Likewise, the functions ''f'' and ''g'' are ''L''-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 column. 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''<sub>3</sub>. There are also six subgroups of order 2, and three of order 1 (as well as subgroups of these subgroups). Six elements of ''T''<sub>3</sub> 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]]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 ideal]]s, 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]]s between ''L''- and ''R''- classes. If ''x'' ''R'' ''y'', then it is always possible to find bijections between ''L''<sub>''x''</sub> and ''L''<sub>''y''</sub> 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'' ''Ο''<sub>1</sub> = ''y'' and ''y'' ''Ο''<sub>2</sub> = ''x'', then the restrictions : ''ρ''<sub>1</sub> : Λ ''x'' β Λ ''y'' : ''ρ''<sub>2</sub> : Λ ''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''<sup>1</sup>, 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== {{Reflist}} * C. E. Clark and J. H. Carruth (1980) ''Generalized Green's theories'', [[Semigroup Forum]] 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]], 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]] (second series) 54(1): 163–172. * {{cite journal | last=Grillet | first=Mireille P. | title=Green's relations in a semiring | zbl=0227.16029 | journal=Port. Math. | volume=29 | pages=181β195 | year=1970 | url=https://eudml.org/doc/115127 }} * [[John M. Howie]] (1976) ''An introduction to Semigroup Theory'', [[Academic Press]] {{ISBN|0-12-356950-8}}. An updated version is available as ''Fundamentals of Semigroup Theory'', [[Oxford University Press]], 1995. {{ISBN|0-19-851194-9}}. * John M. Howie (2002) "Semigroups, Past, Present and Future", ''Proceedings of the International Conference on Algebra and its Applications'', [[Chulalongkorn University]], Thailand * {{cite book | last=Lawson | first=Mark V. | title=Finite automata | publisher=Chapman and Hall/CRC | year=2004 | isbn=1-58488-255-7 | zbl=1086.68074 }} * Petraq Petro (2002) ''Green's relations and minimal quasi-ideals in rings'', [[Communications in Algebra]] 30(10): 4677–4686. * S. Satoh, K. Yama, and M. Tokizawa (1994) "Semigroups of order 8", [[Semigroup Forum]] 49: 7–29. * {{cite book |last1=Gomes |first1=G.M.S. |last2=Pin |first2=J.E. |last3=Silva |first3=J.E. |title=Semigroups, algorithms, automata, and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001 |year=2002 |publisher=[[World Scientific]] |isbn=978-981-238-099-9 | zbl=1005.00031 }} {{DEFAULTSORT:Green's Relations}} [[Category:Semigroup theory]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Cite arXiv
(
edit
)
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:Cite web
(
edit
)
Template:Google books
(
edit
)
Template:ISBN
(
edit
)
Template:Reflist
(
edit
)