# User:Tkojar/Sandbox/Vitali Covering Lemma

This article needs to be tidied.In particular: Copypasted from Wikipedia, so needs to be restyledPlease fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Tidy}}` from the code. |

This article needs to be linked to other articles.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{MissingLinks}}` from the code. |

This page has been identified as a candidate for refactoring.Until this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

## Theorem

- Finite version: Let $ B_{1}, \ldots, B_{n}$ be any finite collection of balls contained in d-dimensional $\mathbb{R}^{d}$ (or, more generally, in an arbitrary metric space) then there exists a subcollection $ B_{j_1}, B_{j_2}, \dots, B_{j_m} $ of these balls which are disjoint and satisfy

- $B_1 \cup B_2 \cup \cdots \cup B_n \subseteq 3 B_{j_1} \cup 3 B_{j_2} \cup \cdots \cup 3 B_{j_m}$

- where $3 B_{j_k}$ denotes the ball with the same center as $B_{j_k}$ but with three times the radius.

- Infinite version: Let $\set {B_j: j \in J}$ be an arbitrary collection of balls in $\R^d$ (or, more generally, in a separable metric space) such that

- $\sup \set {\map {\mathrm {rad} } {B_j} : j \in J } < \infty$

- where $\map {\mathrm {rad} } {B_j}$ denotes the radius of the ball $B_j$. Then there exists a countable subcollection

- $\set {B_j: j \in J'}, \quad J' \subset J$

- of balls from the original collection which are disjoint and satisfy

- $\ds \bigcup_{j \mathop \in J} B_j \subseteq \bigcup_{j \mathop \in J'} 5 B_j$

## Proof of finite version

Without loss of generality, we assume that the collection of balls is not empty; that is $n > 0$.

Let $B_{j_1}$ be the ball of largest radius.

Inductively, assume that $B_{j_1}, \dots, B_{j_k}$ have been chosen.

If there is some ball in $B_1, \ldots, B_n$ that is disjoint from $B_{j_1} \cup B_{j_2} \cup \cdots \cup B_{j_k}$, let $B_{j_{k + 1} }$ be such ball with maximal radius (breaking ties arbitrarily).

Otherwise, we set $m := k$ and terminate the inductive definition.

Now set $\ds X := \bigcup_{k\mathop = 1}^m 3 B_{j_k}$.

It remains to show that $B_i \subset X$ for every $i = 1, 2, \ldots, n$.

This is clear if $i \in \set {j_1,\dots, j_m}$.

Otherwise, there necessarily is some $k \in \set {1, \ldots, m}$ such that $B_i$ intersects $B_{j_k}$ and the radius of $B_{j_k}$ is at least as large as that of $B_i$.

The triangle inequality then easily implies that $B_i \subset 3 B_{j_k} \subset X$, as needed.

This completes the proof of the finite version.

## Proof of infinite version

Let $F$ denote the collection of all balls $B_j$, $j \in J$, that are given in the statement of the *covering lemma*.

The following result provides a certain disjoint subcollection $G$ of $F$.

If this subcollection $G$ is described as $\set {B_j, j \in J'}$, the property of $G$, stated below, readily proves that

- $\bigcup_{j \mathop \in J} B_j \subseteq \bigcup_{j \mathop \in J'} 5 B_j$

Precise form of the covering lemma: Let $F$ be a collection of (nondegenerate) balls in a metric space, with bounded radii. There exists a disjoint subcollection $G$ of $F$ with the following property:

*every ball $B$ in $F$ intersects a ball $C$ in $G$ such that $B \subset C$*

(*Degenerate balls* only contain the center; they are excluded from this discussion.)

Let $R$ be the supremum of the radii of balls in $F$.

Consider the partition of $F$ into subcollections $F_n$, $n \ge 0$, consisting of balls $B$; whose radius is in $\hointl {\dfrac R {2^{n + 1} } } {\dfrac R {2^n} }$.

A sequence $G_n$, with $G_n \subset F_n$ is defined inductively as follows.

First, set $H_0 = F_0$ and let $G_0$ be a maximal disjoint subcollection of $H_0$.

Assuming that $G_0, \ldots, G_n$ have been selected, let

- $\mathbf H_{n + 1} = \set {B \in \mathbf F_{n + 1}: B \cap C = \O, \forall C \in \mathbf G_0 \cup \mathbf G_1 \cup \ldots \cup \mathbf G_n}$

and let $G_{n + 1}$ be a maximal disjoint subcollection of $H_{n + 1}$.

The subcollection

- $\ds \mathbf G := \bigcup_{n \mathop = 0}^\infty \mathbf G_n$

of $F$ satisfies the requirements: $G$ is a disjoint collection, and every ball $B \in F$ intersects a ball $C \in G$ such that $B \subset 5 C$.

Indeed, let $n$ be such that $B$ belongs to $F_n$.

Either $B$ does not belong to $H_n$, which implies $n > 0$ and means that $B$; intersects a ball from the union of $G_0, \ldots, G_{n - 1}$ or $B \in H_n$ and by maximality of $G_n$ $B$ intersects a ball in $G_n$.

In any case, $B$ intersects a ball $C$ that belongs to the union of $G_0, \ldots, G_n$.

Such a ball C has radius $ > \dfrac R {2^{n + 1} }$.

Since the radius of $B$ is $\le \dfrac R {2^n}$, it is less than twice that of $C$ and the conclusion $B\subset C$ follows from the triangle inequality as in the finite version.

$\blacksquare$

## Source of Name

This entry was named for Giuseppe Vitali.