Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Generalized Associative Law for Groups

  1. Jan 18, 2013 #1
    Prove the Generalized Associative Law for Groups (i.e. a finite sum of elements can be bracketed in any way).

    The proof is outlined in D & F. I just want to know whether or not one part of my proof is correct.

    Show that for any group G under the operation °, and elements a1,...,an, any bracketing of the expression a1°...°an can be rewritten as (a1°...°ak)°(ak+1°...°an).

    Originally, I considered defining a directed set and working with that, but this seemed like extra unecessary steps. So, I will instead proceed by starting with the expression a1°...°an and bracketing as follows. First place brackets such that every bracket contains exactly two elements of the group and one °. Then proceed by replacing each bracketed item with a b (so replace ai with bi). Then repeat step one. Continue this process, replacing each new bracketed pair with a new indicator. It must terminate when there are two elements left because there are finite elements and operations. Then we are left with xi ° yi. So if we substitute back in all the ai along with the brackets, we will get (a1°...°ak)°(ak+1°...°an), where each half is bracketed in some way.

    Then we can see that the construction I've described defines all possible ways to bracket the expression, so we are done.

    Is this valid, and would we need to show this indeed defines all bracketing possibilities, or is it clear enough?
    Last edited: Jan 18, 2013
  2. jcsd
  3. Jan 19, 2013 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm not able to follow your description.

    Is n arbitrary? What about k?

    What does this mean? abcdefg=(ab)(cd)(ef)g? Maybe abcdefg=(a(b(c(d(e(fg))))))? What do you mean by "place brackets"? Are you just "placing" them, or are you saying that something is equal to some other thing? :confused:

    I don't understand this comment either.
  4. Jan 19, 2013 #3
    N is arbitrary, and its simply saying for some k that the product looks like this, not for any k. Do I need induction on N? If the construct is valid for arbitrary N, it should be fine, right?

    "Place brackets" just means to choose the first step of the product, i.e. choose, among the n elements, disjoint groups of two elements and an operation between them. Each bracket represents an operation.

    With respect to the comment about "replacing", this simply means that if we bracket in the first step as such, (a1a2)(a3a4)(a5a6), we would replace this statement by b1b2b3, where b1=(a1a2), b2=(a3a4), and b3=(a5a6).

    I'll work with your example. If we have abcdefg, our first step would be to bracket in some way the initial elements. So (ab)(cd)(ef)g. Then we would replace a1=(ab), a2=(cd) and a3=(ef), and get a1a2a3g. Then step 2 would be to bracket this in some way. Let's say we write it as (a1a2)(a3g). Then we replace x1=(a1a2) and y1=(a3g), so that we get x1y1, and we're done.

    Is this valid to do? I'm not sure I can just say, "write abcdefg and choose some operations to do first, so (ab)(cd)(ef)g is our expression," since the order of operations is ambiguous. Maybe a more precise statement is, consider the ordered set {a,b,c,d,e,f,g}. Choose operations between adjacent elements, and then observe the new set {a1, a2, a3, g}, and continue in that fashion. Then, the "bracketing" would represent the order of the operation.

    Is there a better way to do this?
    Last edited: Jan 19, 2013
  5. Jan 19, 2013 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, if you can prove it for arbitrary N, then there's no need for induction.

    Is the point of all this to define the meaning of the string of text "a1a2...an"? I agree that products of more than 2 variables must be defined. I think it's best to do some sort of recursive definition, like
    $$\prod_{i=1}^n a_i=\left(\prod_{i=1}^{n-1}a_i\right)a_n.$$ Your approach seems valid, but it's hard to describe it accurately for arbitrary products, as you have noticed.

    I have proved this theorem once, but I did it without using any hints from books, so I don't know if what I came up with looks anything like the standard proofs. My proof involves both a recursive definition of a product of n variables*, and an induction step to go from products of n variables to n+1 variables. (It took me a long time to figure this out. I found it fascinating that a theorem that's so obviously true was so hard to prove).

    *) My definition was different from the one above. It was more like, for all n, a product of n variables is an expression of the form (P)(Q), where, for some k, P is a product of k variables and Q is a product of n-k variables.
  6. Jan 19, 2013 #5
    I think Dummit and Foote allowed finite products of more than 2 elements to be defined, assuming the reader understood the bracketing notation, but gave a small discussion (and outlined a proof, where this is a piece of that I am trying to formalize) about the choice of order in operations in defining this product (i.e. showing that a(b(cd))=(ab)(cd).

    They did not outline the rules for "bracketing", but I don't think it would be too difficult to formalize these rules (in fact, I think I defined all possible valid bracketing).

    The point of this whole thing really was to show the "Generalized Associative Law for Groups", and this was a step in the process that Dummit and Foote suggested to proving it. Explicitly, this is just the theorem that given an operation that is associative a(bc)=(ab)c, then any finite product does not depend on the choice of brackets (i.e. choice of order of operations).

    It is indeed unfortunate that something that seems obvious is so difficult to prove (but there are other examples of this). Were you proving that the recursive definition you defined was independent of the choice of order of operations, or were you proving that a specific choice in the order of operations was consistent?
  7. Jan 20, 2013 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It looks to me like you only described one way to bracket the product of n factors. That's why I thought you were only going for the definition of the product, not the proof of the theorem. However, your approach can also be used as the induction step from products of less than n factors to products of n factors. This is because if you view the result for products of less than n factors as already proved, you can rearrange the brackets any way you want in each of the two factors ##a_1\cdots a_k## and ##a_{k-1}\cdots a_n##. (You didn't mention that, and in fact suggested that you don't need induction). You can use that to write
    (a_1\cdots a_k)(a_{k+1}\cdots a_n) &=\big((((a_1a_2)a_3)\cdots)a_k\big) \big(a_{k+1}(\cdots(a_{n-1}a_n))\big)\\
    &\big((((a_1a_2)a_3)\cdots)a_{k-1}\big) \big(a_{k}(\cdots(a_{n-1}a_n))\big) =\cdots=\\
    &a_1(a_2(\cdots (a_{n-2}(a_{n-1}a_n)))).
    \end{align} This is in fact exactly what I did. Note that the first step uses the result for less than n factors. This is why the above is only the induction step, and not a complete proof.

    I was proving that the product has the same value regardless of where the parentheses are, by showing that for all n, any product of n factors can be put in the standard form that's the end result of my calculation above.
  8. Jan 20, 2013 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Now I have a question about this, for anyone who finds this sort of thing interesting. We are working within the branch of mathematics defined by ZFC set theory and an associated proof theory. This means that all our theorems are statements about sets. But the "generalized associative law" isn't about sets, it's about strings of text that represent sets. So is it even correct to call it a "theorem"? Should it be called something else? "Meta-theorem" perhaps? Can it be stated in a way that makes it a statement about sets and not a statement about text?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook