\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
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 \rightarrow R \) be a function. Then
\[ \begin{aligned}\sum_{x \in X}\left( \sum_{y \in Y}f(x,y) \right) &= \sum_{(x,y) \in X \times Y}f(x,y) \\&= \sum_{(y,x) \in Y \times X}f(x,y) \\&= \sum_{y \in Y} \left( \sum_{x \in X}f(x,y) \right)\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 \rightarrow \mathbb{R} \) be a function. Then
\[ \sum_{x \in X}\left( \sum_{y \in Y}f(x,y) \right) = \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 \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:

\[\begin{align*}
\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:

\[ \sum_{x \in X}\left( \sum_{y \in Y}f(x,y) \right) = \sum_{(x,y) \in X \times Y}f(x,y) \]

and

\[ \sum_{y \in Y}\left( \sum_{x \in X}f(x,y) \right) = \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 \rightarrow Y \times X \) defined by \( h(x,y) = (y,x) \).