4
$\begingroup$

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$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tom Ariel
    Dec 19, 2020 at 14:22
  • 2
    $\begingroup$ 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}$. $\endgroup$
    – fleablood
    Dec 19, 2020 at 16:37

2 Answers 2

2
$\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
  • 2
    $\begingroup$ One crucial observation is that the associativity & commutativity of addition ensures the choice of permutation is irrelevant, so your sum is well-defined. $\endgroup$
    – J.G.
    Dec 19, 2020 at 17:46
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$

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.