Generalized Associative Law for Groups

[sammycaps]

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 a₁,...,a_n, any bracketing of the expression a₁°...°a_n can be rewritten as (a₁°...°a_k)°(a_k+1°...°a_n).

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 a₁°...°a_n 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 a_i with b_i). 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 x_i ° y_i. So if we substitute back in all the a_i along with the brackets, we will get (a₁°...°a_k)°(a_k+1°...°a_n), 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?

 

[Fredrik]

I'm not able to follow your description.

Show that for any group G under the operation °, and elements a₁,...,a_n, any bracketing of the expression a₁°...°a_n can be rewritten as (a₁°...°a_k)°(a_k+1°...°a_n).

Is n arbitrary? What about k?

First place brackets such that every bracket contains exactly two elements of the group and one °.

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?

Then proceed by replacing each bracketed item with a b (so replace a_i with b_i).

I don't understand this comment either.

 

[sammycaps]

I'm not able to follow your description.Is n arbitrary? What about k?

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?

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?

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

I don't understand this comment either.

With respect to the comment about "replacing", this simply means that if we bracket in the first step as such, (a₁a₂)(a₃a₄)(a₅a₆), we would replace this statement by b₁b₂b₃, where b₁=(a₁a₂), b₂=(a₃a₄), and b₃=(a₅a₆).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 a₁=(ab), a₂=(cd) and a₃=(ef), and get a₁a₂a₃g. Then step 2 would be to bracket this in some way. Let's say we write it as (a₁a₂)(a₃g). Then we replace x₁=(a₁a₂) and y₁=(a₃g), so that we get x₁y₁, 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 {a₁, a₂, a₃, g}, and continue in that fashion. Then, the "bracketing" would represent the order of the operation.

Is there a better way to do this?

 

[Fredrik]

Do I need induction on N? If the construct is valid for arbitrary N, it should be fine, right?

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

"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, (a₁a₂)(a₃a₄)(a₅a₆), we would replace this statement by b₁b₂b₃, where b₁=(a₁a₂), b₂=(a₃a₄), and b₃=(a₅a₆).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 a₁=(ab), a₂=(cd) and a₃=(ef), and get a₁a₂a₃g. Then step 2 would be to bracket this in some way. Let's say we write it as (a₁a₂)(a₃g). Then we replace x₁=(a₁a₂) and y₁=(a₃g), so that we get x₁y₁, 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," but the order of operations is ambiguous, so let me know.

Is the point of all this to define the meaning of the string of text "a₁a₂...a_n"? 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.

 

[sammycaps]

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 "a₁a₂...a_n"? 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.

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?

 

[Fredrik]

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

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
\begin{align}
(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.

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?

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.

 

[Fredrik]

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?