Proving General Associativity for Group by induction

In summary, The problem states that the value of ${a}_{1}\star {a}_{2} \star \dots \star {a}_{n}$ is not dependent on how the expression is bracketed. The proof uses a lemma proved by ordinary induction on $n$.
  • #1
cbarker1
Gold Member
MHB
349
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
  • #2
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$.
 
  • #3
How do we prove this lemma?

What does it mean to be left-associated?
 
  • #4
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$.
 
  • #5
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
 
  • #6
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.
 

FAQ: Proving General Associativity for Group by induction

1. What is the concept of proving general associativity for a group by induction?

Proving general associativity for a group by induction is a mathematical method used to show that a group operation is associative for any number of elements in the group. It involves using mathematical induction to prove that the operation holds true for a base case and then showing that it also holds true for any additional elements added to the group.

2. Why is it important to prove general associativity for a group?

Proving general associativity for a group is important because it ensures that the group operation will always produce the same result, regardless of the order in which the elements are grouped. This is a fundamental property of groups and is necessary for many mathematical proofs and applications.

3. What is mathematical induction and how is it used in proving general associativity for a group?

Mathematical induction is a proof technique that involves showing that a statement is true for a base case and then showing that it also holds true for any additional cases. In proving general associativity for a group, mathematical induction is used to show that the group operation is associative for a base case (usually 2 or 3 elements) and then showing that it also holds true for any additional elements added to the group.

4. Can general associativity be proven for any group?

Yes, general associativity can be proven for any group, as long as the group operation is associative for the base case and the induction step is valid. However, the process of proving general associativity may vary depending on the specific group and operation being studied.

5. Are there any limitations to proving general associativity for a group by induction?

While proving general associativity for a group by induction is a powerful and widely applicable method, it may not be suitable for every situation. In some cases, alternative proof techniques may be more efficient or easier to understand. Additionally, the process of proving general associativity may become more complex for larger groups with more elements.

Similar threads

Replies
2
Views
1K
Replies
2
Views
2K
Replies
9
Views
2K
Replies
9
Views
1K
Replies
1
Views
1K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
1K
Back
Top