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

Answer

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.