Alternative proof of the generalized associative law for groups

abstract-algebraalternative-proofgroup-theoryinduction

The generalized associative law for groups claims that the value of $a_1\star a_2\star … \star a_n$ is independent of how it is bracketed, where the symbols denote the usual notations of group theory.

While attempting a proof on my own, I discovered a method that seems right to me but does not appear anywhere as a standard proof. Please comment on the validity of this proof, since it is likely I messed up somewhere.

Throughout the proof we consider elements belonging to a group $G$.

We attempt a proof by induction on the number of elements in the expression. The base cases of 1,2,3 are seen to be true trivially or by the associative property. Now assume that the value of any n-element expression is independent of how the expression is bracketed. (Induction Hypothesis)

Now consider any $(n+1)$-element expression given by $a_1\star a_2\star … \star a_n\star a_{n+1}$. All bracketings of this expression may be divided into $n$ types as follows (these types are not necessarily disjoint):

  1. bracketings containing $(a_1\star a_2)$
  1. bracketings containing $(a_2\star a_3)$
    .
    .
    .

n. bracketings containing $(a_n\star a_{n+1})$

Let $(a_i\star a_{i+1})$ = $a_{(i,i+1)}$, which is also an element of $G$ (where $i$ ranges from $1$ to $n$).
Now for any type $i$ considered above, the corresponding $(n+1)$ – element expression can be reduced to an $n$ – element expression by substituting $a_{(i,i+1)}$ instead of $(a_i\star a_{i+1})$. Then by IH, all bracketings of this type evaluate to a bracketing- independent value which we shall call $A_i$.

It remains to show that $A_1 = A_2 = A_3 = …. = A_n$.

But note that for any $i$,
$A_i$ = $(..((a_1\star a_2)\star a_3)..\star a_{i-1}) \star ((a_{i}\star a_{i+1})\star a_{i+2})\star(..((a_{i+3}\star a_{i+4})\star a_{i+5})..\star a_{n+1})$ = $(..((a_1\star a_2)\star a_3)..\star a_{i-1}) \star (a_{i}\star( a_{i+1}\star a_{i+2}))\star(..((a_{i+3}\star a_{i+4})\star a_{i+5})..\star a_{n+1})$ = $A_{i+1}$.

So for all $i$ from $1$ to $n$, $A_i$ = $A_{i+1}$. This implies
$A_1 = A_2 = A_3 = …. = A_n$, as required. This proves the result for the case of $n+1$. The result is then true by induction for all natural $n$.

Best Answer

Your proof looks OK to me, apart from a couple of typos in the big formula showing $A_i=A_{i+1}$. That formula has an unintended "=" at the end of the first line, and it has "$=A_{i+1}$" at the end of the next-to-last line whereas it should be at the end of the last line.

I think what confused some of the commenters is that you're using $A_i$ initially to denote any of numerous bracketings, and you prove later that they're all equivalent. Let me write out a version of your proof intended to un-confuse that point.

Let $C_i$ be the class of those bracketings of $n+1$ factors in which $a_i$ and $a_{i+1}$ are bracketed together. (In the tree picture, this means that those two leaves have the same immediate predecessor.) These bracketings can be viewed as bracketings of $n$ factors, by treating the combination $(a_i*a_{i+1})$ as a single factor. (Chop those two leaves off the tree but retain their predecessor.) By induction hypothesis, all of the bracketings in $C_i$ are equivalent, meaning their equality is provable from the associative law.

So to complete the proof of the generalized associative law, it suffices to show that some bracketing in $C_i$ is equivalent to some bracketing in $C_{i+1}$. For this purpose, use a bracketing in $C_i$ that contains the segment $((a_i*a_{i+1})*a_{i+2})$ and the bracketing in $C_{i+1}$ that is the same except for changing that one segment to $(a_i*(a_{i+1}*a_{i+2}))$. These are equivalent because the only change was one application of the associative law.

I claim that this is a proof, that the commenters would accept it as a proof, and that it's really the same as your proof.

Related Question