26
$\begingroup$

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.

  • 4
    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.2011-02-11
  • 0
    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).2011-08-26
  • 0
    http://www.proofwiki.org/wiki/General_Associativity_Theorem2012-01-07

6 Answers 6

34

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.

  • 9
    Arturo is a canonical example of an enterprising soul! :)2011-02-11
  • 1
    @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...)2011-02-11
  • 1
    I knew of your enterprisingness (?) long before this question came along! :)2011-02-11
  • 0
    Thank you Arturo. A wonderful answer, much obliged.2011-02-11
  • 2
    And yet, a downvote... Go figure.2012-03-25
  • 0
    We got one each. For my part, I have to say there is much worse company to be in :)2012-03-25
  • 0
    I tried to formulate a proof like this, but failed to spot the last induction applied to the $(n-1)$ elements, which I find rather beautiful. This is a really nice proof.2012-03-25
  • 0
    @Mariano: And here I was just thinking the same thing... I now call today's meeting of the MAS (mutual admiration society) to a close. (-:2012-03-25
9

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$

5

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

  • 1
    For reference, the proof is sketched in "Alegbra" by Dummit and Foote page 19.2011-02-11
3

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} $$

0

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.

  • 1
    Hmm. A *more formal version* would have been an actual proof that there is ambiguity.2011-02-11
  • 0
    Fair enough. I've edited accordingly.2011-02-11
  • 0
    @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.2011-02-11
  • 0
    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."2011-02-11
  • 0
    @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$ ?2011-02-11
  • 0
    @Bart, @Mariano: Hope I'm not speaking out of turn, but I suspect Mariano meant to write "an actual proof that there is *no* ambiguity", as opposed to merely affirming "as a consequence, there is no ambiguity..."2011-02-11
  • 0
    What Arturo said.2011-02-11
  • 0
    @Arturo, @Mariano: I was not claiming to give a full answer (proof) to the OQ. My intent was merely to make somewhat more "formal" Mariano's statement (_That «one can drop the parentheses» really means that «no matter how you put the parentheses in, the result will be the same»_) in the case of three factors, by pointing out that because the multiplication is a binary operation, an expression like $abc$ is a priori not unambiguously defined. It seems I failed. Better luck next time.2011-02-12