Say I have a finite ordered set $X=\{x_1,x_2,x_3...\}$ (not necessarily containing numbers), and we have an addition $+$ defined on this set (commutative and associative). We can define the sum of the elements of this set, $\sum X$ as follows:

  • $\sum_{i=a}^b x_i=\left\{\begin{array}{c}x_a, a=b\\x_b+\sum_{i=a}^{b-1}x_n,a<b\end{array}\right.$
  • $\sum X = \sum_{i=1}^{|X|}x_i$

Now consider an unordered set $Y$. How would I go about defining $\sum Y$? Since there is no notion of order, I can't give a rigorous definition of which value to add first.

Thank you.

  • $\begingroup$ If $+$ is commutative then you can choose any order you want, if $+$ is not commutative then $\sum Y$ is ill-defined. $\endgroup$ – Najib Idrissi Nov 9 '16 at 12:30
  • $\begingroup$ $+$ is both commutative and associative, so there's no issue there. In a rigorous definition can I then just say that $\sum Y$ is the recursive addition of elements of $Y$ in any order? $\endgroup$ – Disousa Nov 9 '16 at 12:33

You can choose any linear order on $Y$ (which exists because $Y$ is finite), say for example $Y = \{ y_1, \dots, y_n \}$, and compute $\sum Y$ using this order. Since $+$ is commutative and associative, then any two orderings of $Y$ will give the same result, and so you get a well-defined element which you can call $\sum Y$.

To see that this is independent from the chosen ordering on $Y$. Another ordering on $Y$ is given by a permutation $\sigma \in \Sigma_n$, by considering $Y = \{ y_{\sigma(1)}, \dots, y_{\sigma(n)}\}$. The symmetric group is generated by transpositions, so it essentially suffices to prove: $$x + (y + z) = (x + y) + z = (y + x) + z = y + (x + z)$$ so you can swap two consecutive elements, and therefore start from any ordering of $Y$ and end up on any other one.

If $+$ is not commutative and associative however, there's no way of giving a proper meaning to the expression "$\sum Y$" if $Y$ isn't ordered.

  • $\begingroup$ I wonder if it's also useful to point out explicitly that the finiteness condition is required. $\endgroup$ – MJD Nov 9 '16 at 14:08

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.