# Associativity math help

1. Dec 31, 2007

### ehrenfest

1. The problem statement, all variables and given/known data
I am trying to prove that if the binary operation * is associative, then

$$a_1*a_2*...*a_n$$

is unambiguous.

2. Relevant equations

3. The attempt at a solution
This clearly calls for induction. The base case, n=3, is true by the definition of associativity. Assume that the result is true for n=k. From the induction hypothesis, it is clear that (a_1*...*a_n)*a_{k+1} is unambiguous. It is also clear that a_1*(a_2*...*a_{k+1}) is unambiguous. Because both of these expressions are unambiguous and because we have the n=3 case, we know that
$$(a_1*...*a_k)*a_{k+1} = (a_1*(a_2*...*a_k))*a_{k+1} = a_1*((a_2*...*a_k)*a_{k+1}) = (a_1*...*a_k)*a_{k+1}$$
So, that shows the result for one very specific case. I cannot think of how to knock out all the cases at once though...

Last edited: Jan 1, 2008
2. Jan 1, 2008

### Hurkyl

Staff Emeritus
Do you know what a parse tree is? That should help organize things conceptually.

Anyways, the general case is suppose you have to factorizations of your product:

A * B
C * D

where A has fewer terms than C....

3. Jan 1, 2008

### mathboy

Proofs of these important fundamental properties must be in a textbook somewhere. But I've never seen this proof before. Where are these proofs stored? Why doesn't the math literature keep a central inventory of proofs?

4. Jan 1, 2008

### Hurkyl

Staff Emeritus
It's called a library.

5. Jan 1, 2008

### ehrenfest

I see. Suppose we represent two different ways of multiplying

a_1*a_2*...*a_n

with parse trees T_1 and T_2. For these parse trees to make sense in this context, we require that every node has exactly two branches. Also require that this parse is embedded in a plane such that the leafs a_1,...,a_n are laid out in a straight line and that THERE ARE NO CROSSING BRANCHES. This ensures that the parse tree represents some way of inserting parenthesis in that product such that every pair of parenthesis encloses two elements. Also, we can easily draw a parse tree representing any way of evaluating the product.

Now, in our two different parse trees, let A and B be the two second-level nodes of T_1, with A to the left of B and let C and D be the two second-level nodes of T_2, with C to the left of D. If C has the same number of elements as A,we apply the induction hypothesis to A and C, and B and D, and we are done. If A has fewer terms than C, then I think I am stuck. :(

6. Jan 1, 2008

### Hurkyl

Staff Emeritus
Well, it does mean that A only has a subset of the terms of C...

If I diagram it, it might look like:

Code (Text):

|--A--|----B----|
|----C----|--D--|

7. Jan 1, 2008

### ehrenfest

The terms in A are a subset of the terms in C. That does NOT mean that there is a node below C that contains exactly the same terms as A. So, I am not really sure how to apply the IH.

8. Jan 1, 2008

### Hurkyl

Staff Emeritus
The IH says you can rearrange the tree without changing the value!

9. Jan 1, 2008

### ehrenfest

It says you can reevaluate k terms in a different way without changing the value. I am not seeing which k terms in T_1 I need to reevaluate to get T_2.

Last edited: Jan 1, 2008
10. Jan 1, 2008

### Hurkyl

Staff Emeritus
You identified a specific obstacle earlier -- can you see how to overcome it?

11. Jan 1, 2008

### ehrenfest

I'll try. Let A = abcdefghij. let B = klmnopqr...wxyz

Let C = abcdefghijklmno. Let D = pqrst...wxyz.

We want to show that A*B = C*D. The induction hypothesis tells us that A,B,C,and D are unambiguous. The induction hypothesis also tells us that

A*B = (abcdefghij)(klmnopqrstuvwxyz)=(abcdefghij)((klmno)(pqrstuvwxyz))

We now apply the property of associativity (n=3) to get that:

(abcdefghij)((klmno)(pqrstuvwxyz))=((abcdefghij)(klmno))(pqrstuvwxyz)

We again apply the IH to get that

((abcdefghij)(klmno))(pqrstuvwxyz)=(abcdefghijklmno)(pqrstuvwxyz)=C*D

Does that work?

12. Jan 1, 2008

### Hurkyl

Staff Emeritus
Yes, that's the basic idea.