1
$\begingroup$

I've seen it asserted in several places (e.g., Spivak's Calculus, p.3) that the fact that "parentheses can be freely rearranged" in expressions involving only addition ($+$) is based solely on (P1) associtivity of addition, $$a+\left(b+c\right) =\left(a+b\right)+c,$$ and can see that this is the case in every example I've tired. However it is also asserted that one can eliminate parenthesis altogether, so that, for example $$a+b+c$$ is identical to the above expressions.

I can't see how to prove this with using only P1. The proof would seem to require (P2) additive identity, $$a+0=a,$$ (P3) additive inverse, $$a+\left(-a\right)=0,$$ and (P4) commutativity, $$a+b=b+a.$$ For example, the proof $$\left(a+b\right)+c$$ $$=\left(a+b\right)+c+0$$ $$=0+\left(a+b\right)+c$$ $$=a+\left(-a\right)+\left(a+b\right)+c$$ $$=a+\left(\left(-a\right)+a\right)+b+c$$ $$=a+\left(a+\left(-a\right)\right)+b+c$$ $$=a+0+b+c$$ $$=a+b+c$$ requires P2, P4, P3, P1, P4, P3, and P2.

Am I missing something that allows one to conclude that $$\left(a+b\right)+c=a+b+c$$ based solely on P1? Perhaps there something subtle about what parentheses represent that I'm missing.

$\endgroup$
  • 2
    $\begingroup$ I always thought brackets simply represent order of operations. So a + b + c is the same as (a + b) + c, if we define addition as left-to-right (and the opposite if we define the other way). $\endgroup$ – davin Sep 28 '11 at 21:57
  • $\begingroup$ Note that parentheses can only be freely rearranged when the sum involves finitely many terms: $(1 + -1) + (1 + -1) + \ldots \neq 1 + (-1 + 1) + (-1 + 1) + \ldots$ for instance. $\endgroup$ – user7530 Sep 28 '11 at 22:21
  • $\begingroup$ I think my question wasn't clear. I'm given just P1, as written above. Is that sufficient to conclude $(a+b)+c=a+b+c$ or do I need additional properties? $\endgroup$ – orome Sep 29 '11 at 1:25
  • $\begingroup$ @davin: Is that my mistake then (and the reason that my question is dumb)? The parentheses aren't just arbitrary symbols that require formal steps to remove (as in my "proof"). They're just what we all "know" they are: a way of specifying the order of operations. $\endgroup$ – orome Sep 29 '11 at 2:02
6
$\begingroup$

HINT $\: $ It is easy: keep pushing ')'s rightward using the rewrite rule $\rm\ (x+y)+z\ \to\:\ x+(y+z)\:.\ $ An easy induction shows that this process terminates with the right-associated normal form where all ')'s are at the right end, e.g. $\rm\ a+(b+(c+(d+\:\cdots\:)))\:.\: $ By associativity, the rewrite rule preserves equality, so every possible bracketing of the summands is equal to the normalized bracketing. Thus we can omit the brackets, yielding a well-defined $\rm\:n$-ary addition operation $\rm\ a_1+ a_2+\: \cdots\:+a_n\:. $

However, for nonassociative operations, different bracketings need not yield equal values, so the brackets are required in order to uniquely specify the intended value. It might help to think of the expressions presented as (parse) trees, e.g. below. enter image description here

$\endgroup$
  • $\begingroup$ So it is the case then that I'm attaching too much significance to the parentheses as symbols, and thus to the formalism if getting rid of them—that their only significance is the obvious and common one of specifying an order, so that once things are in the normal form above, we can simply drop them, based on their effect on the order of operation? If that's the case, I see that only P1 is indeed necessary (and the elaborate "proof" is not). $\endgroup$ – orome Sep 29 '11 at 1:34
  • $\begingroup$ @rax What I wrote above holds true for any associative operation. None of the other laws are required to show that sums are independent of the bracketing. For example consider, for products $\rm\:((ab)c)d = (ab)(cd) = a(b(cd))\:.$ $\endgroup$ – Bill Dubuque Sep 29 '11 at 1:58
  • $\begingroup$ Yes, I see that, as for addition. But what I was unsure of was what additional rules or definitions were required to remove the parentheses altogether. If I understand correctly, you've answered that. $\endgroup$ – orome Sep 29 '11 at 2:05
  • $\begingroup$ @rax Yes, only the associative law is required. $\endgroup$ – Bill Dubuque Sep 29 '11 at 2:09
  • 2
    $\begingroup$ @rax The brackets specify not order but, rather, shape (tree structure). $\endgroup$ – Bill Dubuque Sep 29 '11 at 3:46
12
$\begingroup$

$+$ is initially defined only as a binary operation. Then we can define $a+b+c$ as either $(a+b)+c$ or $a+(b+c)$; associativity says it doesn't matter which one we use, since they are equal. But until that definition is made, the expression $a+b+c$ has no meaning.

$\endgroup$
  • $\begingroup$ So is it simply that? The full definition of associativity is just $$a+\left(b+c\right) =\left(a+b\right)+c=a+b+c$$ and there is, in fact, nothing further to prove? $\endgroup$ – orome Sep 29 '11 at 1:17
  • $\begingroup$ @rax: Dear raxacoricofallapatorius, Yes, although the two equalities are of a slightly different nature: the first is not true by definition, but is rather an axiom (the associative law). The second is true by definition: it is what "$a+b+c$" means. Regards, $\endgroup$ – Matt E Sep 29 '11 at 5:18
5
$\begingroup$

The point is that no matter how you parenthesize $a+b+c$, the result is the same, so the expression without parentheses is unambiguous. Thus, it doesn’t matter whether you define $a+b+c$ to be $(a+b)+c$ or $a+(b+c)$. (Note that some such definition is ultimately required, since $+$ is originally defined only as a binary operation.)

Compare this with $a-b-c$: in general $(a-b)-c\ne a-(b-c)$, so the expression $a-b-c$ is uninterpretable without some convention, e.g., work from left to right. When the operation is associative, no such convention is required.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.