Formal Definition of Summation over a Set

Formal definition of summation over a sequence is very clear. Suppose we have a sequence $$\left\{a_{i}\right\}_{0}^{\infty}$$. Then the summation of this sequence can be defined as a new sequence $$\left\{ b_i \right\}_0^\infty$$ in a recursive way:

$$b_0 = a_0,\ b_{i+1} = b_{i} + a_{i+1},\ i \geq 0.$$

Then we may write $$\sum_{i=0}^n a_i = b_n,$$

and

$$\sum_{i=0}^\infty a_i = \lim_{i\to\infty} b_i.$$

However, sometimes we see summation over a set. For example, in defining the determinant, we use the following notation:

$$\det(A) = \sum_{\sigma\in S_n} \left(\operatorname{sgn}(\sigma)\prod_{i=1}^n a_{i,\sigma_i}\right),$$

where $$S_n$$ is the set of all permutations of the sequence $$\left\{1,2,\dots,n\right\}$$. How are summation symbols over sets like $$\sum_{\sigma\in S_n}$$ formally defined?

• If you're okay with the idea of summing a set of numbers, you can - for example - define it for the determinant as the sum of the set $\{ \left(\operatorname{sgn}\left(\sigma\right)\prod_{i=1}^{n}a_{i,\sigma_{i}}\right) | \sigma \in S_{n}\}$. This idea can usually be used in most cases where a sum over a (finite!) set is presented. Dec 19, 2020 at 14:22
• We can only define a sum on sets on finite sets. In which case there is a mapping from the natural numbers to the elements of the set; that is to say the every $\sigma\in S$ may be labeled as $s_i$ for some $i\in \{0,....,n\}$. Therefore, as addition is commutative (and associative), we just add one step to the definition: $\sum_{\sigma\in S}\sigma=\sum_{s_i\in S} s_i=\sum_{i\in \{0,...,n\}}s_i=\sum_{i=0}^ns_i=b_n$ where $b_0=s_0$ and $b_{k+1}= b_k + s_{k+1}$. Dec 19, 2020 at 16:37

Assume that $$\lvert S \rvert = n$$. Then there is a bijection between the set $$\left\{1,2,\dots,n\right\}$$ and $$S$$. That is, there exists a mapping $$f: \left\{1,2,\dots,n\right\} \mapsto S$$ and the inverse $$f^{-1}: S \mapsto \left\{1,2,\dots,n\right\}$$ exists. Then we may write $$\sum_{s \in S}h_{s} = \sum_{i=1}^{n}h_{f_{i}},$$ where $$h: S \mapsto \mathbb{R}$$ is the sequence we'd like to sum. This definition incorporates the definition of determinants, as a bijection between permutations of the sequence $$\left\{1,2,\dots,n\right\}$$ and a subset of natural numbers always exists.

• One crucial observation is that the associativity & commutativity of addition ensures the choice of permutation is irrelevant, so your sum is well-defined.
– J.G.
Dec 19, 2020 at 17:46

The set in your example is finite.

Suppose you have an infinite set $$S$$ and you want to understand $$\sum_{i\in S} a_i.$$

If $$a_i\ge0$$ for all $$i$$ then one can define this sum as $$\sup \left\{ \sum_{i\in S_0} a_i : S_0\subseteq S \text{ and } S_0 \text{ is finite} \right\}.$$

One can do a similar thing if every term is negative. Then if some are positive and some are negative, you have a well defined sum unless both sums are infinite.