Monoids. Disprove that $(a\cdot x=a) \Rightarrow (x=e)$

Question

Wikipedia states that "...not every monoid sits inside a group. For instance, it is perfectly possible to have a monoid in which two elements a and b exist such that $a\cdot b = a$ holds even though $b$ is not the identity element." (link: http://en.wikipedia.org/wiki/Monoid#Properties)

I would like to see a proof or example for this. So, to sum up:

Suppose we have a monoid $\langle S\rangle$, with a binary operation $\langle \cdot\rangle $ and the identity element $\langle e\rangle$. Disprove that $$(a\cdot x=a) \Rightarrow (x=e)$$

It can't be disproved in general, since it is sometimes true. For example, choosing $x=e$ makes the claim true. — hmakholm left over Monica, Mar 07 '13 at 18:22

score 5 · Answer 1 · answered Mar 07 '13 at 18:24

5

An example of a monoid that doesn't allow cancellation is the two-element monoid $(\{0,1\},{\times},1)$. Here $0\times 0=0$ yet $0$ is not the identity.

answered Mar 07 '13 at 18:24

hmakholm left over Monica

286,031

score 4 · Accepted Answer · answered Mar 07 '13 at 18:23

4

Take the monoid $\mathbb R_+$ with operation $\rm Max$ and unit element $0$. Then $ \rm Max (2,1) = 2$ but $1$ is not equal to $0$.

answered Mar 07 '13 at 18:23

Damien L

6,649

If the unit element is 0, shouldn't you expand the monoid to nonnegative reals? (because currently the unit element is not in the monoid) – Ralph Mar 07 '13 at 18:40
1

It is $\mathbb{R}_{\geq 0}$. – Martin Brandenburg Mar 07 '13 at 18:51

score 4 · Answer 3 · answered Mar 07 '13 at 18:35

4

The universal example is the quotient of the free monoid on two generators $a$ and $b$ modulo the relation $ab = a$.

It's easy to see that every element of this monoid can be written (uniquely!) in the form $b^j a^k$ for nonnegative integers $j$ and $k$, and multiplication is given by

$$(b^j a^k)(b^m a^n) = \begin{cases} b^j a^{k+n} & k > 0 \\ b^{j+m} a^n & k = 0 \end{cases}$$

We can see that $b$ is not the identity, because $b \cdot 1 = b$, not $1$.

answered Mar 07 '13 at 18:35

This is, by the way, isomorphic to the ordinals less than $\omega^2$ under ordinal addition. – hmakholm left over Monica Mar 07 '13 at 20:44
@Henning: What a fascinating insight, thank you! Am I right that $a=1$ and $b=\omega$ under this isomorphism, and that we have to reverse the addition? – Martin Brandenburg Mar 08 '13 at 00:06
@MartinBrandenburg: For $ab=a$ we need to have $a=\omega$ and $b=1$, and, as you say, reverse the addition. – hmakholm left over Monica Mar 08 '13 at 00:40

score 4 · Answer 4 · answered Mar 07 '13 at 18:50

4

Probably the easiest example is the monoid of self-maps of a set (with at least two elements). If $a$ is a constant map, then $a \circ x = a$ for all $x$.

answered Mar 07 '13 at 18:50

Martin Brandenburg

163,620

Aleksei Averchenko · Answer 5 · 2013-03-07T18:54:48.123

Let $A$ be a non-trivial ring. For any $x \in A$ we have $0 \cdot x = (1 - 1) \cdot x = x - x = 0$, yet since $A$ is non-trivial, in general $x \neq 0$. Thus, the multiplicative monoid of $A$ satisfies your property.

Consider now a category of monoids with zero, that is an element $0$ that satisfies $0 \cdot x = x \cdot 0 = 0$. The forgetful functor from this category to the category of monoids has a left adjoint (source: Bergman's companion to Lang's Algebra), so you can make any monoid have the property you're looking for by adjoining a zero, much like you can make any semigroup a monoid by adjoining a unit.

Cameron Buie · Answer 6 · 2013-03-11T04:07:20.230

Consider the monoid of $2\times 2$ matrices with real entries under matrix multiplication, and let $$A=X=\left(\begin{array}{cc}1 & 0\\0 & 0\end{array}\right).$$ Then $AX=A,$ but $X\neq I.$ More generally, in any monoid with idempotent non-identity elements, cancellativity must fail to hold.

You cannot disprove the claim for a general monoid, since (for example) a monoid may be a group. All you need to do is demonstrate a counterexample, such as the above.

Monoids. Disprove that $(a\cdot x=a) \Rightarrow (x=e)$

6 Answers6