# In a monoid, does $x \cdot y=e$ imply $y \cdot x=e$?

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.

-
There are counterexamples for matrix algebras, so a fortiori for monoids. –  Martin Brandenburg Oct 19 '12 at 8:10

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.

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

-
Do you have a proof of this? –  user22805 Oct 18 '12 at 7:13
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$.

-