Cancellative semigroup

In mathematics, a cancellative semigroup (also called a cancellation semigroup) is a semigroup having the cancellation property.^[1] In intuitive terms, the cancellation property asserts that from an equality of the form a·b = a·c, where · is a binary operation, one can cancel the element a and deduce the equality b = c. In this case the element being cancelled out is appearing as the left factors of a·b and a·c and hence it is a case of the left cancellation property. The right cancellation property can be defined analogously. Prototypical examples of cancellative semigroups are the positive integers under addition or multiplication. Cancellative semigroups are considered to be very close to being groups because cancellability is one of the necessary conditions for a semigroup to be embeddable in a group. Moreover, every finite cancellative semigroup is a group. One of the main problems associated with the study of cancellative semigroups is to determine the necessary and sufficient conditions for embedding a cancellative semigroup in a group.

The origins of the study of cancellative semigroups can be traced to the first substantial paper on semigroups, (Suschkewitsch 1928).^[2]

Formal definitions

Let S be a semigroup. An element a in S is left cancellative (or, is left cancellable, or, has the left cancellation property) if ab = ac implies b = c for all b and c in S. If every element in S is left cancellative, then S is called a left cancellative semigroup.

Let S be a semigroup. An element a in S is right cancellative (or, is right cancellable, or, has the right cancellation property) if ba = ca implies b = c for all b and c in S. If every element in S is right cancellative, then S is called a right cancellative semigroup.

Let S be a semigroup. If every element in S is both left cancellative and right cancellative, then S is called a cancellative semigroup.

Alternative definitions

It is possible to restate the characteristic property of a cancellative element in terms of a property held by the corresponding left multiplication L_a : S → S and right multiplication R_a : S → S maps defined by L_a(b) = ab and R_a(b) = ba: an element a in S is left cancellative if and only if L_a is injective, an element a is right cancellative if and only if R_a is injective.

Examples

Every group is a cancellative semigroup.
The set of positive integers under addition is a cancellative semigroup.
The set of nonnegative integers under addition is a cancellative monoid.
The set of positive integers under multiplication is a cancellative monoid.
A left zero semigroup is right cancellative but not left cancellative, unless it is trivial.
A right zero semigroup is left cancellative but not right cancellative, unless it is trivial.
A null semigroup with more than one element is neither left cancellative nor right cancellative. In such a semigroup there is no element that is either left cancellative or right cancellative.
Let S be the semigroup of real square matrices of order n under matrix multiplication. Let a be any element in S. If a is nonsingular then a is both left cancellative and right cancellative. If a is singular then a is neither left cancellative nor right cancellative.

Finite cancellative semigroups

It is an elementary result in group theory that a finite cancellative semigroup is a group. Let S be a finite cancellative semigroup.

Cancellativity and finiteness taken together imply that Sa = aS = S for all a in S. So given an element a in S, there is an element e_a, depending on a, in S such that ae_a = a. Cancellativity now further implies that this e_a is independent of a and that xe_a = e_ax = x for all x in S. Thus e_a is the identity element of S, which may from now on be denoted by e.
Using the property Sa = S one now sees that there is b in S such that ba = e. Cancellativity can be invoked to show that ab = e also, thereby establishing that every element a in S has an inverse in S. Thus S must necessarily be a group.

Furthermore, every cancellative epigroup is also a group.^[3]

Embeddability in groups

A commutative semigroup can be embedded in a group (i.e., is isomorphic to a subsemigroup of a group) if and only if it is cancellative. The procedure for doing this is similar to that of embedding an integral domain in a field (Clifford & Preston 1961, p. 34) – it is called the Grothendieck group construction, and is the universal mapping from a commutative semigroup to abelian groups that is an embedding if the semigroup is cancellative.

