How to describe all semigroups $(S, \, \cdot)$ based on a choice operation?

Question

Let $S$ be a non-empty set. We say that a binary operation $f \, \colon S \times S \to S$ is a choice operation if it always returns one of its arguments. In other words, $\forall \, a \in S \, \colon f(a,a)=a$ and $\forall \, a, b \in S, \, a \ne b \, \colon f(a,b) \in \{ a, b \}$.

If $f$ is associative, it defines a semigroup on $S$. We'll use more simple and common to semigroups notation $a \cdot b$ instead of $f(a,b)$ further. Several notable (and, in some sense, exhaustive) examples of such operations are $a \cdot b \equiv \max (a,b)$, $a \cdot b \equiv \min (a,b)$ on some totally ordered set and $a \cdot b \equiv a$ ("leftArg"), $a \cdot b \equiv b$ ("rightArg") on any set. The first two are commutative, while the last two are not.

How to describe all semigroups $(S, \, \cdot)$ based on a choice operation?

It is not hard to prove that such semigroup is commutative if and only if there is a total order on $S$ such that $a \cdot b \equiv \max (a,b)$ (or, alternatively, $a \cdot b \equiv \min (a,b)$ for the reverse order). That's why I've said that $\max (a,b)$ is exhaustive.

What about non-commutative semigroups? My conjecture is that $(S, \, \cdot)$ is a semigroup with a choice operation $\cdot$ if and only if there exist a totally ordered set $(T, \, \leq)$ and two functions $r \, \colon S \to T$ (rank) and $s \, \colon T \to \{\mathcal L, \mathcal R\}$ (side) such that $\cdot$ is a combination of the above max, leftArg and rightArg functions in the following sense:

$$ a \cdot b \equiv \begin{cases} a, & \text{if $r(b) < r(a)$} \\ b, & \text{if $r(a) < r(b)$} \\ a, & \text{if $r(a) = r(b)$ and $s(r(a)) = \mathcal L$} \\ b, & \text{if $r(a) = r(b)$ and $s(r(a)) = \mathcal R$} \end{cases}$$

Is it true?

Answer 1

Introduce strict partial order on $S$: $a < b$ if $ab = ba = b$ (it's transitive: if $a < b$ and $b < c$ then $ac = a(bc) = (ab)c = bc = c$). Say that $a \sim b$ if $a \not < b$ and $b \not < a$ (so $ab \neq ba$ - one of them if $a$ and other is $b$).

$\sim$ is also transitive: assume $a \sim b$ and $b \sim c$. Wlog $ab = a$, $ba = b$.

If $bc = b$, $cb = c$, then $ac = a(bc) = (ab)c = a(bc) = ab = a$ and $ca = (cb)a = c(ba) = cb = c$, so $a \sim c$.

If $bc = c$, $cb = b$, we have $4$ variants for $ac$ and $ca$, and none of them is possible:

1. $ac = ca = c$: $(ca)b = cb = b$, but $c(ab) = ca = c$.
2. $ac = ca = a$: $(bc)a = ca = a$, but $b(ca) = ba = b$.
3. $ac = a$, $ca = c$: $c = bc = b(ac) = ba = b$.
4. $ac = c$, $ca = a$: $(ac)b = cb = b$, but $a(cb) = ab = a$.

So, $\sim$ is transitive. Moreover, on each class of equivalence, $\cdot$ is either left or right choice.

Assume $a \sim b$, $a < c$. Then $b < c$. By transitivity of $\sim$, either $b < c$ or $c < b$. Assume $c < b$. If $ab = a$, then $(ab)c = ac = c$, but $a(bc) = ab = a$ - contradiction; similarly if $ba = a$. Thus $b < c$.

Similarly, if $a < c$, $c \sim d$ then $a < d$.

Together, it means that set of equivalence classes by $\sim$ is totally ordered by $<$. Taking this set of classes as $T$, with $r$ sending each element to its class, gives your representation.