The Intuition of the Construction of a Non-Measurable Set (Vitali Set) on the Real Line

I think the following is a pretty plausible "story."

We start with the notion of Lebesgue outer measure: we define the diameter of an open interval in the obvious way, and then set $\mu^*(A)$ to be the infimum over all covers $\mathcal{C}$ of $A$ by open intervals of $\sum_{I\in\mathcal{C}}diam(I)$. This is already a nontrivial notion, with $\mu^*(\mathbb{Q})=0$ in contrast to the situation with respect to Jordan measure and $\mu^*([0,1])$ requiring some effort, but this early work (in my opinion) strongly suggests that this is a natural notion to consider.

Now one of the earliest general results one proves about $\mu^*$ is its finite subadditivity: $\mu^*(A\sqcup B)\le \mu^*(A)+\mu^*(B)$. It's natural to ask whether we can prove equality in this case, given that the union in question is disjoint ("$\sqcup$" instead of "$\cup$"):

Suppose $A\cap B=\emptyset$. Must we have $\mu^*(A\sqcup B)=\mu^*(A)+\mu^*(B)$?

One's utter failure to find a proof that the answer is yes will quickly suggest that one should look for a counterexample; however, it's also pretty easy to come to the conclusion that any "reasonably natural" disjoint sets will satisfy the relevant equality. So to find a counterexample, we need to start thinking in terms of coarse properties which will ensure bad measure-combining behavior. This naturally suggests arithmetic with infinity (especially after one proves countable subadditivity of Lebesgue outer measure, and countable closure of the ideal of null sets).

Specifically, if we can partition $[0,1]$ into countably many pieces $A_i$ ($i\in\mathbb{N}$), which are each guaranteed to have the same outer measure $k$, then we'll know that finite additivity must fail:

• We can't have $k=0$ because a quick argument shows that the union of countably many null sets is null.

• But if $k>0$, then by the Archimedean principle there is some $n\in\mathbb{N}$ such that $nk>1$; consequently, we have $$\mu^*(A_1\sqcup...\sqcup A_n)\le \mu^*([0,1])=1<nk=\mu^*(A_1)+...+\mu^*(A_n),$$ which is a clear failure of finite additivity.

This seems like a great idea ... for about five seconds. The problem is the bolded clause a few sentences ago: partitioning $[0,1]$ into countably infinitely many pieces is easy, but why should we at the outset know that those pieces (which after all we want to be weird) will all look the same measure-wise?

Ultimately we're saved here by the realization that certain operations on sets preserve outer measure. In particular, for each $\alpha\in\mathbb{R}$ and $X\subseteq[0,1)$ the "mod 1 sum" $$X\star \alpha:=\{x+\alpha: x\in X, x+\alpha< 1\}\sqcup\{x+\alpha-1: x\in X, x+\alpha\ge 1\}$$ has the same outer measure as $X$ itself. To get the countable union we desire, we pick some nicely messy countable set - like $\mathbb{Q}$ - and hope for a positive answer to the following:

Is there some $X\subseteq[0,1)$ such that $\{X\star q:q\in\mathbb{Q}\}$ partitions $[0,1)$?

At this point we're extremely close to the definition of the Vitali set, and the idea of passing to mod-$\mathbb{Q}$ equivalence classes is not too big a leap.

I don't know how one would come up with the original idea. But here is an intuition or big picture that I find helpful to understand the usual textbook presentations. In what follows I'm leaving out all the technical details, assuming you've been through the formal proof as presented in your link or in a textbook.

First, forget the Vitali set for the moment and consider $\mathbb Z / \mathbb 5 Z$, the familiar integers mod $5$.

The integers mod $5$ are constructed by defining an equivalence relation, $\sim$ on the integers by saying that $n \sim m$ if $5 | n - m$. As usual we verify that this is an equivalence relation, so that it partitions the integers into a five pairwise disjoint equivalence classes as follows:

$$ \begin{matrix} 5 \mathbb Z + 0 =& \{\dots,& -15,& -10,& -5,& 0,& 5,& 10,& 15,& \dots\} \\ 5 \mathbb Z + 1 =& \{\dots,& -14,& -9,& -4,& 1,& 6,& 11,& 16,& \dots \} \\ 5 \mathbb Z + 2 =& \{\dots,& -13,& -8,& -3,& 2,& 7,& 12,& 17,& \dots \} \\ 5 \mathbb Z + 3 =& \{\dots,& -12,& -7,& -2,& 3,& 8,& 13,& 18,& \dots \} \\ 5 \mathbb Z + 4 =& \{\dots,& -11,& -6,& -1,& 4,& 9,& 14,& 19,& \dots \} \end{matrix} $$

We have partitioned the integers into five equivalence classes, each of them countably infinite. That is, we have expressed the integers as a disjoint union:

$\displaystyle \mathbb Z = \bigcup_{n \in \{0,1,2,3,4\}} 5 \mathbb Z + n$

