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?
$\endgroup$ 22 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$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.
$\endgroup$
