13
$\begingroup$

If $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.

$\endgroup$
0

4 Answers 4

11
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ We came up with almost an identical example, within seconds of each other! The internet is a wonderous and stange place. $\endgroup$ Apr 17, 2012 at 2:49
  • $\begingroup$ Yes, indeed it is :-) $\endgroup$ Apr 17, 2012 at 2:50
  • $\begingroup$ Beautiful answer. $\endgroup$
    – 6005
    Nov 9, 2014 at 11:54
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ You surely need to prove that $b\neq c$. This isn't obvious, methinks... $\endgroup$
    – user1729
    Apr 17, 2012 at 15:25
  • $\begingroup$ 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$. $\endgroup$ Apr 17, 2012 at 15:33
  • $\begingroup$ 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... $\endgroup$
    – user1729
    Apr 17, 2012 at 20:48
  • $\begingroup$ 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?) $\endgroup$ Apr 18, 2012 at 0:51
  • $\begingroup$ 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.) $\endgroup$
    – user1729
    Apr 18, 2012 at 9:25
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ No matter/related with the difficulty of the question, this is one of the best answers I've read recently! $\endgroup$ Feb 1, 2015 at 12:28
  • $\begingroup$ @MattAllegro Thanks! $\endgroup$
    – 6005
    Feb 1, 2015 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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