0

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

Community
  • 1
NisaiVloot
  • 1,292
  • 7
  • 11
  • 3
    I think this question might be more suitable for mathoverflow... – Joshua Grochow Mar 24 '14 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... – NisaiVloot Mar 24 '14 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. – Super8 Mar 25 '14 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. – Super8 Mar 25 '14 at 23:02

1 Answers1

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.

NisaiVloot
  • 1,292
  • 7
  • 11
  • 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. http://compsemi.wordpress.com/2013/09/10/the-art-of-semigroup-theory/). I haven't read it though so consider it as 'cheap advice' (?) – NisaiVloot Apr 13 '14 at 21:00
  • 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 ? – Suresh Venkat Apr 13 '14 at 21:11
  • 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. – NisaiVloot Apr 13 '14 at 21:14