Addition and Multiplication Independent of Permutations

45 Views Asked by At

Note: In this discussion, $0$ is included in $\mathbb{N}$.

In Chapter 1, Section 5.13 (a) from Analysis I by Amann and Escher, there is the following statement:

...

If addition $+$ and multiplication $\cdot$ are commutative, we have

$\displaystyle\sum_{k=0}^{n}x_{k}=\sum_{j=0}^{n}x_{\sigma{(j)}}$ and $\displaystyle\prod_{k=0}^{n}x_{k}=\prod_{j=0}^{n}x_{\sigma{(j)}}$

for any permutation $\sigma$ of the numbers $0,\cdots ,n$, that is, for any bijective function $\sigma :\{0,\cdots ,n\}\to\{0,\cdots ,n\}$.

This was stated without proof. However, it does not appear to be that obvious to me at least.

Before this statement, it has previously been proved that if $\odot$ is an associative operation on a set $X$, the value of any valid expression involving $\odot$, elements of $X$ and parentheses, is independent of the placement of parentheses.

In addition, for an associative operation on some set $X$ and with $x_{k}\in X$ for all $k\in\mathbb{N}$, it is possible to give a recursive definition for the expression:

$\displaystyle\bigodot_{k=0}^{n}x_{k}$

This is achieved by the following definitions:

$\displaystyle\bigodot_{k=0}^{0}x_{k}=x_{0}$

$\displaystyle\bigodot_{k=0}^{n+1}x_{k}=\left(\bigodot_{k=0}^{n}x_{k}\right)\odot x_{n+1}$

My idea is to prove the original statement is to deal with a more general case where $\odot$ is both an associative and a commutative operation on $X$.

This is proved by induction on $n$. For $n=1$, $x_{0}\odot x_{1}=x_{1}\odot x_{0}$ because $\odot$ is a commutative operation, and this covers all permutations of $\{0,1\}$.

Now suppose that this property holds for some $n\geq 1$ and let $\sigma$ be a permutation of $\{0,\cdots ,n+1\}$. Then there exists some unique $\ell\in\{0,\cdots ,n+1\}$ such that $\sigma{(\ell)}=n+1$.

If $\ell\in\mathbb{N}^{\times}$ where $\mathbb{N}^{\times}$ is defined as $\mathbb{N}\setminus\{0\}$, $\ell =\ell^{'}+1$ for some $\ell^{'}\in\mathbb{N}$.

In addition, letting $\sigma^{'}$ be defined by $\sigma^{'}(k)=\sigma{(k)}$ for $0\leq k<\ell$ and $\sigma^{'}(k)=\sigma{(k+1)}$ for $\ell\leq k\leq n$ defines a permutation on $\{0,\cdots ,n\}$.

Then expanding the following expression from definition:

$\displaystyle\bigodot_{k=0}^{n+1}x_{\sigma{(k)}}=\left(\cdots\left(\left(\bigodot_{k=0}^{\ell^{'}}x_{\sigma{(k)}}\right)\odot x_{\sigma{(\ell)}}\right)\odot\cdots\right)\odot x_{\sigma{(n+1)}}$

Applying that $\odot$ is a commutative operation and that $\bigodot_{k=0}^{\ell^{'}}x_{\sigma{(k)}}$ is in $X$:

$\displaystyle =\left(\cdots\left(x_{\sigma{(\ell)}}\odot\left(\bigodot_{k=0}^{\ell^{'}}x_{\sigma{(k)}}\right)\right)\odot\cdots\right)\odot x_{\sigma{(n+1)}}$

As this is a valid expression involving elements of $X$, parentheses and an associative operation $\odot$, the order of the brackets can be changed without affecting the value:

$\displaystyle =x_{\sigma{(\ell)}}\odot\left(\left(\cdots\left(\bigodot_{k=0}^{\ell^{'}}x_{\sigma{(k)}}\right)\odot\cdots\right)\odot x_{\sigma{(n+1)}}\right)$

Again applying that $\odot$ is commutative:

$\displaystyle =\left(\left(\cdots\left(\bigodot_{k=0}^{\ell^{'}}x_{\sigma{(k)}}\right)\odot\cdots\right)\odot x_{\sigma{(n+1)}}\right)\odot x_{\sigma{(\ell)}}$

Replacing the terms with $\sigma{(k)}$ in terms of their corresponding expression with $\sigma^{'}$ combined with applying that $\sigma{(\ell)}=n+1$:

$\displaystyle =\left(\left(\cdots\left(\bigodot_{k=0}^{\ell^{'}}x_{\sigma^{'}{(k)}}\right)\odot\cdots\right)\odot x_{\sigma^{'}{(n)}}\right)\odot x_{n+1}$

Applying the definition of $\bigodot$:

$\displaystyle =\left(\bigodot_{k=0}^{n}x_{\sigma^{'}{(k)}}\right)\odot x_{n+1}$

Applying the induction hypothesis and using the definition of $\bigodot$ again:

$\displaystyle =\left(\bigodot_{k=0}^{n}x_{k}\right)\odot x_{n+1}=\bigodot_{k=0}^{n+1}x_{k}$

This deals with the case $\ell\in\mathbb{N}^{\times}$. If $\ell =0$, giving $\sigma^{'}$ the same definition as above, the chain of equalities with the same justification as above give:

$\displaystyle\bigodot_{k=0}^{n+1}x_{\sigma{(k)}}=\left(\cdots\left(x_{\sigma{(0)}}\odot x_{\sigma{(1)}}\right)\odot\cdots\right)\odot x_{\sigma{(n+1)}}$

$=x_{\sigma{(0)}}\odot\left(\left(\cdots\left(x_{\sigma{(1)}}\odot x_{\sigma{(2)}}\right)\odot\cdots\right)\odot x_{\sigma{(n+1)}}\right)$

$=\left(\left(\cdots\left(x_{\sigma{(1)}}\odot x_{\sigma{(2)}}\right)\odot\cdots\right)\odot x_{\sigma{(n+1)}}\right)\odot x_{\sigma{(0)}}$

$=\left(\left(\cdots\left(x_{\sigma^{'}{(0)}}\odot x_{\sigma^{'}{(1)}}\right)\odot\cdots\right)\odot x_{\sigma^{'}{(n)}}\right)\odot x_{n+1}$

$\displaystyle =\left(\bigodot_{k=0}^{n}x_{\sigma^{'}{(k)}}\right)\odot x_{n+1}=\left(\bigodot_{k=0}^{n}x_{k}\right)\odot x_{n+1}=\bigodot_{k=0}^{n+1}x_{k}$

I was wondering, as no proof was given, if there is a shorter argument that gives the result above?