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.

A monoid is a set $S$ together with a binary operation $\cdot:S \times S \rightarrow S$ such that:

  • The binary operation $\cdot$ is associative, that is, $(a\cdot b) \cdot c=a\cdot (b \cdot c)$ for all $a,b,c \in S$.
  • There is an identity element $e \in S$, that is, there exists $e \in S$ such that $e \cdot a=a$ and $a \cdot e=a$ for all $a \in S$.

Question: Suppose, $x,y \in S$ such that $x \cdot y=e$. Does $y \cdot x=e$?

This question was motivated by the question here, where the author attempts to prove a special case of the above in the context of matrix multiplication. It was subsequently proved, but the proofs require the properties of the matrix.

I attempted to use Prover9 to prove the statement. Here's the input:

formulas(assumptions).

% associativity
(x * y) * z = x * (y * z).

% identity element a
x * a = x.
a * x = x.

end_of_list.

formulas(goals).

x * y = a -> y * x = a.

end_of_list.

and it returned sos_empty, which, I guess, implies that no proof of the above statement is possible from the axioms of monoids alone. I ran Mace4 on the same input, and found no counter-examples for monoids of sizes $1,2,\ldots,82$.

A comment by Martin Brandenburg here regarding K-algebras might also apply here. For example, the property might be true for finite monoids, but not all infinite monoids. A counter-example would (obviously) need to be non-commutative.

share|improve this question
    
There are counterexamples for matrix algebras, so a fortiori for monoids. –  Martin Brandenburg Oct 19 '12 at 8:10

3 Answers 3

up vote 16 down vote accepted

Let $M$ be the monoid of all functions from $\mathbb N$ to $\mathbb N$, with function composition as the operation. Let $y(n)=n+1$ for all $n$, while $x(n)=n-1$ for $n\ge 1$, $x(0)=0$. Then $xy$ is the identity function, while $yx$ is not.

As you conjecture, the statement is true for finite monoids. Suppose $xy=e$. If we have a $z$ such that $zx=e$, then $zxy=ey$, so $ze=ey$, so $z=y$. Thus it's enough to show $x$ has a left inverse $z$. To do this, consider the function $f$ from $M$ to $M$ given by $f(a)=ax$. If $ax=bx$, then $axy=bxy$, hence $a=b$. Thus $f$ is injective, and so (since $M$ is finite) $f$ must be surjective, so in particular $e$ is in its image, and we're done.

In short: every monoid $M$ is isomorphic to a set of functions from $M$ to $M$ under composition, and $fg=\mathrm{id} \rightarrow gf=\mathrm{id}$ only holds on finite sets.

share|improve this answer
    
In functional analysis the left- and right-shift operator. –  vesszabo Oct 18 '12 at 7:15
    
Great! Nice proof. Thanks for that (and thanks to the other answerers). –  Douglas S. Stones Oct 18 '12 at 7:25
    
In fact, $x$ has two right inverses (another way to show it is a counterexample using Isaac Solomon's remark). We already have $y$ as constructed in the answer, but also there is $z$ defined by $z(0)=0$ and $z(n)=n+1$ for all other $n\in\Bbb{N}$, and $xz=\text{id}$. –  peoplepower Oct 18 '12 at 7:39
    
This is a nice example because it's also useful for constructing a ring example. If you have a countable dimensional vector space $V$, and you define $f(b_i)=b_{i+1}$ and $g(b_i)=b_{i-1}$ for $i>0$, and $g(b_0)=0$, then the linear transformations of $V$ determined by $f$ and $g$ are such that $gf=1$, but $fg\neq 1$. So even in a monoid as rigid as the monoid of a ring, $ab=1$ need not imply $ba=1$. –  rschwieb Oct 18 '12 at 12:32

If a left inverse and a right inverse exist in a monoid, they are equal. However, the existence of a left inverse need not imply the existence of a right inverse, and vice versa.

share|improve this answer
    
Do you have a proof of this? –  user22805 Oct 18 '12 at 7:13
1  
Great! Prover9 can easily prove the first statement if I add the goal x * y = a & z * x = a -> y = z.. Could you also provide an example of the second claim please? [Stet] –  Douglas S. Stones Oct 18 '12 at 7:13

Let $S$ be the set of maps $\mathbb{C} \rightarrow \mathbb{C}$. Let $f \in S$ be the map defined by $f(x) = x^2$. Since $f$ is surjective, there exists $g \in S$ such that $f\circ g = 1$. Since $f$ is not bijective, $g\circ f \neq 1$.

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.