For the embeddability of noncommutative semigroups in groups, cancellativity is obviously a necessary condition. However, it is not sufficient: there are (noncommutative and infinite) cancellative semigroups that cannot be embedded in a group.^[4] To obtain a sufficient (but not necessary) condition, it may be observed that the proof of the result that a finite cancellative semigroup S is a group critically depended on the fact that Sa = S for all a in S. The paper (Dubreil 1941) generalized this idea and introduced the concept of a right reversible semigroup. A semigroup S is said to be right reversible if any two principal ideals of S intersect, that is, Sa ∩ Sb ≠ Ø for all a and b in S. The sufficient condition for the embeddability of semigroups in groups can now be stated as follows: (Ore's Theorem) Any right reversible cancellative semigroup can be embedded in a group, (Clifford & Preston 1961, p. 35).

The first set of necessary and sufficient conditions for the embeddability of a semigroup in a group were given in (Malcev 1939).^[5] Though theoretically important, the conditions are countably infinite in number and no finite subset will suffice, as shown in (Malcev 1940).^[6] A different (but also countably infinite) set of necessary and sufficient conditions were given in (Lambek 1951), where it was shown that a semigroup can be embedded in a group if and only if it is cancellative and satisfies a so-called "polyhedral condition". The two embedding theorems by Malcev and Lambek were compared in (Bush 1963) and later revisited and generalized by (Johnstone 2008), who also explained the close relationship between the semigroup embeddability problem and the more general problem of embedding a category into a groupoid.

Notes

^ (Clifford & Preston 1967, p. 3)
^ G. B. Preston (1990). "Personal reminiscences of the early history of semigroups". Archived from the original on 2009-01-09. Retrieved 2009-05-12.
^ Peter M. Higgins (1992). Techniques of semigroup theory. Oxford University Press. p. 12. ISBN 978-0-19-853577-5.
^ A. Malcev, On the Immersion of an Algebraic Ring into a Field, Mathematische Annalen 1937, Volume 113, Issue 1, pp 686-691
^ Paul M. Cohn (1981), Universal Algebra, Springer, pp. 268–269, ISBN 90-277-1254-9
^ John Rhodes (April 1970), "Book Review of 'The Algebraic Theory of Semigroups Vol I & II' by A H Clifford & G B Preston", Bulletin of the AMS, American Mathematical Society. [1] (Accessed on 11 May 2009)

References

Bush, George C. (1963), "The embedding theorems of Malcev and Lambek", Canadian Journal of Mathematics, 15: 49–58, doi:10.4153/CJM-1963-006-x
Clifford, Alfred Hoblitzelle; Preston, Gordon Bamford (1961), The algebraic theory of semigroups. Vol. I, Mathematical Surveys, No. 7, Providence, R.I.: American Mathematical Society, ISBN 978-0-8218-0272-4, MR 0132791
Clifford, Alfred Hoblitzelle; Preston, Gordon Bamford (1967), The algebraic theory of semigroups. Vol. II, Mathematical Surveys, No. 7, Providence, R.I.: American Mathematical Society, MR 0218472
Dubreil, Paul (1941), "Contribution à la théorie des demi-groupes", Mém. Acad. Sci. Inst. France (2), 63 (3): 52, MR 0016424
Johnstone, Peter (2008), "On embedding categories into groupoids", Mathematical Proceedings of the Cambridge Philosophical Society, 145 (2): 273–294, doi:10.1017/S0305004108001345
Lambek, J. (1951), "The immersibility of a semigroup into a group", Canadian Journal of Mathematics, 3: 34–43, doi:10.4153/CJM-1951-005-8
Malcev, A. I. (1939), "Über die Einbettung von assoziativen Systemen in Gruppen", Rec. Math. (Mat. Sbornik), Nouvelle Série, 6: 331–336, MR 0002152
Malcev, A. I. (1940), "Über die Einbettung von assoziativen Systemen in Gruppen. II", Rec. Math. (Mat. Sbornik), Nouvelle Série, 8: 251–264, MR 0002895
Preston, Gordon Bamford (1991), "Personal reminiscences of the early history of semigroups", Monash Conference on Semigroup Theory (Melbourne, 1990), World Sci. Publ., River Edge, NJ, pp. 16–30, MR 1232669, archived from the original on 2009-01-09, retrieved 2009-05-12
Suschkewitsch, Anton (1928), "Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit", Mathematische Annalen, 99 (1): 30–50, doi:10.1007/BF01459084, hdl:10338.dmlcz/100078, ISSN 0025-5831, MR 1512437

[1] (Clifford & Preston 1967, p. 3)

[2] G. B. Preston (1990). "Personal reminiscences of the early history of semigroups". Archived from the original on 2009-01-09. Retrieved 2009-05-12.

[3] Peter M. Higgins (1992). Techniques of semigroup theory. Oxford University Press. p. 12. ISBN 978-0-19-853577-5.

[4] A. Malcev, On the Immersion of an Algebraic Ring into a Field, Mathematische Annalen 1937, Volume 113, Issue 1, pp 686-691

[5] Paul M. Cohn (1981), Universal Algebra, Springer, pp. 268–269, ISBN 90-277-1254-9

[6] John Rhodes (April 1970), "Book Review of 'The Algebraic Theory of Semigroups Vol I & II' by A H Clifford & G B Preston", Bulletin of the AMS, American Mathematical Society. [1] (Accessed on 11 May 2009)

[1]

[2]

[3]

[4]

[5]

[6]