MHB Proving General Associativity for Group by induction

cbarker1
Gold Member
MHB
Messages
345
Reaction score
23
Dear Everyone,

I am having some troubles with the problem. The problem states:

Let $(G,\star)$ be a group with ${a}_{1},{a}_{2},\dots, {a}_{n}$ in $G$. Prove using induction that the value of
${a}_{1}\star {a}_{2} \star \dots \star {a}_{n}$ is independent of how the expression is bracketed. My attempt

Base Case: We know that the definition of a group requires the associative property. So when $n=3$, associativity holds true.

Induction Hypothesis:
Assume $n>k$. (Here is where I am having troubles.)

Thanks,
Cbarker1
 
Physics news on Phys.org
I think this requires a lemma proved by ordinary induction on $n$: if $a_1\star\dots\star a_m$ and $a_{m+1}\star\dots\star a_{m+n}$ are left-associated, then their product equals the left-associated expression $a_1\star\dots\star a_{m+n}$.

Then in the proof of the main statement we break $a_1\star\dots\star a_n$ into a product of two shorter expressions, apply the inductive hypothesis to each of them and use the lemma. This requires strong induction on $n$.
 
How do we prove this lemma?

What does it mean to be left-associated?
 
I am calling expressions of the form $(\dots((a_1\star a_2)\star a_3)\star\dots\star a_{n-1})\star a_n$ left-associated.

Try proving the lemma yourself. You may consider examples for $n=1, 2, 3, 4$.
 
Evgeny.Makarov said:
I am calling expressions of the form $(\dots((a_1\star a_2)\star a_3)\star\dots\star a_{n-1})\star a_n$ left-associated.

Try proving the lemma yourself. You may consider examples for $n=1, 2, 3, 4$.
Suppose that ${a}_{1}\star {a}_{2}\star {a}_{3}...{a}_{m}$ and ${a}_{m+1}\star {a}_{m+2}...{a}_{m+n}$ are left-associated. Then, $({a}_{1} \star {a}_{2})\star ...)\star {a}_{m}$ and $({a}_{m+1} \star {a}_{m+2})...)\star {a}_{m+n}$. So then, $({a}_{1} \star {a}_{2})\star ...)\star {a}_{m}\star ({a}_{m+1} \star {a}_{m+2})...)\star {a}_{m+n}$. Therefore, we will get the following product ${a}_{1} \star {a}_{2}\star ...\star {a}_{m}\star {a}_{m+1} \star {a}_{m+2}...\star {a}_{m+n}$.

Is the proof corrected?

Thanks
Cbarker1
 
Cbarker1 said:
Suppose that ${a}_{1}\star {a}_{2}\star {a}_{3}...{a}_{m}$ and ${a}_{m+1}\star {a}_{m+2}...{a}_{m+n}$ are left-associated. Then, $({a}_{1} \star {a}_{2})\star ...)\star {a}_{m}$ and $({a}_{m+1} \star {a}_{m+2})...)\star {a}_{m+n}$.
"Then" must be followed by a proposition, i.e., something that is either true or false. Examples of propositions are: $x+y=z$, $x^2\ge0$, "$n$ is prime". In contrast, $(({a}_{1} \star {a}_{2})\star ...)\star {a}_{m}$ is an element of the group and as such is neither true nor false.

Cbarker1 said:
So then, $({a}_{1} \star {a}_{2})\star ...)\star {a}_{m}\star ({a}_{m+1} \star {a}_{m+2})...)\star {a}_{m+n}$.
Same remark. Besides, this expression is not fully parenthesized. The product of the two original expressions is $(\dots(a_1 \star a_2)\star\dots\star a_m)\star((\dots (a_{m+1} \star {a}_{m+2})\star\dots\star a_{m+n-1})\star {a}_{m+n})$.

Cbarker1 said:
Therefore, we will get the following product ${a}_{1} \star {a}_{2}\star ...\star {a}_{m}\star {a}_{m+1} \star {a}_{m+2}...\star {a}_{m+n}$.
How? That's the most important question of the proof. Have you done the examples carefully? Where exactly do you apply the inductive hypothesis?

Also, instead of "we will get" it is better to write a more precise statement, e.g., "the product equals...".

A remark about LaTeX. It is not necessary to put braces around an expression that is not an index (subscript). For example, {a}_{123} gives the same result as a_{123}. It is only necessary to put braces around an index if it consists of more than one character or command. For example, a_{m} is the same as a_m.
 
Back
Top