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

Fubini's theorem for finite series

Let

X

and

Y

be finite sets, and let

f : X \times Y \to R

be a function. Then

\begin{aligned} \sum_{x \in X} (\sum_{y \in Y} f (x, y)) & = \sum_{(x, y) \in X \times Y} f (x, y) \\ = \sum_{(y, x) \in Y \times X} f (x, y) \\ = \sum_{y \in Y} (\sum_{x \in X} f (x, y)) \end{aligned}

The proof isn't too involved. Most of the work is done by the lemma:

Lemma

Let

X

and

Y

be finite sets, and let

f : X \times Y \to R

be a function. Then

\sum_{x \in X} (\sum_{y \in Y} f (x, y)) = \sum_{(x, y) \in X \times Y} f (x, y)

Proof

Let $n$ be the number of elements in $X$ . We will induce on $n$ . Let $P (n)$ be the assertion that the lemma is true for any set $X$ with $n$ elements, and any finite set $Y$ and any function $f : X \times Y \to R$ . We wish to prove that $P (n)$ is true for all natural numbers $n$ .

The base case, $P (0)$ , is easy; it follows from the proposition that the sum over an empty set is zero.

Now suppose that $P (k)$ is true for some $k \in N$ ; we consider $P (k + 1)$ .

Let $X$ be a set with $k + 1$ elements. Write $X$ as $X = X^{'} \cup {x_{0}}$ , where $x_{0}$ is an element of $X$ . Using the 5^th of the 9 propositions on sums over finite sets:

\begin{aligned} \sum_{x \in X} (\sum_{y \in Y} f (x, y)) & = (\sum_{x \in X^{'}} (\sum_{y \in Y} f (x, y))) + (\sum_{y \in Y} f (x_{0}, y)) \\ By the induction hypothesis: \\ = \sum_{(x, y) \in X^{'} \times Y} f (x, y) + (\sum_{y \in Y} f (x_{0}, y)) \\ By the substitution proposition for sums over finite sets: \\ = \sum_{(x, y) \in X^{'} \times Y} f (x, y) + (\sum_{(x, y) \in {x_{0}} \times Y} f (x, y)) \\ by the proposition of sums over disjoint finite sets: \\ = \sum_{(x, y) \in X \times Y} f (x, y) \end{aligned}

Proving Fubini's theorem

The above lemma means we already know that both:

\sum_{x \in X} (\sum_{y \in Y} f (x, y)) = \sum_{(x, y) \in X \times Y} f (x, y)

and

\sum_{y \in Y} (\sum_{x \in X} f (x, y)) = \sum_{(y, x) \in Y \times X} f (x, y)

So it suffices to show that:

\sum_{(x, y) \in X \times Y} f (x, y) = \sum_{(y, x) \in Y \times X} f (x, y)

But this follows from the substitution proposition for sums over finite sets by choosing the bijection $h : X \times Y \to Y \times X$ defined by $h (x, y) = (y, x)$ .

17.11.2019