Order of calculation in a Semigroup.

Question

If $(A,\cdot)$ is a semigroup, i.e. if we have: $\forall (x,y,z)\in A^{3}, (x\cdot y)\cdot z=x\cdot(y\cdot z)$, then the order of calculations doesn't matter no matter the number of factors and we can do aways with the parenthesis, for example: $\forall (w,x,y,z)\in A^{4}, (w\cdot(x\cdot y))\cdot z=(w\cdot x)\cdot(y\cdot z)=w\cdot x\cdot y\cdot z $ It seems obvious but I don't really know how to prove this for any n-uple of elements of A. It probably is a recurrence, but I don't see how to write it. Help?

Answer 1

This is a standard thing, with a standard proof that I don't know. Here's a fairly simple proof.

Given $x_1,\dots,x_n$, define the standard grouping for the product $x_1\dots x_n$ to be "$\prod_{j=1}^nx_j$", defined recursively by $\prod_{j=1}^1x_j=x_1$ and $$\prod_{j=1}^{n+1}x_j=\left(\prod_{j=1}^nx_j\right)x_{n+1}.$$

It's enough to prove by induction on $n$ that if $\alpha$ is any grouping of the product $x_1\dots x_n$ then $\alpha$ is equal to the standard grouping.

Now, there exist a grouping $\beta$ of the product $x_1\dots x_k$ and a grouping $\gamma$ of the product $x_{k+1}\dots x_n$ such that $$\alpha=\beta\gamma.$$Here $1\le k<n$. Since both $\beta$ and $\gamma$ involve fewer variables, you can assume by induction that $$\beta=\prod_{j=1}^kx_j$$and$$\gamma=\prod_{j=k+1}^nx_j.$$So you only need to show that $$\left(\prod_{j=1}^{k}x_j\right)\left(\prod_{j=k+1}^{n}x_j\right)=\prod_{j=1}^nx_j.$$

And you prove that by an easy induction on $n-k$, the number of factors in $\gamma$. It's true for $n-k=1$ by the definition of the standard grouping, and the induction step is trivial: $$\begin{eqnarray}\left(\prod_{j=1}^{k}x_j\right)\left(\prod_{j=k+1}^{n+1}x_j\right)&=&\left(\prod_{j=1}^{k}x_j\right)\left(\left(\prod_{j=k+1}^{n}x_j\right)x_{n+1}\right) \\&=&\left(\left(\prod_{j=1}^{k}x_j\right)\left(\prod_{j=k+1}^{n}x_j\right)\right)x_{n+1} \\&=&\left(\prod_{j=1}^nx_j\right)x_{n+1} \\&=&\prod_{j=1}^{n+1}x_j.\end{eqnarray}$$

Answer 2

Prove, by induction on $n$, that every parenthesization of $n$ or fewer factors gives the same product as "parenthesization to the left". The cases of $n=1$ and $2$ are trivial, and $3$ is the assumption of associativity; these provide the basis of the induction. For the induction step, regard any product of $n+1$ factors as the product of two pieces, each having $n$ or fewer factors. Apply the induction hypothesis to each of the two pieces; then apply associativity to put it in the form of a complicated product of $n$ elements times (on the right) a single element; finally, apply the induction hypothesis once more to that complicated product.