# Natural pre-order for (non-commutative) monoids

Any commutative monoid is endowed with its algebraic preordering $\leq$, defined by $x\leq y$ if there exists $z$ such that $x + z = y$.

I was wondering why we need commutativity here. It seems to me that for non-commutative monoids, we also have this algebraic preordering. To be precise, suppose $M$ is a generally non-commutative monoid and we define $x\leq y$ if there exists $z$ such that $xz= y$. We have

1. (Reflexivity) For any $x$, $x\leq x$ since $xe=x$, where $e$ is the identity.
2. (Transitivity) Assume $x\leq y$ and $y\leq z$. Then there exists $a$ and $b$ such that $xa=y$ and $yb=z$. Thus $x(ab)=z$. Therefore we deduce that $x\leq z$.

I guess we do not need commutativity here. However, in almost all related books that I read, when they talk about this natural pre-ordering, they assume commutative monoids. Thank you for your help :-)

• where we write $xz\leq y$ do you mean $xz=y$? – YTS Oct 8 '17 at 17:35
• @YTS, sorry that is a typo. Thanks! I corrected it :-) – Cech Cohomology Oct 8 '17 at 17:36
• I think you are right. Maybe it is just a matter of importance: Is there any important non commutative monoid where you required that preorder? – YTS Oct 8 '17 at 17:38
• Thanks @YTS. I am reading some textbooks about monoids but was quite confused that they all assumed commutative monoids when they talked about the natural preorder and so did the Wikipedia page. Then I was afraid there should be some important point I neglected. – Cech Cohomology Oct 8 '17 at 17:41
• @YTS: “Is there any important non commutative monoid where you required that preorder?” It is right in front of us. List concatenation is a monoid and is not commutative. The natural preorder obtained from list concatenation is the prefix relation: $x\leq y$ means “$x$ is a prefix of $y$”. This partial order is useful in computer science. The natural preorder obtained from the dual monoid is the suffix relation. The supremum of prefix and suffix preorders is the infix (sublist) relation. – beroal Oct 13 '17 at 8:52

## 1 Answer

The relation you define is the opposite of the Green's preorder $\leqslant_\mathcal{R}$ on a (not necessarily commutative) monoid $M$, defined as follows: $$x \mathrel{\leqslant_\mathcal{R}} y \quad \text{if and only if} \quad xM \subseteq yM \quad \text{if and only if} \quad \text{there exists z \in M such that x= yz}$$ This definition is quite standard, see for instance [1, p. 288] or [2, Chap. 2]. See also this related answer.

[1] S. Eilenberg, Automata, languages, and machines. Vol. B. With two chapters by Bret Tilson. Pure and Applied Mathematics, Vol. 59. Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1976.

[2] P. A. Grillet, Semigroups, An Introduction to the Structure Theory, Marcel Dekker, Inc., New York, 1995.