A constructive proof of the Vitali Covering Lemma

Theorem:

Let $\{B_i\}_{i=1}^n$ be a finite collection of balls in $\mathbb{R}^d$. Then there exists a sub-collection of balls $\{B_{j_i}\}_{i=1}^m$ that are disjoint and satisfy:

\begin{equation} \bigcup_{i=1}^n B_i \subseteq \bigcup_{i=1}^m 3 \cdot B_{j_i} \end{equation}

Demonstration:

Let’s define:

\begin{equation} \mathcal{B_1} := \bigcup_{i=1}^n B_i \end{equation}

such that we re-index $B_i$ so we have:

\begin{equation} \mathcal{B_{1,1}} := B_1 \end{equation}

\begin{equation} Vol(\mathcal{B_{1,i}}) \geq Vol(\mathcal{B_{1,i+1}}) \end{equation}

and given $\mathcal{B_1}$ we may define:

\begin{equation} C_1 = \{\mathcal{B_{1,j}}: \mathcal{B_{1,j}} \cap \mathcal{B_{1,1}} \neq \emptyset \} \end{equation}

so we have:

\begin{equation} C_1 \subseteq 3 \cdot \mathcal{B_{1,1}} \end{equation}

Now, using $\mathcal{B_i}$ and $C_i$ we may construct the following:

\begin{equation} \mathcal{B_{i+1}} = \mathcal{B_i} \setminus C_i \end{equation}

\begin{equation} \lvert \mathcal{B_{i+1}} \rvert < \lvert \mathcal{B_{i}} \rvert \end{equation}

\begin{equation} Vol(\mathcal{B_{i,j}}) > Vol(\mathcal{B_{i,j+1}}) \end{equation}

and by induction we have:

\begin{equation} \bigcup_{i=1}^n B_i \subseteq \bigcup_{j=1}^m 3 \cdot \mathcal{B_{j,1}} \end{equation}

where $m$ is the smallest integer such that $\lvert \mathcal{B_{m+1}} \rvert = 0$.