0

When proving the asociativity of some operation denoted by $\bullet$ one first proves that $a\bullet(b\bullet c)=(a\bullet b)\bullet c$ for any $a$, $b$ and $c$.

This automatically implies that $$a_1\bullet a_2\bullet\cdots\bullet a_n$$ is well defined for $a_1, a_2,\dots, a_n$ with $n$ arbitrarily large, but I would like to see a symbollic proof using the fact that all "parenthesifications" are equivalent, for example $$(a\bullet b)\bullet(c\bullet d)=a\bullet(b\bullet(c\bullet d))$$

So, given $a_1,a_2,\dots,a_n$, is there a notation to represent any such combination of parenthesis and $\bullet$s?

With this notation one could prove the equivalence of any two combinations by transforming any one of then by the rule $a\bullet(b\bullet c)=(a\bullet b)\bullet c$ until arriving at the "standard" $$a_1\bullet(a_2\bullet(\cdots(a_{n-1}\bullet a_n)\cdots))$$

A good notation should behave "mecanically" through the rule

Thanks in advance!

augustoperez
  • 3,216
  • 1
    the most natural data structure for representing bracketings is the binary tree, see one of the answers here: https://math.stackexchange.com/questions/709196/definition-of-general-associativity-for-binary-operations – Matthew Towers Oct 26 '23 at 17:36
  • 1
    Maybe one can try induction on the number of variables $n$. – Benjamin Wang Oct 26 '23 at 17:40
  • 1
    The most straightforward proof would utilize induction, but it seems like you're asking instead for something more constructive, e.g. a sequence of steps from any one "parenthesification" to any other, using only the "basic" associativity rule. Is that right? If so I second @MatthewTowers 's link. – Eli Johnson Oct 26 '23 at 17:47
  • @EliJohnson definitely it helps, and I now think I can't get anything better than using de dyck word as the notation, but I was looking for something like tensor notation with indices expressing the location of the $($ and $)$ – augustoperez Oct 26 '23 at 17:53

1 Answers1

2

I have used numbers under the operation to specify the order of evaluation. Thus:

$$(ab)c=a\underset1\bullet b\underset2\bullet c,\qquad a(bc)=a\underset2\bullet b\underset1\bullet c,$$ $$a((bc)d)=a\underset3\bullet b\underset1\bullet c\underset2\bullet d,\qquad a(b(c(de)))=a\underset4\bullet b\underset3\bullet c\underset2\bullet d\underset1\bullet e.$$

However, this means we have two different ways of writing $(ab)(cd)$:

$$a\underset1\bullet b\underset3\bullet c\underset2\bullet d,\qquad a\underset2\bullet b\underset3\bullet c\underset1\bullet d.$$

An application of the operation to $n$ elements $a_1,a_2,\cdots,a_n$ is specified by a permutation of the numbers $1,2,\cdots,n-1$.

Three-term associativity means that any two consecutive (not necessarily adjacent) numbers in the permutation can be swapped. For example,

$$a\underset3\bullet b\underset2\bullet c\underset5\bullet d\underset1\bullet e\underset4\bullet f=(a(bc))((de)f)$$ $$=a\underset3\bullet b\underset2\bullet c\underset4\bullet d\underset1\bullet e\underset5\bullet f=((a(bc))(de))f$$

(let the three terms be $(a(bc))$ and $(de)$ and $(f)$). If there's a larger number between the two consecutive numbers, then they can be swapped without assuming associativity, as in the $(ab)(cd)$ example.

mr_e_man
  • 5,364