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

Summation over finite sets, definition

Let

X

be a set with

n \in N

elements and let

f : X \to 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 N : 1 \leq i \leq n}

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 N$ ), let $f : X \to R$ be a function, and let $g : {i \in N : 1 \leq i \leq n} \to X$ and $h : {i \in N : 1 \leq i \leq n} \to 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 \to X$ be the function $f (a) := 2$ , $f (b) := 5$ and $f (c) := - 1$ . Select a bijection $g : {1, 2, 3} \to 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}

17.11.2019