0
$\begingroup$

I am pretty new to reasoning rigorously and right now I'm at the stage of trying to understand a lot of already known material in a more rigorous way. If $A$ is a finite set and $g:A\to A$ is a bijection, then for any function $f:A\to\mathbb{R}$ it is intuitively obvious that $$\sum_{a\in A}f(a)=\sum_{a\in A}f(g(a)),$$ because you are just permuting the terms of the sum. However, how would I prove this property rigorously, assuming just some relevant properties of real addition like commutativity, and perhaps some more if needed. I don't even know formally how the sum over $A$ would be defined. The only rigorous definition of summation is when you sum between two natural numbers, like this $$\sum_{i=a}^b x_i:=\begin{cases}0\quad\text{if $a>b$};\\x_a+\sum_{i=a+1}^b x_i\quad\text{if $a\leq b$}.\end{cases}$$

Am I reading too much into this? Most people, reading around, seem to be fine with just accepting that the first equation holds simply because you are just changing the order of the terms, but I feel like this is not a rigorous argument.

$\endgroup$
  • 1
    $\begingroup$ You can prove it using your definition of the summation symbol, by induction on the size of $A$. $\endgroup$ – Antoine Apr 11 '17 at 11:37
  • 1
    $\begingroup$ If $A$ has two elements then this is just the commutativity of addition in $\Bbb{R}$. For larger sets, an argument using induction may work. Assume that it is true for sets of size up to $n$ and then try to prove it for size $n + 1$. $\endgroup$ – badjohn Apr 11 '17 at 11:37
2
$\begingroup$

As soon as you write $\sum\limits_{a\in A}$ instead of the $\sum\limits_{i=a}^b$ notation, you have already assumed the property you're trying to prove -- because that is your guarantee that $\sum\limits_{a\in A}$ does not depend on which order you take the elements of $A$ in.

So what you really ought to prove first is that if $g$ is any permutation of $\{1,2,\ldots,n\}$, then $$ \sum_{i=1}^n f(i) = \sum_{i=1}^n f(g(i)) $$ In order to do this, you need to develop enough permutation theory to show that $g$ is a product of neighbor-transpositions, and then show that a single neighbor-transposition does not change the finite sum (which is then a matter of using the commutative law in an appropriate step of the inductive definition).

After proving this, you can argue that it is meaningful to define $$ \sum_{a\in A} f(a) = \sum_{i=1}^n f(h(i)) $$ where $h$ is an arbitrary bijection $\{1,2,\ldots,n\} \to A$. Knowing that the sum is invariant under permutations will then tell you that it is immaterial which bijection you choose.

$\endgroup$
  • $\begingroup$ I don't think it's necessary to show that transpositions span $S_n$. Showing that transpositions don't change the value of the sum will be necessary, but just using the associative law, an induction argument and a composition with a transposition will suffice $\endgroup$ – Maxime Ramzi Apr 11 '17 at 12:22
  • $\begingroup$ @Max: If you don't know that the arbitrary $g$ is a product of transpositions, then what will knowing that that "transpositions don't change the sum" help you? $\endgroup$ – hmakholm left over Monica Apr 11 '17 at 12:31
  • $\begingroup$ You want to show by induction that $\displaystyle\sum_{i=0}^n f(i) = \displaystyle\sum_{i=0}^n f(g(i))$. The base case, $n=0$ is trivial. To go from $n\to n+1$, you can compose $g$ with the transposition $(n+1, g(n+1))$ to get $h$ and you know that this doesn't change the sum so $\displaystyle\sum^{n+1} f(g(i)) = \displaystyle\sum^{n+1} f(h(i))$. But $n+1$ is a fixed point of $h$, so that gives you $\displaystyle\sum^{n+1} f(g(i)) = (\displaystyle\sum^n f(h(i))) + f(n+1)$ (here you use the associative property). Then by induction hypothesis, you can replace $\displaystyle\sum^n f(h(i))$ $\endgroup$ – Maxime Ramzi Apr 11 '17 at 13:02
  • $\begingroup$ with $\displaystyle\sum^n f(i)$ since essentially $h$ is a permutation on $n$ elements. And you can thus conclude by induction $\endgroup$ – Maxime Ramzi Apr 11 '17 at 13:03
  • $\begingroup$ @Max: That amounts to proving the necessary facts about transpositions and permutations all while denying that you're proving them. $\endgroup$ – hmakholm left over Monica Apr 11 '17 at 13:19
1
$\begingroup$

It is a rigorous argument and on the other hand, it is not.

You already found the problem and the answer when you said:

I don't even know formally how the sum over A would be defined.

The sum over a set $A$ is defined as evaluating the expression for every $a \in A$ and then building the sum of them all. As a set comes without ordering, this is only well defined if the value of the sum does not change under the rearrangement of terms.

Thus, by writing a sum over $A$, you are already assuming that it does not depend on the order of elements. If $A$ is a finite set and $f$ maps it to a set where we have a commutative and associative addition, then you can show that indeed, the sum does not change when reordering. As almost all common sets (natural numbers, reel numbers, complex numbers, matrices, polynomials,...) have this kind of addition, you can almost always simply accept that fact.

However, you are right to question it, as it is not always true. For example you can run into big problems if your set $A$ gets infinite. There are many videos on youtube where it is shown that sum infinite sum (here $A = \mathbb{N}$ is the set of natural numbers) has one value or an other, simply by rearranging the terms. One thing you learn rather early when considering such sums is that under certain conditions, you can get almost any value just by rearranging; and surely also different ones.

So long story short: If you write $\sum_{a \in A}$, you are assuming that reordering doesn't change anything; otherwise this sum is not well defined. Reordering is almost always ok if $A$ is a finite set, but with infinite sets you really need to be careful.

$\endgroup$
0
$\begingroup$

Just now I provided a proof outline for why permutations have the same sum here: Prove the sum $\sum_{i=1}^n a_{\sigma_i}$ computed over all permutations σ of the set {1, 2, …, n} remains unchanged.

Let $(1, 2, ..., n)$ be the order we'd normally find $a_i$ in and $(\sigma1, \sigma2, ..., \sigma n)$ the order after our permutation has been applied. Then let $\sigma j$ correspond with $1$. If we now exchange $\sigma j$ and $\sigma(j-1)$, we'll keep the same sum (addition is commutative). Therefore, we can move $\sigma j$ to the first place in $j-1$ steps and get a new permutation which has the same sum. We can then repeat this process for all terms to "revert" the permutation made and end up with our original sum.

Therefore it must be that $$\sum_i a_i=\sum_i a_{\sigma i}$$

To make it fully rigorous, one would have to define the field, or ring, or group over which you're summing and let $1\leq j\leq n$.

When it comes to the question about the sums definition: It just means "the sum of all $a:a\in A$"

$\endgroup$

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.