# How does one actually show from associativity that one can drop parentheses?

I've always heard this reasoning, and it makes obvious sense, but how do you actually show it for some arbitrary product? Would it be something like this?

$$(a(b(cd)))e=((ab)(cd))e=(((ab)c)d)e=abcde?$$

Do you just say that the grouping of the parentheses now corresponds to just multiplying straight through? Thanks.

-
Well, you can say that, but you should prove it if you're unsure. The idea is generally to define a "preferred" parenthesization (e.g. the last one you've got there) and show that associativity implies that all parenthesizations are equivalent to that one. –  Qiaochu Yuan Feb 11 '11 at 20:28
One might want to note this only necessarily works for structures only where we have a single "product" or "binary operation" at work, and no other binary operations. Even if we have two associative products "@" and "^" at work, you'll still need parentheses (in infix notation). Define "@" as "pseudo-modular" over "^" if (x@(y^z))=((x@y)^z) and correspondingly "^" as "pseudo-modular" over "@" if (x^(y@z))=((x^y)@z). If you have more than one associative product, it at least looks like you'll also need that each product is "pseudo-modular" over any other one to drop all parentheses (in infix). –  Doug Spoonwood Aug 26 '11 at 3:33

You can prove by induction on the number of factors that all such products are equal. We show that if you have $a_1,\ldots,a_n$, then any way to place the parenthesis will yield the same result as $a_1(a_2(\cdots(a_{n-1}a_n)\cdots))$.

If the number of factors is $1$ or $2$, then the result is immediate. If the number of factors is $3$, then it follows precisely by associativity: $(a_1a_2)a_3 = a_1(a_2a_3)$.

Assume the result holds for any $k$, $1\leq k\lt n$, and you have some product of $n$ elements $a_1,\ldots,a_n$, in order, with parentheses placed in some arbitrary (but valid) manner. Then there exists $k$, $1\leq k\lt n$, such that the product is of the form $$w_1(a_1,\ldots,a_k)\cdot w_2(a_{k+1},\ldots,a_n)$$ where $w_1(a_1,\ldots,a_k)$ is just an expression involving the product of $a_1,\ldots,a_k$ with parentheses placed in some fashion, and similarly with $w_2$. (We are just looking at the "last" product to be done; e.g., if you have $((a_1a_2)a_3)(a_4a_5)$, we would have $k=3$, $w_1(a_1,a_2,a_3) = (a_1a_2)a_3$, and $w_2(a_4,a_5) = a_4a_5$; if you have $a_1((a_2a_3)(a_4a_5))$, then $k=1$, $w_1(a_1) = a_1$, and $w_2(a_2,a_3,a_4,a_5) = (a_2a_3)(a_4a_5)$; etc).

By induction we can write $$w_1(a_1,\ldots,a_k) = a_1(a_2(\cdots(a_{k-1}a_k)\cdots))$$ so \begin{align*} w_1(a_1,\ldots,a_k)w_2(a_{k+1},\ldots,a_n) &= \Bigl(a_1\bigl(a_2(\cdots(a_{k-1}a_k)\cdots)\Bigr)\cdot w_2(a_{k+1},\ldots,a_n)\\ &= a_1\cdot\Bigl(a_2(\cdots(a_{k-1}a_k)\cdots)w_2(a_{k+1},\ldots,a_n)\Bigr) \\ &= a_1\cdot\Bigl( a_2(a_3(\cdots(a_{n-1}a_n)\cdots)\Bigr) \end{align*} where the last equality follows from the induction hypothesis applied to a product with $n-1$ factors, and the immediately preceding equality by simple associativity of three factors, applied to $a_1$, $a_2(\cdots(a_{k-1}a_k)\cdots)$, and $w_2(a_{k+1},\ldots,a_n)$. (Note: If $k=1$, then you can skip directly from the first line to the last line without having to invoke associativity; the argument still holds.)

Thus, any expression of a product of $a_1,\ldots,a_n$, in that order, with parentheses place in an arbitrary but valid manner, is equal to $$a_1(a_2(\cdots(a_{n-1}a_n)\cdots)),$$ This completes the induction and the proof.

Since all ways of associating a product of $n$ factors, $a_1,\ldots,a_n$ yield results that are equal to one another, we may freely write any such product simply as $a_1\cdots a_n$ to represent their common value.

-
Arturo is a canonical example of an enterprising soul! :) –  Mariano Suárez-Alvarez Feb 11 '11 at 20:48
@Mariano: You are affirming the consequent! Your statement was basically "If $X$ is enterprising, then $X$ might post a proof"; I posted a proof, it does not follow I am enterprising...(-: (Besides, I was in the middle of it when your post came through...) –  Arturo Magidin Feb 11 '11 at 20:53
I knew of your enterprisingness (?) long before this question came along! :) –  Mariano Suárez-Alvarez Feb 11 '11 at 20:54
Thank you Arturo. A wonderful answer, much obliged. –  user6927 Feb 11 '11 at 22:23
And yet, a downvote... Go figure. –  Arturo Magidin Mar 25 '12 at 19:05

That «one can drop the parentheses» really means that «no matter how you put the parentheses in, the result will be the same».

To prove such a statement, what one usually does is pick one specific way of putting in parentheses, and shows that any other way gives the same result as the one we picked. This is done by induction in the number of factors.

Some enterprising soul might post a complete proof...

-
For reference, the proof is sketched in "Alegbra" by Dummit and Foote page 19. –  Klaus Feb 11 '11 at 20:39

HINT $\:$ It's very easy: keep pushing ')'s rightward using the rewrite rule $\rm\ (xy)\:z\ \to\ x(yz)\:.$ This process terminates with the right-associated normal form where all ')'s are at the right end, namely $\rm\ a(b(c(d(\cdots)))\:,\$ written $\rm\ a\ b\ c\ \cdots$ (without ambiguity - all possible bracketings agree).

