Cancellation property

In mathematics, the notion of cancellative is a generalization of the notion of invertible.

This article is about the extension of 'invertibility' in abstract algebra. For cancellation of terms in an equation or in elementary algebra, see cancelling out.

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

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.[1] That the function g is injective implies that given some equality of the form a * x = b, 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 f(g(x)) = f(a ∗ x) = x. Put another way, for all x and y in M, if a * x = a * y, then x = y.[2]

Examples of cancellative monoids and semigroups

The positive (equally non-negative) integers form a cancellative semigroup 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.

In a different vein, (a subsemigroup of) the multiplicative semigroup of elements of a ring 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. Note that 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 numbers (with the single exception of multiplication by zero and division of zero by another number), there are a number of algebraic structures 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 ≠ 0, 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.

Also note that if AB = CA and A ≠ 0 and the matrix A is invertible (i.e. has det(A) ≠ 0), it is not necessarily true that B = C. Cancellation works only for AB = AC and BA = CA (provided that matrix A is invertible) and not for AB = CA and BA = AC.

gollark: I would probably just go for automatically generated machine-readable changelogs of some form.
gollark: *Currently* I can't do half of those because there's no actual versioning mechanism, and no way to compile stuff because it is all run straight off pastebin.
gollark: Having version control would probably make some potatOS things I've wanted possible, such as verified boot where potatOS ensures that the currently installed stuff matches a checksum, compressed updates, and updates which work if I change a non-core file (the updater logic is very weird).
gollark: And I think cloud catcher.
gollark: Monaco is the one VSCode uses.

See also

References
  1. Warner, Seth (1965). Modern Algebra Volume I. Englewood Cliffs, NJ: Prentice-Hall, Inc. p. 50.
  2. Warner, Seth (1965). Modern Algebra Volume I. Englewood Cliffs, NJ: Prentice-Hall, Inc. p. 48.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.