Associative implies generalized associative

Statement

Let $S$ be a set and $*$ be a binary operation on $S$. Suppose that $*$ is an associative binary operation; in other words:

$a*(b*c)=(a*b)*c\ \forall \ a,b,c\in S$

Then, for any positive integer $n$, every possible parenthesization of the expression:

$a_{1}*a_{2}*\dots *a_{n}$

is equivalent.

Proof

The technique of proof here is a strong form of induction: we assume the result is true for every $m<n$, and we prove it for $n$. Note that the cases $n=1,2$ are tautological. For the case $n=3$, there are precisely two possible parenthesizations, and associativity tells us that they are both equal.

Thus, assume $n>3$, and that the result holds for all $m<n$. We will show that any way of parenthesization of:

$a_{1}*a_{2}*\dots *a_{n}$

is equal to the left-associated expression:

$((\dots (a_{1}*a_{2})*a_{3})*\dots )*a_{n})$

Let's prove this. For any method of parenthesization, there is an outermost multiplication, and in terms of this outermost multiplication, we can view the parenthesization as:

$A*B$

where $A=a_{1}*\dots *a_{m}$ and $B=a_{m+1}*\dots *a_{n}$, both parenthesized in some unknown way, with $0<m<n$. Applying the induction assumption, $A$ equals the left-associated expression for $a_{1}*a_{2}*\dots *a_{m}$ and $B$ equals the left-associated expression for $a_{m+1}*a_{m+2}*\dots *a_{n}$.

Now, in the case that $B$ is a single letter (i.e., $m=n-1$), we are already done: $A*B$ equals the left-associated expression. If not, we can write $A*B$ as:

$A*(C*a_{n})$

where $C$ is the left-associated expression for $a_{m+1}*\dots *a_{n-1}$. Applying associativity, we get that the original expression equals:

$(A*C)*a_{n}$

which is precisely the left-associated expression for $a_{1}*a_{2}*\dots *a_{n}$.

References

• Abstract Algebra by David S. Dummit and Richard M. Foote, 10-digit ISBN 0471433349, 13-digit ISBN 978-0471433347, ^{More info}, Page 18-19, Section 1.1, Proposition 1 (statement on page 18, proof on page 19)