Vitali's Theorem

Let $\mathcal{S}$ be a collection of sets. A point x is said to be Vitali covered by $\mathcal{S}$ if for all $\epsilon>0$ there exists $S\in\mathcal{S}$ such that $x\in S$ and the diameter of S is less than $\epsilon$. The Vitali Covering Theorem in its simplest form says the following: if $\mathcal{I}$ is a sequence of intervals which Vitali covers an interval E in the real line, then $\mathcal{I}$ contains a countable, pairwise disjoint set of intervals I_n, $n\in\mathbb{N}$, such that $\bigcup_{n=0}^\infty I_n$ covers E except for a set of Lebesgue measure 0.

The purpose of this section is to show that various forms of the Vitali Covering Theorem are provable in $\mathsf{WWKL}_0$ and in fact equivalent to WWKL over $\mathsf{RCA}_0$.

Throughout this section, we use $\mu$ to denote Lebesgue measure.

Lemma 5.1 (Baby Vitali Lemma)   The following is provable in $\mathsf{RCA}_0$. Let $I_0,\dots,I_n$ be a finite sequence of intervals. Then we can find a pairwise disjoint subsequence $I_{k_0},\dots,I_{k_m}$ such that

$$\mu(I_{k_0}\cup\dots\cup I_{k_m}) \,\,\geq\,\, \frac13\, \mu(I_0\cup\dots\cup I_n) \,\,.$$

Proof. Put $N=\{0,\dots,n\}$. By bounded $\Sigma^0_1$ comprehension in $\mathsf{RCA}_0$, the finite sets

$$\{\,(i,j)\in N^2\mid I_i\cap I_j=\emptyset\,\}$$

and

$$\{\,(i,j)\in N^2\mid\mu(I_i)\leq\mu(I_j)\,\}$$

exist. Using these finite sets as parameters, we can carry out the following primitive recursion within $\mathsf{RCA}_0$. Begin by letting $k_0\leq n$ be such that $\mu(I_{k_0})$ is as large as possible. Then let k₁ be such that $I_{k_1}\cap I_{k_0}=\emptyset$ and $\mu(I_{k_1})$ is as large as possible. At stage j, let k_j be such that $I_{k_j}\cap I_{k_0}=\emptyset$, ..., $I_{k_j}\cap I_{k_{j-1}}=\emptyset$ and $\mu(I_{k_j})$ is as large as possible. The recursion ends with a finite, pairwise disjoint sequence of intervals I_k0, ..., I_km such that

$$\forall i\leq n\,\, \exists j\leq m\,\, [\, I_i\cap I_{k_j}\,\neq\,\emptyset \,] \,\,.$$

By construction it follows easily that

$$\forall i\leq n\,\, \exists j\leq m\,\, [\, I_i\cap I_{k_j}\... ...,\emptyset\mbox{ and } \mu(I_i)\,\leq\,\mu(I_{k_j}) \,] \,\,.$$

