In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the notion of cancellativity (or ''cancellability'') is a generalization of the notion of
invertibility.
An element ''a'' in a
magma
Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma (sometimes colloquially but incorrectly referred to as ''lava'') is found beneath the surface of the Earth, and evidence of magmatism has also ...
has the left cancellation property (or is left-cancellative) if for all ''b'' and ''c'' in ''M'', always implies that .
An element ''a'' in a magma has the right cancellation property (or is right-cancellative) if for all ''b'' and ''c'' in ''M'', always implies that .
An element ''a'' in a magma has the two-sided cancellation property (or is cancellative) if it is both left- and right-cancellative.
A magma is left-cancellative if all ''a'' in the magma are left cancellative, and similar definitions apply for the right cancellative or two-sided cancellative properties.
In 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 (just notation, not necessarily th ...
, a left-invertible element is left-cancellative, and analogously for right and two-sided. If ''a''
−1 is the left inverse of ''a'', then implies , which implies by associativity.
For example, every
quasigroup
In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure that resembles a group in the sense that " division" is always possible. Quasigroups differ from groups mainly in that the associative and identity element pro ...
, and thus 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 iden ...
, is cancellative.
Interpretation
To say that an element
in a magma is left-cancellative, is to say that the function 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 of its codomain; that is, implies (equivalently by contraposition, impl ...
where is also an element of . That the function ''g'' is injective implies that given some equality of the form , where the only unknown is ''x'', there is only one possible value of ''x'' satisfying the equality. More precisely, we are able to define some function ''f'', the inverse of ''g'', such that for all ''x,'' . Put another way, for all ''x'' and ''y'' in ''M'', if , then .
Similarly, to say that the element ''a'' is right-cancellative, is to say that the function is injective and that for all ''x'' and ''y'' in ''M'', if , then .
Examples of cancellative monoids and semigroups
The positive (equally non-negative) integers form a cancellative
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 (just notation, not necessarily th ...
under addition. The non-negative integers form a cancellative
monoid
In abstract algebra, 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 .
Monoids are semigroups with identity ...
under addition. Each of these is an example of a cancellative magma that is not a quasigroup.
Any free semigroup or monoid obeys the cancellative law, and in general, any semigroup or monoid that embeds into a group (as the above examples clearly do) will obey the cancellative law.
In a different vein, (a subsemigroup of) the multiplicative semigroup of elements of a
ring
(The) Ring(s) may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
Arts, entertainment, and media Film and TV
* ''The Ring'' (franchise), a ...
that are not zero divisors (which is just the set of all nonzero elements if the ring in question is a
domain, like the integers) has the cancellation property. This remains valid even if the ring in question is noncommutative and/or nonunital.
Non-cancellative algebraic structures
Although the cancellation law holds for addition, subtraction, multiplication and division of
real and
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the for ...
s (with the single exception of multiplication by
zero
0 (zero) is a number representing an empty quantity. Adding (or subtracting) 0 to any number leaves that number unchanged; in mathematical terminology, 0 is the additive identity of the integers, rational numbers, real numbers, and compl ...
and division of zero by another number), there are a number of algebraic structures where the cancellation law is not valid.
The
cross product
In mathematics, the cross product or vector product (occasionally directed area product, to emphasize its geometric significance) is a binary operation on two vectors in a three-dimensional oriented Euclidean vector space (named here E), and ...
of two vectors does not obey the cancellation law. If , then it does not follow that even if (take for example)
Matrix multiplication
In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix (mathematics), matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the n ...
also does not necessarily obey the cancellation law. If and , then one must show that matrix A is ''invertible'' (i.e. has ) before one can conclude that . If , then B might not equal C, because the
matrix
Matrix (: matrices or matrixes) or MATRIX may refer to:
Science and mathematics
* Matrix (mathematics), a rectangular array of numbers, symbols or expressions
* Matrix (logic), part of a formula in prenex normal form
* Matrix (biology), the m ...
equation will not have a unique solution for a non-invertible matrix A.
Also note that if and and the matrix A is ''invertible'' (i.e. has ), it is not necessarily true that . Cancellation works only for and (provided that matrix A is ''invertible'') and not for and .
See also
*
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 group homomorp ...
*
Invertible element
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that ...
*
Cancellative semigroup
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'', ...
*
Integral domain
In mathematics, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural setting for studying divisibilit ...
References
{{DEFAULTSORT:Cancellation Property
Non-associative algebra
Properties of binary operations
Algebraic properties of elements
fr:Loi de composition interne#Réguliers et dérivés