27
$\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.

  • 0
    http://www.proofwiki.org/wiki/General_Associativity_Theorem2012-01-07

6 Answers 6

38

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

  • 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
10

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\ abc\cdots $ (unambiguous - since every bracketing rewrites to it by below).

Below is a proof sketch, by induction on the length $\rm\:\ell(Z) = $ number of operands (factors)

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

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

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

$\rm\ \ \ell(X)\! >\! 1\!:\ \ \ XY = \underbrace{(a \bar X)Y = a(\bar X Y)}_{\rm associative\ law} = a(b(c(\cdots)))\ $ by induction applied to $\rm X,\, $ then $\rm\bar XY$

The proof used only the associative law $\rm\, (XY)Z = X(YZ)\,$ so works for any associative operation.

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.

  • 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