Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$G$ is a monoid,$e$ is its identity,if $ab=e$ and $ac=e$,

can you give me a counterexample such that $b\neq c$.

if not,please prove $b=c$

thanks a lot.

share|improve this question

4 Answers 4

up vote 8 down vote accepted

Consider the infinite Cartesian product

$$S = \prod_{i=1}^{\infty} \mathbb{Z} $$

The maps $f \colon S \rightarrow S$ form a monoid under composition, with identity being the identity map.

Let $a \colon S \rightarrow S$ be the map

$$ a ((z_1, z_2, z_3 \ldots)) = (z_2, z_3, z_4, \ldots)$$

Let $b$ be the map

$$ b ((z_1, z_2, z_3 \ldots)) = (0, z_1, z_2, z_3 \ldots)$$

and let $c$ be the map

$$ c ((z_1, z_2, z_3 \ldots)) = (1, z_1, z_2, z_3, \ldots)$$

Then $ab = ac = e$, but $b \neq c$.

share|improve this answer
    
We came up with almost an identical example, within seconds of each other! The internet is a wonderous and stange place. –  John Stalfos Apr 17 '12 at 2:49
    
Yes, indeed it is :-) –  Barry Smith Apr 17 '12 at 2:50
    
Beautiful answer. –  Goos Nov 9 at 11:54

Lets look at the endomorphisms of a particular vector space: namely let our vector space $V := \mathbb{R}^\infty$ so an element of $V$ looks like a countable (not necessarily convergent) sequence of real numbers. The set of linear maps $\phi: V \rightarrow V$ form a monoid under composition(prove it!). Let $R: V \rightarrow V$ be the right shift map, namely it takes $R: (x_0, x_1, \dots) \mapsto (0,x_0,x_1, \dots)$. Let $L: V \rightarrow V$ be the left shift map $L: (x_0, x_1, \dots) \mapsto (x_1, x_2, \dots)$, clearly $L \circ R = \textrm{id}_V = e$. Now define $R' : V \rightarrow V$ where $R' : (x_0, x_1, \dots) \mapsto (x_0, x_0, x_1, x_2, \dots)$. We also have $L \circ R' = \textrm{id}_V = e$, but these are different maps.

There are probably simpler examples, but this is pretty explicit so I thought it would be good to see.

share|improve this answer

Yes, there is a simpler example.

Let $G$ be the free monoid over $A =\{a,b,c\}$ satisfying the relations $ab = ac =e$.

Intuitively, $G$ is the set of all finite strings over $A$ that contain neither the subword $ab$ nor $ac$. Or, think of $b$ and $c$ as different but both of which cancel a single trailing $a$ when multiplied on the right.


If you are concerned that we must show $b \neq c$, then do it this way instead. Forget the part about relations and just define $G$ as strings over $A=${a,b,c}, that is: $G \subset A^*$, $G = \{x \in A^*:\text{neither }ab\text{ nor }ac\text{ is a subword of }x\}$ or $G = A^* - A^*abA^* - A^*acA^*$. Multiplication in $G$ is ordinary string catentation, except for two special cases: $xa \cdot by = xy$ and $xa \cdot cy = xy$ for $x, y \in G$. You can easily verify that $G$ with this multiplication is a monoid and meets the criteria, and there is no reason to worry that $b=c$.

In particular, the strings "$b$" and "$c$" are both in the free monoid $A^*$ and nothing in the subtraction of sets removes them, nor do any of the multiplication rules, so they are still in $G$. So therefore the monoid elements $b$ and $c$ in $G$ are distinct.


addendum -- This G is the "simplest" possible in the sense of being universal. That is, for any morphism $f$ and monoid $M$ satisfying the criteria $f(ab)=f(ac)=f(e)=e$, with $f:A^* \rightarrow M$, there is a morphism $g:G \rightarrow M$ with $g(x)=f(x) \text{ for all } x \in A$. $g$ simply acts properly on $A$ and then extends to $A^*$

That cannot be said of Barry's monoid of functions: $S \rightarrow S$ because it has extra structure, namely $ba=ca=e$ and others. So even if you use just the closure of $\{a,b,c,e\}$ under function composition (rather that all functions: $S \rightarrow S$), you'd have extra structure in S versus the free case, which prevents it from acting universal wrt G.

share|improve this answer
    
You surely need to prove that $b\neq c$. This isn't obvious, methinks... –  user1729 Apr 17 '12 at 15:25
    
I know it seems like cheating, but these are strings (that is, elements of the free monoid over $A$) and $b$ and $c$ are distinct strings. So are $bb$, $cc$, $ba$, $ca$ and so on. That's really all there is to it. The free monoid over a finite set works the same way, and all this does is "back off" from the free monoid as little as possible to meet the criteria. You could even add the relation $bb=cc$ and others and it would still work, as long as you don't add $b=c$. –  David Lewis Apr 17 '12 at 15:33
    
I'm not claiming that the monoid is trivial, just that there is something to prove here. For instance, people spent a long time wondering whether given free burnside groups were finite or infinite... –  user1729 Apr 17 '12 at 20:48
    
OK, I guess I see your point -- you want me to prove $ab=ac=e \text{ does not imply }b=c$. But that means proving "$b \neq c \land ab=ac=e$", that is, exhibiting a structure where that holds, which I have now done with the addition ot the answer -- or if you want more, then please show me how. I do think, however, that my original proof is within the bounds of acceptable collapsing of arguments for monoids, but you may disagree. (How do you do a $\Rightarrow$ with a slash through it in LaTeX?) –  David Lewis Apr 18 '12 at 0:51
    
Yeah, what you have added completes it for me. (\nRightarrow, or \not\Rightarrow both work--in general, putting \not before something negates it, \not\in, \not\cong, \not\equiv, etc.) –  user1729 Apr 18 '12 at 9:25

For anyone interested, here are a couple more examples, followed by some special cases for which this property is true.

Examples

  1. Let $T$ be the monoid of functions on $\mathbb{N}$, under composition. Let $b(x) = 2x$, $c(x) = 2x+1$, and $a(x) = \lfloor x / 2 \rfloor$. We have $a(b(x)) = x$ and $a(c(x)) = x$ but $b \ne c$.

  2. Let $X$ be the set of $\mathcal{C}^\infty$ functions on $[0,1]$, and let $L$ be the monoid of linear operators on $X$. (In fact, $L$ is a ring.) Let $A(f) = \frac{df}{dx}$, $B(f) = \int_0^x f(t) \; dt$, and $C(f) = f(0) + \int_0^x f(t) \; dt$. Again $A \circ B = A \circ C = \text{id}$, but $B \ne C$.

Special Cases

  • Suppose $M$ is finite. Then $ab = ac = e$ implies $b = c$.

    Proof. $M$ naturally embeds in the monoid $T$ of functions on $M$ via $a \mapsto f_a$, where $f_a(x) = ax$. (See also.) $T$ is finite. If $ab = ac = e$ then $f_a$ is surjective, hence injective, hence its inverse is unique.

  • Suppose $M$ is commutative. Then $ab = ac = e$ implies $b = c$.

    Proof. $b = abc = c$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.