I'm studying real analysis from the Terence Tao book. In Exercise 1.2.3. (iii) they ask the reader to prove subadditivity of Lebesgue outer measure. It mentions the proof should use the axiom of choice, Tonelli's theorem for series, and epsilon/2**n trick.

The proof I came up with used only tonelli's theorem, and seemed almost immediate. So there's probably something wrong with it...

given $\{E_n\}_{n=1}^\infty$ sets in $\mathbb{R}^d$

$m^*(\cup_{n=1}^\infty E_n) = \inf \sum_{n=1}^\infty |B_n|$ over all covers of $\cup_{n=1}^\infty E_n$ by a countable set of boxes $\{B_n\}_{n=1}^\infty$

Given any cover of each of individual sets $E_n$ by a sequence of boxes $\{B_{n,m}\}_{m=1}^\infty$, we have $\cup_{n=1}^\infty E_n \subseteq \cup_{n,m=1}^\infty B_{n,m}$ making it a cover included in the infimum above

Therefore $\inf \sum_{n=1}^\infty |B_n| \le \inf \sum_{n,m=1}^\infty |B_{n,m}| = \inf \sum_{n=1}^\infty \sum_{m=1}^\infty |B_{n,m}| = \sum_{n=1}^\infty m^*(E_n)$

The inequality is due to the right side infimum being over the same function but over a set contained in the one considered by the left side infimum.

The first equality is due to Tonelli's theorem for series.

The second equality is direct from the definition of $m^*$.

• I may have figured out why they mention the epsilon/2n trick... the second equality is not obvious because the infimum is outside the outer sum, but using the trick we can show we can select B(n,m)'s, for each n, to within epsilon/2n of m*(En), so the infimum is no more than the sum of m*'s, plus epsilon (for any epsilon>0) and that is why they are equal – yonil Sep 20 '13 at 21:46
• still no idea where the axiom of choice should be used, tho – yonil Sep 20 '13 at 21:52
• (A note for possible future readers:) As explicitly stated in the Xiao's answer below, you choose "any cover of each of individual sets" $E_n$. – kekkonen Jul 7 '14 at 20:28

I believe that in your argument $m^*(\cup_{n=1}^\infty E_n) = \inf\sum_{n=1}^\infty |B_n|$, the index isn't very clear.
To show $m^*(\cup_{n=1}^\infty E_n) \leq \sum_{n=1}^\infty m^*(E_n)$, it suffices to show that $m^*(\cup_{n=1}^\infty E_n) \leq \sum_{n=1}^\infty m^*(E_n) + \epsilon$ for each $\epsilon > 0$.
Let $\epsilon$ be given, for each $E_n$, define $\mathcal F_n$ to be the collection of countable collection of boxes (which means $\{B_{n,k}\}_{k\in \mathbb{N}} \in \mathcal{F}_n$) such that
1. $E_n \subset \cup_{k\in \mathbb{N}} B_{n,k}$,
2. $m^*(E_n) + \frac{\epsilon}{2^n} \geq \sum_{k\in \mathbb{N}} |B_{n,k}|$.
By Axiom of Choice, we take one $\{B_{n,k}\}_{k\in \mathbb{N}}$ from each $\mathcal F_n$, we see that by construction $\cup_{n=1}^\infty E_n \subset \cup_{(n,k) \in \mathbb{N}^2} B_{n,k}$, then \begin{align} m^*(\cup_{n=1}^\infty E_n) &\leq m^*(\cup_{(n,k) \in \mathbb{N}^2} B_{n,k})\\ &\leq \sum_{(n,k) \in \mathbb{N}^2} |B_{n,k}|\\ &= \sum_{n=1}^\infty \sum_{k=1}^\infty |B_{n,k}|\\ &\leq \sum_{n=1}^\infty (m^*(E_n) + \frac{\epsilon}{2^n} )\\ &\leq \sum_{n=1}^\infty m^*(E_n) + \epsilon \end{align}