3
$\begingroup$

I want to prove the following: If $G$ is a group under the operation $\star$, $\forall a_1,...,a_n\in G$, the value of $a_1\star a_2\star ... \star a_n$ is independent of how the expression is bracketed.

My attemp at the proof:

We prove this with induction on $n$. Base case: $n=3$, $a_1\star (a_2\star a_3)=(a_1\star a_2)\star a_3$. This is true by the definition of a group operation. Because a group operation is a mapping $\star :G\times G\rightarrow G$, we can substitute any $a_i\star a_j$ with some $a_k\in G$. Therefore, $a_1\star a_2\star ...\star a_n\star a_{n+1}$ is equivalent to $a_1\star a_2\star ...\star a_k$, which is true by the inductive hypothesis.

I want to know if:

$1)$ There are any correction to be made, and

$2)$ Better wording for the proof.

Thank you all in advance.

$\endgroup$
  • $\begingroup$ This proof doesn't really make any sense. How do you know you're replacing the same two elements in the two expressions? $\endgroup$ – Steve D Oct 6 '17 at 0:32
8
$\begingroup$

I see what you're trying to do here, but the wording needs some work.

I actually proved this in an assignment once. It was a great work of passive agression against my lecturer who insisted vehemently that no steps be missed. So, I decided to try formally proving generalised associativity (and commutativity too). Here's a cleaned-up version of the proof I gave him.

Lemma: (Generalised Associativity) Suppose $(G, *)$ is a group. We can recursively define a sequence $(*^n : G^n \rightarrow G)_{n=1}^\infty$ by: $$*^1 : x \mapsto x$$ $$*^{n+1} : (x_1, \ldots , x_{n+1}) \mapsto (*^n(x_1, \ldots , x_n)) * x_{n+1}$$ Then $*^2 = *$ and, for any $m, n \in \mathbb{N}$, and $(x_1, \ldots, x_{m+n}) \in G^{m+n}$, we have: \begin{equation} *^{m+n}(x_1, \ldots, x_{m+n}) = (*^m(x_1, \ldots, x_m)) * (*^n(x_{m+1}, \ldots, x_{m+n})) \tag{$\star$} \end{equation}

Proof. The first claim that $*^2 = *$ follows immediately from the recurrence relation with $n = 1$. To prove the second claim, we proceed by induction on $n$. That is, for each $n \in \mathbb{N}$, we wish to prove ($\star$) for all $m \in \mathbb{N}$. For $n = 1$, the equality to be proven is simply the recurrence relation, so we have our base case. Fix $n > 1$, and suppose the claim is true for $n - 1$ instead of $n$. Then, for any $(x_1, \ldots, x_{m + n}) \in G^{m + n}$, we have: \begin{align*} *^{m + n}(x_1, \ldots, x_{m+n}) &= (*^{m+n-1}(x_1, \ldots, x_{m+n-1})) * x_{m+n} \\ &= ((*^m(x_1, \ldots, x_m)) * (*^{n-1}(x_{m+1}, \ldots, x_{m+n-1}))) * x_{m+n} \\ &= (*^m(x_1, \ldots, x_m)) * ((*^{n-1}(x_{m+1}, \ldots, x_{m+n-1})) * x_{m+n}) \\ &= (*^m(x_1, \ldots, x_m)) * (*^n(x_{m+1}, \ldots, x_{m+n})) \end{align*} by the recurrence relation, inductive hypothesis, associativity, and the recurrence relation respectively. By induction, we have proven the claim. QED.

The notation of generalised associativity is rather painful, but it lays the foundations for the common, and far more elegant notation for group operations (and associative operations in general). We typically denote: $$x_1 * x_2 * \ldots * x_n := *^n (x_1, x_2, \ldots, x_n)$$ Notice that, because $*^2 = *$, this notation is consistent with the infix notation of the binary operation $*$. The equality ($\star$) now translates to the far less intimidating: $$x_1 * \ldots * x_m * x_{m+1} * \ldots * x_{m+n} = (x_1 * \ldots * x_m) * (x_{m+1} * \ldots * x_{m+n})$$ In essence, this means we can consistently write strings of group elements delineated by the group operation, and place parentheses anywhere (so long as the formula remains well-formed) without affecting the overall result of the operation.

All of that said, I do realise that the exposition at the end is a bit of a cop-out. In order to do things properly, you need to be able to encode the idea of placing brackets in order to form a well-formed expression. My suggestion would be to form a parse tree, and prune it inductively.

Anyway, I hope this helps in some way.

$\endgroup$
  • $\begingroup$ Thank you for the very detailed answer, was a bit confused at first with the different notation, but I see that it's much more efficient. I don't see why your proof wouldn't be considered a "well-formed" expression, the logic of it seems complete to me. $\endgroup$ – 高田航 Oct 6 '17 at 1:13
  • 1
    $\begingroup$ here's another link to a proof: groupprops.subwiki.org/wiki/… $\endgroup$ – yoshi Sep 5 '18 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.