Proving Associativity in Binary Operations: Math Help for Unambiguous Results

[ehrenfest]

Homework Statement

I am trying to prove that if the binary operation * is associative, then

a_1*a_2*...*a_n

is unambiguous.

Homework Equations

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

 

[Hurkyl]

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

 

[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?

 

[Hurkyl]

Why doesn't the math literature keep a central inventory of proofs?

It's called a library.

 

[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. :(

 

[Hurkyl]

If A has fewer terms than C, then I think I am stuck. :(

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

If I diagram it, it might look like:

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

 

[ehrenfest]

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

If I diagram it, it might look like:

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

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.

 

[Hurkyl]

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.

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

 

[ehrenfest]

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

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.

 

[Hurkyl]

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.

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

 

[ehrenfest]

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

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?

 

[Hurkyl]

Yes, that's the basic idea.