In mathematics, a cancellative semigroup (also called a cancellation semigroup) is 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'' ...

having the

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 (or is left-cancellative) if for all ''b'' and ''c'' in ''M'', always implies that . A ...

. In intuitive terms, the cancellation property asserts that from an

equality Equality may refer to: Society * Political equality, in which all members of a society are of equal standing ** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elite ...

of the form ''a''·''b'' = ''a''·''c'', where · is a

binary operation In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary op ...

, 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 integer In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...

s under

addition Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or '' sum'' of ...

multiplication Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being addi ...

. 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 implies 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 implies 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 and right multiplication maps defined by and : an element ''a'' in ''S'' is left cancellative

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

''L''_''a'' is

injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...

, an element ''a'' is right cancellative if and only if ''R''_''a'' is injective.

Examples

#Every

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

is a cancellative semigroup. #The set of

s under addition is a cancellative semigroup. #The set of nonnegative integers under addition is a cancellative

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. Monoids a ...

. #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 In mathematics, a null semigroup (also called a zero semigroup) is a semigroup with an absorbing element, called zero, in which the product of any two elements is zero. If every element of a semigroup is a left zero then the semigroup is called a l ...

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 Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...

square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length ad ...

matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...

of order ''n'' under

matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the ...

. Let ''a'' be any element in ''S''. If ''a'' is

nonsingular In linear algebra, an -by- square matrix is called invertible (also nonsingular or nondegenerate), if there exists an -by- square matrix such that :\mathbf = \mathbf = \mathbf_n \ where denotes the -by- identity matrix and the multiplicati ...

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

that a finite cancellative semigroup is a group. Let ''S'' be a finite cancellative semigroup. Cancellativity and finiteness taken together imply that 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 . Cancellativity now further implies that this ''e''_''a'' is independent of ''a'' and that 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 one now sees that there is ''b'' in ''S'' such that . 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 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'' be ...

is also a group.

Embeddability in groups

A commutative semigroup can be embedded in a group (i.e., is

isomorphic In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...

to a

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

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 – it is called the

Grothendieck group In mathematics, the Grothendieck group, or group of differences, of a commutative monoid is a certain abelian group. This abelian group is constructed from in the most universal way, in the sense that any abelian group containing a homomorphic ...

construction, and is the universal mapping from a commutative semigroup to

abelian group In mathematics, 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 the order in which they are written. That is, the group operation is comm ...

s 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. 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 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's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with sufficiently many edges must contain a Hamilt ...

) 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 .
(Accessed on 11 May 2009) A different (but also countably infinite) set of necessary and sufficient conditions were given in , 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 later compared in .

Notes

References

* * * * * * * * * {{Citation , last1=Suschkewitsch , first1=Anton , authorlink = Anton Sushkevich, title=Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit , doi=10.1007/BF01459084 , mr=1512437 , year=1928 , journal=

Mathematische Annalen ''Mathematische Annalen'' (abbreviated as ''Math. Ann.'' or, formerly, ''Math. Annal.'') is a German mathematical research journal founded in 1868 by Alfred Clebsch and Carl Neumann. Subsequent managing editors were Felix Klein, David Hilbert, ...

, issn=0025-5831 , volume=99 , issue=1 , pages=30–50, hdl=10338.dmlcz/100078 , hdl-access=free Algebraic structures Semigroup theory