5
$\begingroup$

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.

  • 0
    There are counterexamples for matrix algebras, so *a fortiori* for monoids.2012-10-19

3 Answers 3

20

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.

  • 0
    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$.2012-10-18
8

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.

  • 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](http://en.wikipedia.org/wiki/Stet)]2012-10-18
4

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