# Extending semigroup theory?

In an earlier question I proposed a definition of associativity for ternary relations generalizing the usual notion for composition laws. I'm still not sure whether this definition makes sense, but if so this leads to some interesting algebraic questions. In particular, what parts of "semigroup theory" can be extended to that setting, if any?

Consider such a relation $\cal{R}$ over $X$. Similar to semigroup theory, we can give the following definitions:

• a set $S \subseteq X$ is a "substructure" if $a,b \in S$ and $\cal{R}(a,b,c)$ holds imply that $c \in S$;
• a set $L \subseteq X$ is a "left ideal" if $a \in L, b \in X$ and $\cal{R}(a,b,c)$ holds imply that $c \in L$;
• a set $R \subseteq X$ is a "right ideal" if $a \in X, b \in R$ and $\cal{R}(a,b,c)$ holds imply that $c \in R$;
• given a substructure $S$, we can define an order relation $\leq_S$ such that for any $a,a' \in X$, $a \leq_S a'$ iff for every $b \in S,c \in X$, $\cal{R}(a,b,c)$ implies $\cal{R}(a',b,c)$. We can also define an equivalence relation $\equiv_S$ as $\leq_S \cap \geq_S$.

This leads to some natural questions: (i) what are the conditions on $S$ such that $\cal{R} / \equiv_S$ behaves as a substructure? (ii) how do chains of ideals behave with respect to inclusion? (iii) are there some possible generalizations of the isomorphism theorems? (iv) are there some connections with automata and possible extensions of Krohn-Rhodes theory?

This is probably pie in the sky though, as I don't even have any concrete example of such a structure...

• I think this question might be more suitable for mathoverflow... Commented Mar 24, 2014 at 20:25
• You may be right, but personnally I'm sticking to a "small battlefield" to avoid contaminating other people with the CS disease. Not sure about other computer scientists though... Commented Mar 24, 2014 at 21:05
• Given a poset $P$, you can define a relation $R_P$ by $R_P(x,y,z) \Leftrightarrow z \leq_P x \wedge z \leq_P y$. This satisfies your definition of associativity, and in this case your three notions coincide as they all correspond to the lower-sets of $P$. Note that $R_P$ can be interpreted as a composition law only if $P$ is a semilattice, which suggests that the proposed extension yields greater generality. Commented Mar 25, 2014 at 22:31
• The following construction is even more general. Consider a poset $P = (X,\leq_P)$ with an adjonction operator, i.e. a mapping $F : X \rightarrow X$ s.t. (1) $x \leq_P F^2(x)$ and (2) $F(x) \leq_P y$ iff $x \leq_P F(y)$. Defining $R_P(x,y,z) \Leftrightarrow z \leq_P x \wedge F(z) \leq_P F(y)$ yields an associative relation. In particular, when $P$ is $\Sigma^*$, $\leq_P$ is the prefix relation and $F$ is the mirror operation, you essentially recover the free monoid. Commented Mar 25, 2014 at 23:02