Math and science::Analysis::Tao::07. Series

Summation over finite sets, definition

Let \( X \) be a set with \( n \in \mathbb{N} \) elements and let \( f: X \rightarrow \mathbb{N} \) be a function from \( X \) to the real numbers. Then we define the finite sum \( \sum_{x \in X} f(x) \) as follows.

Select any bijection \( g \) from \( \{i \in \mathbb{N} : 1 \le i \le n \} \) to \( X \). Such a bijection exists since \( X \) is assumed to have \( n \) elements. We then define:

\[ \sum_{x \in X} f(x) := \sum_{i=1}^{n}f(g(i)) \]

While this is just a definition, we still need to check that it creates a valid identity that is consistent with the requirements of equality. Specifically, the requirements of the substitution axiom must be met. Our definition allows for freedom to choose a bijection, so we must insure that any such choice of bijection produces a sum equal to a sum produced from another bijection. This is somewhat more involved that one might expect.

The proof of the following proposition is a good example of a non-obvious induction setup (induction over the size of a set is used). Refer to the book for the proof, as it is symbolically involved.

Proposition, finite summations are well-defined

Let \( X \) be a finite set with \( n \) elments (where \( n \in \mathbb{N} \)), let \( f: X \rightarrow \mathbb{R} \) be a function, and let \( g: \{i \in \mathbb{N} : 1 \le i \le n \} \rightarrow X \) and \( h: \{i \in \mathbb{N} : 1 \le i \le n \} \rightarrow X \) be bijections. Then we have

\[ \sum_{i=i}^{n}f(g(i)) = \sum_{i=2}^{n}f(h(i)) \]

Example

Let \( X \) be the set \( X := \{a, b, c\} \). Let \( f:X \rightarrow X \) be the function \( f(a) := 2 \), \( f(b) := 5 \) and \( f(c) := -1 \). Select a bijection \( g: \{1, 2, 3\} \rightarrow X \), for example \( g(1) := a \), \( g(2) := b \) and \( g(3) := c \). Then we have:

\[
\begin{aligned}
\sum_{x \in X}f(x) &= \sum_{i=1}^{3}f(g(i)) \\
&= f(a) + f(b) + f(c) \\
&= 6
\end{aligned} \]