Skip to main content
3 of 3
Added the equivalence relation for functions, to answer a comment.

Not exactly what you are looking for, but there may be some connection. The following situation is frequent: a monoid $M$, an equivalence relation $R$ on $M$ which is compatible with the monoid operator, and $M/R$ is an idempotent monoid. Examples:

  • Polynomials with a positive highest-degree coefficient, as an additive cancellative monoid:
    $P \mathbin R Q$ is $\operatorname{deg}(P) = \operatorname{deg}(Q)$.
  • Functions $\mathbb{R}^+ \rightarrow \mathbb{R}^+$ as an additive cancellative monoid, with Big O equivalence relation on some point $a$ (where $a \in \mathbb{R}$ or $a=+\infty$ or $a=-\infty$):
    $f \mathbin R g$ is $f(x) = \mathcal{O}(g(x))$ as $x \to a$.
  • Sets with infinite cardinal, operation is union:
    $A \mathbin R B$ is $\operatorname{card}(A) = \operatorname{card}(B)$.
  • Geometric or topological sets, with union:
    $\mathbin R$ is having the same dimension (for some dimensions, e.g. Hausdorff).

All these examples share the same pattern: the resulting idempotent monoid is a totally ordered set, and the operator is $\max$. One could build more complex examples with the same ingredients, e.g. multiple-variable polynomials, with $\operatorname{deg}$ being the set of highest-degree terms, but that looks artificial.

One possible question: given an idempotent monoid, can it always be considered as the quotient of a cancellative monoid?