Basic algebra proof review for the commutativity of a product

I am able to prove that the product of $x_{1}, ..., x_{n}$ is the same no matter how you order it in a commutative monoid $G$ if this theorem, along with its proof, is correct: http://mathbin.net/74656

I hope you don't mind that I wrote it in mathbin, it's just that I prefer using that. What I am asking for is basically a review of the proof because I'm not too sure it is formal and correct.

-
It looks more or less similar to this proof, though you are doing induction on the image of $n$, whereas the proof I link to uses induction on the number of factors. – Arturo Magidin Oct 15 '11 at 20:39
@ArturoMagidin: That seems to be the same proof given in the book that I'm following (Lang's Algebra). I wanted to come up with my own proof (partly because I didn't feel like trying to completely understand his proof :p) – Pedro Oct 15 '11 at 21:01
Yes, it is essentially the proof in Lang. Upon looking at your argument, though, I don't think it's right. I don't think your induction is correct: your induction hypothesis is that if $n$ is mapped to $k$, then the product over the permutation $\psi$ is the same as over the permutation $\psi'$. But in the inductive step, you are trying to perform a "shuffle" which is not your induction hypothesis, so I don't see how you justify the inductive step. – Arturo Magidin Oct 15 '11 at 21:07

Let me expand on my comment.

It seems that you are trying to prove a "one step" general commutativity, by showing that if you have a permutation $\psi\colon \{1,\ldots,n\}\to\{1,\ldots,n\}$ that "moves $n$", then you can replace it with a permutation $\psi'$ that has the same values as $\psi$ everywhere except at $n$ and at $\psi^{-1}(n)$; namely, if $\psi^{-1}(n)=k$, then you define $$\phi(i) = \left\{\begin{array}{ll} \psi(i) &\text{if }i\neq k, i\neq n;\\ \psi(n) &\text{if }i=k;\\ n &\text{if }i=n. \end{array}\right.$$ and then want to show that for any elements $a_1,\ldots,a_n\in M$, $$\prod_{i=1}^n a_{\psi(i)} = \prod_{i=1}^{n}a_{\phi(n)}.$$

You try to argue by induction on $\delta=n-k$. When $k=1$, you have that $\psi(n-1)=n$, so \begin{align*} a_{\psi(1)}\cdots a_{\psi(n-1)}a_{\psi(n)} &= \bigl(a_{\phi(1)}\cdots a_{\phi(n-2)}\bigr)a_na_{\phi(n-1)}\\ &= \bigl(a_{\phi(1)}\cdots a_{\phi(n-2)}\bigr)a_{\phi(n-1)}a_n\\ &= a_{\phi(1)}\cdots a_{\phi(n-2)}a_{\phi(n-1})a_{\phi(n)}, \end{align*} so you are fine.

Your induction hypothesis then is that if $\phi(k)=n$, then $$\bigl(a_{\psi(1)}\cdots a_{\psi(k-1)}\bigr)a_n\bigl(a_{\psi(k+1)}\cdots a_{\psi(n)}\bigr) = \bigl( a_{\psi(1)}\cdots a_{\psi(k-1)}\bigr)\bigl(a_{\psi(k+1)}\cdots a_{\psi(n)}\bigr)a_n.$$ You then consider the situation in which $\phi(k-1)=n$. You have: $$\bigl( a_{\psi(1)}\cdots a_{\psi(k-2)}\bigr) a_n \bigl( a_{\psi(k)}\cdots a_{\psi(n)}\bigr).$$ I cannot see how you are applying your induction hypothesis to go from here to $$\bigl( a_{\psi(1)}\cdots a_{\psi(k-2)}\bigr)a_{\psi(n)}\bigl(a_{\psi(k)}\cdots a_{\psi(n-1)}\bigr) a_{n}.$$ Rather, you seem to be applying associativity and a two-step binary commutativity. If this is the case, then why muddie the waters with an unnecessary proof "by induction"? You aren't really doing induction, you are using associativity and binary commutativity.

Simply let $k$ be the element such that $\psi(k) = n$. Then \begin{align*} a_{\psi(1)}\cdots a_{\psi(n)} &= \Bigl(a_{\psi(1)}\cdots a_{\psi(k-1)}\Bigr)a_{\psi(k)}\Bigl(\bigl(a_{\psi(k+1)}\cdots a_{\psi(n-1)}\bigr)a_{\psi(n)}\Bigr)\\ &= \Bigl(a_{\phi(1)}\cdots a_{\phi(k-1)}\Bigr)a_{n}\Bigl(\bigl(a_{\phi(k+1)}\cdots a_{\phi(n-1)}\bigr)a_{\phi(k)}\Bigr)\\ &= \Bigl(a_{\phi(1)}\cdots a_{\phi(k-1)}\Bigr)a_{n}\Bigl(a_{\phi(k)}\bigl(a_{\phi(k+1)}\cdots a_{\phi(n-1)}\bigr)\Bigr)\\ &= \Bigl(a_{\phi(1)}\cdots a_{\phi(k-1)}\Bigr)\Bigl(a_{\phi(k)}\bigl(a_{\phi(k+1)}\cdots a_{\phi(n-1)}\bigr)\Bigr)a_n\\ &= a_{\phi(1)}\cdots a_{\phi(k-1)}a_{\phi(k)}a_{\phi(k+1)}\cdots a_{\phi(n-1)}a_{\phi(n)}\\ &= a_{\phi(1)}\cdots a_{\phi(n)}, \end{align*} as desired; first equality holds by general associativity; second by the definition of $\phi$; third by commuting the elements $a_{\phi(k)}$ and $(a_{\phi(k+1)}\cdots a_{\phi(n-1)})$; fourth by commuting $a_n$ with the factor $(a_{\phi(k)}(a_{\phi(k+1)}\cdots a_{\phi(n-1)}))$, and fifth by general associativity.

Of course, then you'll want to do an induction on $n$ to finish the proof, having applied the first step to reduce the problem from a permutation of $\{1,\ldots,n\}$ to a permutation of $\{1,\ldots,n-1\}$ extended identically to $\{1,\ldots,n\}$...

-
Now that's what I'd call "expanding on a comment"! :-) – Asaf Karagila Oct 15 '11 at 21:46
Yes, Arturo. I did later notice that I wasn't really using the inductive hypothesis. I'm going to rewrite the proof. Thanks for taking the time to look through it! – Pedro Oct 15 '11 at 21:47