6

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?

Michael Hardy
  • 1
Ziqi Fan
  • 1,816
  • 2
    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. – Tom Ariel Dec 19 '20 at 14:22
  • 2
    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}$. – fleablood Dec 19 '20 at 16:37

2 Answers2

4

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.

Ziqi Fan
  • 1,816
  • 2
    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 '20 at 17:46
1

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.

Michael Hardy
  • 1