Fubini's theorem for finite series
Let \( X \) and \( Y \) be finite sets, and let \( f: X \times Y \rightarrow R \) be a function. Then
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 \rightarrow \mathbb{R} \) be a function. ThenProof
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 \rightarrow \mathbb{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 \mathbb{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 5th of the 9 propositions on sums over finite sets:
\sum_{x \in X} \left( \sum_{y \in Y}f(x,y) \right) &= \left( \sum_{x \in X'} \left( \sum_{y \in Y}f(x,y) \right) \right) + \left( \sum_{y \in Y}f(x_0,y) \right) \\
\text{By the induction hypothesis:} \\
&= \sum_{(x,y) \in X' \times Y} f(x,y) + \left( \sum_{y \in Y} f(x_0, y) \right)\\
\text{By the substitution proposition for sums over finite sets:} \\
&= \sum_{(x,y) \in X' \times Y} f(x,y) + \left( \sum_{(x,y) \in \{x_0\} \times Y} f(x, y) \right) \\
\text{by the proposition of sums over disjoint finite sets:} \\
&= \sum_{(x,y) \in X \times Y} f(x,y)\end{align*}\]
Proving Fubini's theorem
The above lemma means we already know that both:
and
So it suffices to show that:
But this follows from the substitution proposition for sums over finite sets by choosing the bijection \( h: X \times Y \rightarrow Y \times X \) defined by \( h(x,y) = (y,x) \).