On the right we have a collection of nonempty sets, so by the axiom of choice there exists a choice set $C$ containing exactly one element from each equivalence class. In this case we don't actually need the axiom of choice since we could (for example) take the smallest positive integer in each equivalence class, but no harm is done by using choice, and this will parallel the case of the Vitali set to come.

In fact in this union there is nothing special about $\{0,1,2,3,4\}$. It's just another choice set. We can equally well write the integers as a disjoint union like this:

$\displaystyle \mathbb Z = \bigcup_{n \in C} 5 \mathbb Z + n$

For definiteness, let's say that our choice set $C = \{-15, -9, -3, 3, 9 \}$. Any choice set will do. Let's rewrite the five equivalence classes, visually lining up our choice set vertically:

$$ \begin{matrix} &&&&& \text{vvvv} \\ 5 \mathbb Z + 0 = & \{\dots,&-30,& -25,& -20,& -15,& -10,& -5,& 0,& \dots\} \\ 5 \mathbb Z + 1 = & \{\dots,& -24,& -19,& -14,& -9,& -4,& \ 1,& \ 6,& \dots \} \\ 5 \mathbb Z + 2 = & \{\dots,& -18,& -13,& -8,& -3,& 2,& 7,& 12,& \dots \} \\ 5 \mathbb Z + 3 = & \{\dots,& -12,& -7,& -2,& \ 3,& 8,& 13,& 18,& \dots \} \\ 5 \mathbb Z + 4 = & \{\dots,& -6,& -1,& \ 4,& \ 9,& 14,& 15,& 19,& \dots \} \\ &&&&& \text{^^^^} \end{matrix} $$

Now it is perfectly clear, visually, that the translates of the choice set by multiples of $5$ fill out all of $\mathbb Z$. That is, by successively adding $5$ to each of the elements of the choice column, we get all the vertical slices to the right of it; and by successively subtracting $5$, we get all the columns to the left. That is, we can write $\mathbb Z$ as a disjoint union:

$\displaystyle \mathbb Z = \bigcup_{n \in 5 \mathbb Z} C + n$

In other words we started with a partition of $\mathbb Z$ into a five-fold disjoint union of of countably infinite sets; and now we have expressed $\mathbb Z$ as a countably infinite union of sets of cardinality $5$. We have "swapped the cardinalities." In a more general sense, we've swapped the a pair of properties. It makes no difference here, but it will for the Vitali set.

Symbolically, we started with $\displaystyle \mathbb Z = \bigcup_{n \in C} 5 \mathbb Z + n$ and "swapped the symbols" on the bottom and to the right of the union to get $\displaystyle \mathbb Z = \bigcup_{n \in 5 \mathbb Z} C + n$. To formally prove that this is legitimate we have to do a little algebra, but it comes down to the fact that $5 \mathbb Z$ is a subgroup of the additive Abelian group $\mathbb Z$.

The construction of the Vitali set is exactly the same idea. We start out with an equivalence relation on the reals, $x \sim y$ if $x - y \in \mathbb Q$. This allows us to write the reals as a union, not disjoint:

$\displaystyle \mathbb R = \bigcup_{x \in \mathbb R} \mathbb Q + x$

Here we do need the axiom of choice to form a choice set $V$ consisting of exactly one element of each equivalence class. And "a moment's thought," as they say, should convince you that we can actually write the reals as a disjoint union:

$\displaystyle \mathbb R = \bigcup_{x \in V} \mathbb Q + x$

And now doing the same symbol swap that we did in the integers mod $5$, we can write:

$\displaystyle \mathbb R = \bigcup_{q \in \mathbb Q} V + q$

Of course this requires proof, but as with the integers mod $5$ it comes down to the fact that $\mathbb Q$ is a subgroup of the additive Abelian group $\mathbb R$. This is the intuition behind the calculations: that all we're doing is rewriting an uncountable union of countable sets as a countable union of uncountable sets, in order to apply countable additivity.

We are not done with the construction. Even if each translate has positive measure and countable additivity gives us an infinite sum, we still don't have a contradiction because the measure of the reals is also infinite.

That's why we now have to reduce the reals mod 1, either by "addition mod 1" or else by doing the construction on the circle, as is sometimes done. Now the fact that the sum of the measures of the translates of $V$ is either zero or infinite, contradicts the fact that the measure of the unit interval is $1$.

The essential idea behind the computations in the standard proof is that we did a "symbol swap" between the index under the union symbol and the disjuncts to the right, justified by the fact that we are modding out by a subgroup of an Abelian group. And we did this in order to get a useful property, namely countability, as the index of the union.

I note in passing that the exact same idea also works in more generality, for example in the Banach-Tarski paradox. In that case we're not modding out by an Abelian subgroup, but rather by a sufficiently well-behaved group action that allows us to do yet another symbol-swap across a union that gives a favorable index set. I was wondering if there's a general name for this idea, or perhaps if it's some kind of categorical construction. Perhaps that belongs as a separate question.