# What is the definition of the sum of an unordered set?

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.

• If $+$ is commutative then you can choose any order you want, if $+$ is not commutative then $\sum Y$ is ill-defined. – Najib Idrissi Nov 9 '16 at 12:30
• $+$ 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? – Disousa Nov 9 '16 at 12:33

## 1 Answer

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.

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