1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Associativity math help

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

    [tex]a_1*a_2*...*a_n [/tex]

    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
    [tex](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}[/tex]
    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. jcsd
  3. Jan 1, 2008 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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....
     
  4. Jan 1, 2008 #3
    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?
     
  5. Jan 1, 2008 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's called a library. :wink:
     
  6. Jan 1, 2008 #5
    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. :(
     
  7. Jan 1, 2008 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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--|
     
     
  8. Jan 1, 2008 #7
    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.
     
  9. Jan 1, 2008 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The IH says you can rearrange the tree without changing the value!
     
  10. Jan 1, 2008 #9
    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
  11. Jan 1, 2008 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You identified a specific obstacle earlier -- can you see how to overcome it?
     
  12. Jan 1, 2008 #11
    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?
     
  13. Jan 1, 2008 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, that's the basic idea.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Associativity math help
  1. Math Help (Replies: 3)

  2. Transitive math help (Replies: 16)

Loading...