Tour:Invertible implies cancellative in monoid: Difference between revisions

Latest revision as of 08:44, 4 April 2013

This article adapts material from the main article: invertible implies cancellative in monoid

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Equivalence of definitions of group| UP: Introduction two (beginners)| NEXT: Equivalence of definitions of subgroup
Expected time for this page: 5 minutes
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

WHAT YOU NEED TO DO:
Understand the statement below; try proving it yourself

Understand the proof, and the crucial way in which it relies on associativity

PONDER:

What happens if we remove the assumption of associativity? Can you cook up a magma (set with binary operation) having a neutral element, where an element has a left inverse but is not cancellative?

Statement

In a monoid (a set with an associative binary operation possessing a multiplicative identity element) the following are true:

Any left invertible element (element having a left inverse) is left cancellative.
Any right invertible element (element having a right inverse) is right cancellative.
Any invertible element is cancellative.

Proof

We'll give here the proof for left invertible and left cancellative. An analogous proof works for right invertible and right cancellative.

Given: A monoid $M$ with binary operation $*$ , and identity element (also called neutral element) $e$ . $a \in M$ has a left inverse $b$ (i.e. an element $b * a = e$ )

To prove: $a$ is left-cancellative: whenever $c, d \in M$ are such that $a * c = a * d$ , then $c = d$ .

Proof: We start with:

$a * c = a * d$

Left-multiply both sides by $b$ :

$b * (a * c) = b * (a * d)$

Use associativity:

$(b * a) * c = (b * a) * d$

We now use that $b * a = e$ is the identity element, to conclude that $c = d$ .

This page is part of the Groupprops guided tour for beginners. Make notes of any doubts, confusions or comments you have about this page before proceeding.
PREVIOUS: Equivalence of definitions of group| UP: Introduction two (beginners)| NEXT: Equivalence of definitions of subgroup

@@ Line 1: / Line 1: @@
-{{quotation|In a [[monoid]] (set with associative binary operation and neutral element) any invertible element can be canceled from an equation. In particular, in groups, ''any'' element is cancellative. The proof makes use of associativity in a crucial way.<br>Proceed to [[Guided tour for beginners:Finite group]]}}
+{{derivative of|invertible implies cancellative in monoid}}
-==Statement==
+{{tour-regular|
+target = beginners|
+secnum = two|
+previous = Equivalence of definitions of group|
+next = Equivalence of definitions of subgroup|
+expected time = 5 minutes}}
+{{quotation|'''WHAT YOU NEED TO DO''':
+* Understand the statement below; try proving it yourself
+* Understand the proof, and the crucial way in which it relies on associativity
+'''PONDER''':
+* What happens if we remove the assumption of associativity? Can you cook up a magma (set with binary operation) having a neutral element, where an element has a left inverse but is not cancellative?}}
-In a [[monoid]] (a set with an [[associative binary operation]] possessing a multiplicative identity element) the following are true:
+{{#lst:Invertible implies cancellative in monoid|main}}
+{{tour-regular-bottom|
-* Any [[left invertible element]] (element having a left inverse) is [[left cancellative element|left cancellative]].
+target = beginners|
-* Any [[right invertible element]] (element having a right inverse) is [[right cancellative element|right cancellative]].
+secnum = two|
-* Any [[invertible element]] is [[cancellative element|cancellative]].
+previous = Equivalence of definitions of group|
+next = Equivalence of definitions of subgroup}}
-==Proof==
-We'll give here the proof for left invertible and left cancellative. An analogous proof works for right invertible and right cancellative.
-''Given'': A monoid <math>M</math> with binary operation <math>*</math>, and identity element (also called ''neutral element'') <math>e</math>. <math>a \in M</math> has a left inverse <math>b</math> (i.e. an element <math>b * a = e</math>)
-''To prove'': <math>a</math> is left-cancellative: whenever <math>c,d \in M</math> are such that <math>a * c = a * d</math>, then <math>c =d </math>
-''Proof'': We start with:
-<math>a * c = a * d</math>
-Left-multiply both sides by <math>b</math>:
-<math>b * (a * c) = b * (a * d)</math>
-Use associativity:
-<math>(b * a) * c = (b * a) * d</math>
-We now use that <math>b * a = e</math> is the identity element, to conclude that <math>c = d</math>.