Cancellative semigroup
Encyclopedia
In mathematics
, a cancellative semigroup (also called a cancellation semigroup) is a semigroup
having the cancellation property
. 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 canceled out is appearing as the left factors of a · b and a · c and hence it is a case of left cancellation property. The right cancellation property can be defined in an analogous way. Prototypical
examples of cancellative semigroups are the group
s and the semigroup
of 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, .
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.
that a finite cancellatve 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 ea, depending on a, in S such that aea = a. Cancellativity now further implies that this ea is independent of a and that xea = eax = x for all x in S. Thus ea 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.
, the universal mapping from a commutative semigroup to abelian group
s that is an embedding if the semigroup is cancellative.
For the embeddability of noncommutative semigroups in groups, cancellativity is obviously a necessary condition. To obtain a sufficient 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 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, .
The first set of necessary and sufficient conditions for the embeddability of a semigroup in a group were given in . Though theoretically important, the conditions are countably infinite in number and no finite subset will suffice, as shown in .
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a cancellative semigroup (also called a cancellation semigroup) is a semigroup
Semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
having the cancellation property
Cancellation property
In mathematics, the notion of cancellative is a generalization of the notion of invertible.An element a in a magma has the left cancellation property if for all b and c in M, a * b = a * c always implies b = c.An element a in a magma has the right cancellation...
. In intuitive terms, the cancellation property asserts that from an equality of the form a · b = a · c, where · is a binary operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
, one can cancel the element a and deduce the equality b = c. In this case the element being canceled out is appearing as the left factors of a · b and a · c and hence it is a case of left cancellation property. The right cancellation property can be defined in an analogous way. Prototypical
Prototype
A prototype is an early sample or model built to test a concept or process or to act as a thing to be replicated or learned from.The word prototype derives from the Greek πρωτότυπον , "primitive form", neutral of πρωτότυπος , "original, primitive", from πρῶτος , "first" and τύπος ,...
examples of cancellative semigroups are the group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
s and the semigroup
Semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
of positive integers under addition
Addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
or multiplication
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
. 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, .
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.
Examples
- Every groupGroup (mathematics)In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
is a cancellative semigroup. - The set of natural numberNatural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s under addition is a cancellative semigroup. - The set of nonnegative integers under addition is a cancellative monoid.
- The set of natural numberNatural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s under multiplication is a cancellative monoid. - A left zero semigroup is right cancellative but not left cancellative.
- A right zero semigroup is left cancellative but not right cancellative.
- A null semigroupNull semigroupIn mathematics, a null semigroup is a semigroup with an absorbing element, called zero, in which the product of any two elements is zero...
with more than one element is neither left cancellative nor right cancellative. In fact in such a semigroup there is no element which is either left cancellable or right cancellable. - Let S be the semigroup of real square matricesMatrix (mathematics)In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
of order n under matrix multiplicationMatrix multiplicationIn mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...
. Let a be any element in S. If a is nonsingular then a is both left cancellable and right cancellable. If a is singular then a is neither left cancellable nor right cancellable.
Finite cancellative semigroups
It is an elementary result in group theoryGroup theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
that a finite cancellatve 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 ea, depending on a, in S such that aea = a. Cancellativity now further implies that this ea is independent of a and that xea = eax = x for all x in S. Thus ea 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.
Embeddability in groups
A commutative semigroup can be embedded in 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, . See also Grothendieck groupGrothendieck group
In mathematics, the Grothendieck group construction in abstract algebra constructs an abelian group from a commutative monoid in the best possible way...
, the universal mapping from a commutative semigroup to abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
s that is an embedding if the semigroup is cancellative.
For the embeddability of noncommutative semigroups in groups, cancellativity is obviously a necessary condition. To obtain a sufficient 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 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
Ore condition
In mathematics, especially in the area of algebra known as ring theory, the Ore condition is a condition introduced by Øystein Ore, in connection with the question of extending beyond commutative rings the construction of a field of fractions, or more generally localization of a ring...
) Any right reversible cancellative semigroup can be embedded in a group, .
The first set of necessary and sufficient conditions for the embeddability of a semigroup in a group were given in . Though theoretically important, the conditions are countably infinite in number and no finite subset will suffice, as shown in .