Below is a proof sketch, by induction on the length $\rm\:\ell(Z)$

$\rm \ell(Z) = 1\!:\ \ \ Z = a\$ is in normal form

$\rm \ell(Z) > 1\!:\ \ \ Z = XY\$ where $\rm\:\ell(X),\ell(Y)< \ell(Z)$

$\rm\ \ \ell(X) = 1\!:\ \ \ XY = aY = a(b(c(\cdots)))\$ by induction applied to $\rm Y$

$\rm\ \ \ell(X) > 1\!:\ \ \ XY = (a \bar X)Y = a(\bar X Y) = a(b(c(\cdots)))\$ by induction applied to $\rm X$ and $\rm\bar XY$

-

We argue by induction on the number $n$ of factors, assuming, as we may, $n\ge4$.

By induction hypothesis, we know that, for $k < n$, any product of the factors $b_1,\dots,b_k$ taken in this order can be written unambiguously as $b_1\cdots b_k$.

Then a product of any given sequence $a_1,\dots,a_n$ is necessarily of the form $$c_k:=(a_1\cdots a_k)(a_{k+1}\cdots a_n)$$ for some $k=2,\dots,n-1$, and we only need to check $$c_p=c_q\quad\forall\quad1 < p < q < n,$$ which we do as follows: $$\begin{matrix} &(a_1\cdots a_p)&(a_{p+1}\cdots a_q& a_{q+1}\cdots a_n)\\ \\ =&(a_1\cdots a_p)&((a_{p+1}\cdots a_q)&(a_{q+1}\cdots a_n))\\ \\ =&((a_1\cdots a_p)&(a_{p+1}\cdots a_q))&(a_{q+1}\cdots a_n)\\ \\ =&(a_1\cdots a_p&a_{p+1}\cdots a_q)&(a_{q+1}\cdots a_n). \end{matrix}$$

-

A more formal pedantic version of part a very small part of Mariano Suárez-Alvarez' answer.

Associativity is a property of multiplication, which is a binary operation. More precisely, multiplication is a map $m:R \times R \to R, (a,b) \mapsto m(a,b)=ab$.
The associative law says that (ab)c = a(bc). Using m, that is the same as m(m(a,b),c) = m(a,m(b,c)). (Note that m takes exactly two elements of $R$ as "input"). A consequence of the associative law is that there is no ambiguity in writing abc, since «no matter how you put the parentheses in, the result will be the same».

Edit:As Arturo writes in a comment below: "associativity is not a property of multiplication per se ([...] addition [is] associative [as is] composition of functions) but rather, a property that a binary operation may or may not have." Of course, Arturo's proof in his answer works for any associative binary operation.

-
Hmm. A more formal version would have been an actual proof that there is ambiguity. –  Mariano Suárez-Alvarez Feb 11 '11 at 20:40
Fair enough. I've edited accordingly. –  Bart Van Steirteghem Feb 11 '11 at 20:54
@Bart: As long as you are editing, associativity is not a property of multiplication per se (isn't addition associative also? composition of functions?) but rather, a property that a binary operation may or may not have. –  Arturo Magidin Feb 11 '11 at 20:58
Of course you are right. I was actually debating whether to include something like that, but wasn't sure how helpful it would be. I just wrote about multiplication because the OP mentions "product" and "multiplying." –  Bart Van Steirteghem Feb 11 '11 at 21:55
@Mariano: In your comment, did you mean something like $3-(5-2) \neq (3-5)-2$, therefore $3-5-2$ is ambiguous without the convention that we go from left to right, i.e. the convention that $3-5-2 = (3-5)-2$ ? –  Bart Van Steirteghem Feb 11 '11 at 22:08