Green's Relations

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:

The ''principal left ideal'' generated by ''a'': $S^1 a = \{sa \mid s \in S^1\}$ . This is the same as $\{sa \mid s \in S\} \cup \{a\}$ , which is $Sa \cup \{a\}$ .

The ''principal right ideal'' generated by ''a'': $a S^1 = \{as \mid s \in S^1\}$ , or equivalently $aS \cup \{a\}$ .

The ''principal two-sided ideal'' generated by ''a'': $S^1 a S^1$ , or $SaS \cup aS \cup Sa \cup \{a\}$ .

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''¹.

_''a''

Green used the lowercase Blackletter

\mathfrak{l}

\mathfrak{r}

and

\mathfrak{f}

for these relations, and wrote

a \equiv b (\mathfrak{l})

for ''a'' ''L'' ''b'' (and likewise for ''R'' and ''J''). Mathematicians today tend to use script letters such as

\mathcal{R}

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

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''.

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''.)

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''.)

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 .)

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.

	{ Border	"1" cellpadding="6" cellspacing="0"
	{ Border	"1" cellpadding="6" cellspacing="0"

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

Green's Relations