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...

  • 3
    $\begingroup$ I think this question might be more suitable for mathoverflow... $\endgroup$ Mar 24, 2014 at 20:25
  • $\begingroup$ 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... $\endgroup$
    – NisaiVloot
    Mar 24, 2014 at 21:05
  • $\begingroup$ 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. $\endgroup$
    – Super8
    Mar 25, 2014 at 22:31
  • $\begingroup$ 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. $\endgroup$
    – Super8
    Mar 25, 2014 at 23:02

1 Answer 1


The structure you suggest is known as a 'semihypergroup', a notion introduced by F. Marty in 1934. According to Google, some of your questions have already been attacked by a diverse community of mathematicians involving Greeks, Iranians and Thai people. The most challenging question seems point (iv) but I'm unsure about the outcome, though a positive result in that directions would probably have far-reaching consequences -- possibly in relation with Rhodes' interest in the separation of complexity classes.

  • $\begingroup$ By the way, for the artistically minded newbies interested in the subject, I would recommend the book 'The Art of Semigroup Theory' by A.J. Cain (see e.g. compsemi.wordpress.com/2013/09/10/the-art-of-semigroup-theory). I haven't read it though so consider it as 'cheap advice' (?) $\endgroup$
    – NisaiVloot
    Apr 13, 2014 at 21:00
  • $\begingroup$ If the mathematicians mentioned are from Greece, Iran and Thailand, then maybe better to phrase it that way ? otherwise I fail to see how their cultural/ethnic background matters ? $\endgroup$ Apr 13, 2014 at 21:11
  • $\begingroup$ A brief remark: it seems that these 'semihypergroups' are currently the most general formulation of associativity, but there may be further generalizations to discover. I had actually asked a previous question about possible generalizations but I couldn't retrieve the question on the site. Still, there may be an 'Associative Structure Theory' to discover that may unify different approaches such as SG, ML (Moufang Loops) and the like. $\endgroup$
    – NisaiVloot
    Apr 13, 2014 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.