I have a binary operation $\star$ on a set of graphs such that the $\star$ is an associative (so far i have tried) that is for any three graphs $A$, $B$ and $C$ $\implies (A\star B)\star C=A\star(B\star C)$. But when i take four graphs, $A, B, C$ and $D$, then the following inequality holds: $[(A\star B)\star C]\star D\neq A\star[B\star(C\star D)]$. Now, what can be said about such operations? Can i still call the $\star$ associative?

  • 1
    $\begingroup$ an associative binary operation can never do this. $((a \cdot b) \cdot c) \cdot d = (a \cdot b) \cdot (c \cdot d) = a \cdot (b \cdot (c \cdot d))$ $\endgroup$ – Zachary Hunter Jun 2 at 17:22

This is not possible: if a binary operation $\star$ is associative, then it also satisfies $$((A\star B)\star C)\star D= A\star(B\star(C\star D)).$$ Indeed, we have $$((A\star B)\star C)\star D=(A\star B)\star (C\star D)=(A\star (B\star (C\star D))$$ where each step is an application of associativity. So in fact you can use your example where $$((A\star B)\star C)\star D\neq A\star(B\star(C\star D))$$ to find a counterexample to associativity (namely, one of the two steps of the proof above must fail).

More generally, by a similar argument and induction on $n$, you can prove that any two ways to parenthesize an $n$-fold product must be equal (see Let $a_1,a_2,a_3,...,a_n$ be elements of a group $(G,*)$. Show by induction that $a_1*a_2*a_3...*a_n$ always gives the same answer. for instance).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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