Show Question
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}