For any such i and j, we have $I_i\subseteq I'_{k_j}$, where I'_kj is an interval with the same midpoint as I_kj and 3 times as long. (If I=[a,b], then I'=[2a-b,2b-a].) Thus

$$\begin{eqnarray*}\mu(I_0\cup\dots\cup I_n) & \leq & \mu(I'_{k_0}\cup\dots\cup I... ...u(I_{k_m}) \\ [3pt] & = & 3\,\mu(I_{k_0}\cup\dots\cup I_{k_m}) \end{eqnarray*}$$

and the lemma is proved.

Lemma 5.2   The following is provable in $\mathsf{WWKL}_0$. Let E be an interval, and let I_n, $n\in\mathbb{N}$, be a sequence of intervals. If $E\subseteq\bigcup_{n=0}^\infty I_n$, then

$$\mu(E)\,\,\leq\,\,\lim_{k\to\infty}\,\mu\!\left(\,\bigcup_{n=0}^k I_n\!\right) \,\,.$$

Proof. If the intervals I_n are open, then the desired conclusion follows immediately from countable additivity (Theorem 3.3). Otherwise, fix $\epsilon>0$ and let I'_n be an open interval with the same midpoint as I_n and

$$\mu(I'_n)\,\,=\,\,\mu(I_n)+\frac\epsilon{2^n} \,\,.$$

Then by countable additivity we have

$$\mu(E) \,\,\leq\,\, \lim_{k\to\infty}\,\mu\!\left(\,\bigcup_... ...\,\mu\!\left(\,\bigcup_{n=0}^k I_n\!\right) + 2\epsilon \,\,.$$

Since this holds for all $\epsilon>0$, the desired conclusion follows.

Lemma 5.3 (Vitali theorem for intervals)   The following is provable in $\mathsf{WWKL}_0$. Let E be an interval, and let $\mathcal{I}$ be a sequence of intervals which is a Vitali covering of E. Then $\mathcal{I}$ contains a pairwise disjoint sequence of intervals I_n, $n\in\mathbb{N}$, such that

$$\mu\!\left(\!E\setminus\bigcup_{n=0}^\infty I_n\!\right) = 0 \,\,.$$

Proof. We reason in $\mathsf{WWKL}_0$. Without loss of generality, let us assume that $\mathcal{I}$ consists of closed intervals. Let $\mathcal{I}^{*}$ be the set of finite unions $I_1\cup\dots\cup I_k$ where $I_1,\dots,I_k$ are pairwise disjoint intervals from $\mathcal{I}$. We claim: Given $A\in\mathcal{I}^{*}$, if $\mu(E\setminus A)>0$ then we can find $B\in\mathcal{I}^{*}$ such that $A\cap B=\emptyset$ and

$$\mu(E\setminus(A\cup B)) \,\,<\,\, \frac34 \,\mu(E\setminus A) \,\,.$$ (3)

To prove the claim, use Lemma 5.2 and the Vitali property to find a finite set of intervals $J_1,\dots,J_l\in\mathcal{I}$ such that $J_1,\dots,J_l\subseteq E\setminus A$ and

$$\mu\left(E\setminus(A\cup J_1\cup\dots\cup J_l\right)) \,\,<\,\, \frac1{12} \,\mu(E\setminus A) \,\,.$$

By the Baby Vitali Lemma 5.1, we can find a pairwise disjoint subset $\{I_1,\dots,I_k\}\subseteq\{J_1,\dots,J_l\}$ such that

$$\mu(I_1\cup\dots\cup I_k) \,\,\ge\,\, \frac13 \,\mu(J_1\cup\dots\cup J_l) \,\,.$$

We then have

$$\begin{eqnarray*}\lefteqn{\mu(E\setminus(A\cup I_1\cup\dots\cup I_k))} \quad \\ ... ...12} \,\mu(E\setminus A) \\ & = & \frac34 \,\mu(E\setminus A) \end{eqnarray*}$$

Thus we may take $B=I_1\cup\dots\cup I_k$ and our claim is proved.

Note that the predicates $A\cap B=\emptyset$ and (3) are $\Sigma^0_1$. Thus within $\mathsf{RCA}_0$ we can apply our claim recursively to choose a pairwise disjoint sequence $A_0=\emptyset$, A₁, A₂, ...of sets in $\mathcal{I}^{*}$ such that for all $n\ge1$,

$$\mu(E\setminus(A_1\cup\dots\cup A_n)) \,\,<\,\, \left(\frac34\right)^n \mu(E) \,\,.$$

Then by countable additivity we have

$$\mu\!\left(\!E\setminus\bigcup_{n=1}^\infty A_n\!\right) \,\,=\,\, 0$$

and the lemma is proved.

Remark 5.4   It is straightforward to generalize the previous lemma to the case of a Vitali covering of the n-cube [0,1]ⁿ by closed balls or n-dimensional cubes. In the case of closed balls, the constant 3 in the Baby Vitali Lemma 5.1 is replaced by 3ⁿ.

Theorem 5.5   The Vitali theorem for the interval [0,1] (as stated in Lemma 5.3) is equivalent to WWKL over $\mathsf{RCA}_0$.

Proof. Lemma 5.3 shows that, in $\mathsf{RCA}_0$, WWKL implies the Vitali theorem for intervals. It remains to prove within $\mathsf{RCA}_0$ that the Vitali theorem for [0,1] implies WWKL. Instead of proving WWKL, we shall prove the equivalent statement 3.3.3. Reasoning in $\mathsf{RCA}_0$, suppose that (a_n,b_n), $n\in\mathbb{N}$, is a sequence of open intervals which covers [0,1]. Let $\mathcal{I}$ be the countable set of intervals

$$(a_{nki},b_{nki}) \,\,=\,\, \left(a_n+\frac{i}{k}(b_n-a_n)\,,\,\, a_n+\frac{i+1}{k}(b_n-a_n)\right)$$

where $i,k,n\in\mathbb{N}$ and $0\le i<k$. Then $\mathcal{I}$ is a Vitali covering of [0,1]. By the Vitali theorem for intervals, $\mathcal{I}$ contains a sequence of pairwise disjoint intervals I_m, $m\in\mathbb{N}$, such that

$$\mu\!\left(\,\bigcup_{m=0}^\infty I_m\!\right)\,\,\geq\,\,1\,\,.$$

By disjoint countable additivity (Corollary 2.5), we have

$$\sum_{m=0}^\infty\,\mu(I_m)\,\,\geq\,\,1\,\,.$$

From this it follows easily that $\sum_{n=0}^\infty\vert a_n-b_n\vert\geq1$. Thus we have 3.3.3 and our theorem is proved.

We now turn to Vitali's theorem for measurable sets. Recall our discussion of measurable sets in section 4. A sequence of intervals $\mathcal{I}$ is said to almost Vitali cover a Lebesgue measurable set $E\subseteq[0,1]$ if for all $\epsilon>0$ we have $\mu_L\left(E\setminus O_\epsilon\right) = 0$, where

$$O_\epsilon \,\,=\,\, \bigcup\,\{I\mid I\in\mathcal{I}\,, \mbox{ diam}(I)<\epsilon\}\,\,.$$

Theorem 5.6   The following is provable in $\mathsf{WWKL}_0$. Let $E\subseteq[0,1]$ be a Lebesgue measurable set with $\mu(E)>0$. Let $\mathcal{I}$ be a sequence of intervals which almost Vitali covers E. Then $\mathcal{I}$ contains a pairwise disjoint sequence of intervals I_n, $n\in\mathbb{N}$, such that

$$\mu\!\left(\!E\setminus\bigcup_{n=0}^\infty I_n\!\right) \,\,=\,\, 0 \,\,.$$

Proof. The proof of this theorem is similar to that of Lemma 5.3. The only modification needed is in the proof of the claim. Recall from Definition 4.5 that $E=\lim_{n\to\infty}E_n$ where each E_n is a finite union of intervals in [0,1]. Fix m so large that

$$\mu((E\setminus E_m)\cup(E_m\setminus E)) \,\,<\,\, \frac1{36} \,\mu(E\setminus A) \,\,.$$

As before, find a finite set of intervals $J_1,\dots,J_l\in\mathcal{I}$ such that

$$J_1\cup\dots\cup J_l\,\,\subseteq\,\, E_m\setminus A$$

and

$$\mu\left(E_m\setminus(A\cup J_1\cup\dots\cup J_l\right)) \,\,<\,\, \frac1{36} \,\mu(E\setminus A) \,\,.$$

Find $\{I_1,\dots,I_k\}\subseteq\{J_1,\dots,J_l\}$ as before. We then have

$$\begin{eqnarray*}\lefteqn{\mu(E\setminus(A\cup I_1\cup\dots\cup I_k))} \quad \\ ... ...6} \,\mu(E\setminus A) \\ & = & \frac34 \,\mu(E\setminus A) \end{eqnarray*}$$

Thus we may take $B=I_1\cup\dots\cup I_k$ and the claim is proved. The rest of the proof is as for Lemma 5.3.

Remark 5.7   Once again, the previous theorem can be generalized to the case of a Lebesgue measurable set $E\subseteq[0,1]^n$ and a Vitali covering consisting of closed balls or n-dimensional cubes. Such versions of Vitali's theorem are also provable in $\mathsf{WWKL}_0$.