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

$\endgroup$
1
  • $\begingroup$ There are counterexamples for matrix algebras, so a fortiori for monoids. $\endgroup$ Oct 19 '12 at 8:10
21
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ In functional analysis the left- and right-shift operator. $\endgroup$
    – vesszabo
    Oct 18 '12 at 7:15
  • $\begingroup$ Great! Nice proof. Thanks for that (and thanks to the other answerers). $\endgroup$ Oct 18 '12 at 7:25
  • $\begingroup$ 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}$. $\endgroup$ Oct 18 '12 at 7:39
  • $\begingroup$ 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$. $\endgroup$
    – rschwieb
    Oct 18 '12 at 12:32
8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Do you have a proof of this? $\endgroup$
    – user22805
    Oct 18 '12 at 7:13
  • 1
    $\begingroup$ 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] $\endgroup$ Oct 18 '12 at 7:13
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.