Proving General Associativity for Group by induction

[cbarker1]

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

 

[Evgeny.Makarov]

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

 

[cbarker1]

How do we prove this lemma?

What does it mean to be left-associated?

 

[Evgeny.Makarov]

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

 

[cbarker1]

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

 

[Evgeny.Makarov]

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.

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

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.