Cancellation property
Encyclopedia
In mathematics
, the notion of cancellative is a generalization of the notion of invertible.
An element a in a magma
(M,*) has the left cancellation property (or is left-cancellative) if for all b and c in M, a * b = a * c always implies b = c.
An element a in a magma (M,*) has the right cancellation property (or is right-cancellative) if for all b and c in M, b * a = c * a always implies b = c.
An element a in a magma (M,*) has the two-sided cancellation property (or is cancellative) if it is both left- and right-cancellative.
A magma (M,*) has the left cancellation property (or 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.
A left-invertible element is left-cancellative, and analogously for right and two-sided.
For example, every quasigroup
, and thus every group
, is cancellative.
but as it is a set endomorphism
it is a set section
, i.e. there is a set epimorphism
f such f(g(x)) = f(a *x ) = x for all x, so f is a retraction
. Moreover, we can be "constructive" with f taking the inverse
in the range
of g and sending the rest precisely to a.
under addition. The non-negative integers form a cancellative monoid
under addition.
In fact any free semigroup or monoid obeys the cancellative law, and in general any semigroup or monoid embedding into a group (as the above examples clearly do) will obey the cancellative law.
and division of zero by another number, the cancellation law holds for addition, subtraction, multiplication and division of real
and complex number
s, there are a number of algebras where the cancellation law is not valid.
The cross product
of two vectors does not obey the cancellation law. If a×b = a×c, then it does not follow that b=c even if a≠0.
Matrix multiplication
also does not necessarily obey the cancellation law.
If AB=AC and A≠O, then one must show that matrix A is invertible (i.e. has det
(A)≠0) before one can conclude that B=C. If det(A)=0, then B might not equal C, because the matrix
equation AX=B will not have a unique solution for a non-invertible matrix A.
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...
, the notion of cancellative is a generalization of the notion of invertible.
An element a in a magma
Magma (algebra)
In abstract algebra, a magma is a basic kind of algebraic structure. Specifically, a magma consists of a set M equipped with a single binary operation M \times M \rightarrow M....
(M,*) has the left cancellation property (or is left-cancellative) if for all b and c in M, a * b = a * c always implies b = c.
An element a in a magma (M,*) has the right cancellation property (or is right-cancellative) if for all b and c in M, b * a = c * a always implies b = c.
An element a in a magma (M,*) has the two-sided cancellation property (or is cancellative) if it is both left- and right-cancellative.
A magma (M,*) has the left cancellation property (or 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.
A left-invertible element is left-cancellative, and analogously for right and two-sided.
For example, every quasigroup
Quasigroup
In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that "division" is always possible...
, and thus every 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...
, is cancellative.
Interpretation
To say that an element a in a magma (M,*) is left-cancellative, is to say that the function g: x a * x is injective, so a set monomorphismMonomorphism
In the context of abstract algebra or universal algebra, a monomorphism is an injective homomorphism. A monomorphism from X to Y is often denoted with the notation X \hookrightarrow Y....
but as it is a set endomorphism
Endomorphism
In mathematics, an endomorphism is a morphism from a mathematical object to itself. For example, an endomorphism of a vector space V is a linear map ƒ: V → V, and an endomorphism of a group G is a group homomorphism ƒ: G → G. In general, we can talk about...
it is a set section
Section (category theory)
In category theory, a branch of mathematics, a section is a right inverse of a morphism. Dually, a retraction is a left inverse...
, i.e. there is a set epimorphism
Epimorphism
In category theory, an epimorphism is a morphism f : X → Y which is right-cancellative in the sense that, for all morphisms ,...
f such f(g(x)) = f(a *x ) = x for all x, so f is a retraction
Retraction
A retraction is a public statement, by the author of an earlier statement, that withdraws, cancels, refutes, diametrically reverses the original statement or ceases and desists from publishing the original statement...
. Moreover, we can be "constructive" with f taking the inverse
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...
in the range
Range (mathematics)
In mathematics, the range of a function refers to either the codomain or the image of the function, depending upon usage. This ambiguity is illustrated by the function f that maps real numbers to real numbers with f = x^2. Some books say that range of this function is its codomain, the set of all...
of g and sending the rest precisely to a.
Examples of cancellative monoids and semigroups
The positive (equally non-negative) integers form a cancellative semigroupSemigroup
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...
under addition. The non-negative integers form a cancellative monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
under addition.
In fact any free semigroup or monoid obeys the cancellative law, and in general any semigroup or monoid embedding into a group (as the above examples clearly do) will obey the cancellative law.
Non-cancellative algebras
Although, with the single exception of multiplication by zero0 (number)
0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...
and division of zero by another number, the cancellation law holds for addition, subtraction, multiplication and division of real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
and complex number
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
s, there are a number of algebras where the cancellation law is not valid.
The cross product
Cross product
In mathematics, the cross product, vector product, or Gibbs vector product is a binary operation on two vectors in three-dimensional space. It results in a vector which is perpendicular to both of the vectors being multiplied and normal to the plane containing them...
of two vectors does not obey the cancellation law. If a×b = a×c, then it does not follow that b=c even if a≠0.
Matrix multiplication
Matrix multiplication
In 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...
also does not necessarily obey the cancellation law.
If AB=AC and A≠O, then one must show that matrix A is invertible (i.e. has det
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
(A)≠0) before one can conclude that B=C. If det(A)=0, then B might not equal C, because the matrix
Matrix (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...
equation AX=B will not have a unique solution for a non-invertible matrix A.
See also
- Grothendieck groupGrothendieck groupIn mathematics, the Grothendieck group construction in abstract algebra constructs an abelian group from a commutative monoid in the best possible way...
- Invertible element
- Cancellative semigroupCancellative semigroupIn mathematics, a cancellative 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...