Semigroup where the sum of any two elements is one of the two elements

Question

Is there a name for a semigroup where the sum of any two elements is one of the two elements?

Let $S = (G, +)$ be a semigroup. I want to add the additional structure that $\forall g \in G, \forall h \in G$, $g + h$ is either $g$ or $h$. This means, of course, that $g + g = g$.

An example of this is $\min$ on integers (without $-\infty$ as the identity), and I'm approaching this from the context of range minimum queries (which can be done in $O(n), O(1)$ time) compared to general range semigroup queries (which can be done in $O(n), \Theta(\alpha(n))$ time).

Thanks!

Answer 1

Examples include the right zero semigroups, which satisfy the identity $xy = x$, and the left zero semigroups, which satisfy the identity $yx = x$.

In fact, your semigroups are chains of right or left zero semigroups.

Theorem. Let $S$ be a semigroup such that, for all $x, y \in S$, $xy \in \{ x, y \}$. Then there is a totally ordered set $(I, \leqslant)$ and for each $i \in I$ a semigroup $S_i$ such that:

1. for each $i \in I$, $S_i$ is either a right or a left zero semigroup,
2. $S$ is the disjoint union of the $S_i$,
3. If $s\in S_i$ and $t\in S_j$, the product on $S$ is given by $st = \begin{cases} s & \text{if $i < j$ or $i = j$ and $S_i$ is a right zero semigroup}\\ t & \text{if $j < i$ or $i = j$ and $S_i$ is a left zero semigroup} \end{cases}$

Proof. I let you verify that these conditions define a semigroup. For the rest of the proof, you need to know about Green's relations. First of all, since for all $x, y \in S$, $xy \in \{ x, y \}$, the relation $\leqslant_\mathcal{J}$ is a total order. Let $(S_i)_{i \in I}$ be the set of all $\mathcal{J}$-classes of $S$. Then (2) holds. Moreover, $I$ is totally ordered by the relation $\leqslant$ defined by $i \leqslant j$ if and only if $S_i \leqslant_\mathcal{J} S_j$. Since $S$ is idempotent, each $\mathcal{J}$-class $S_i$ is a subsemigroup of $S$. Moreover, since for all $x, y \in S$, $xy \in \{ x, y \}$, by Green's lemma, $S_i$ is necessarily either a right or a left zero semigroup, which proves (1). Condition (3) is now clear: if $s\in S_i$ and $t\in S_j$ with $i < j$, then since $st \leqslant_\mathcal{J} s <_\mathcal{J} t$ and $st \in \{s, t\}$, one has $st = s$.