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

I suppose the question could be stated another way: if you were asked to construct a non-measurable set the first time in the history, what would motivate the construction to a Vitali set? For a construction of the Vitali set, I followed the post posted here: The construction of a Vitali set.

• One of the most controversial parts of measure theory is the axiom of $\sigma$-additivity. I'm not sure the concept of "a non-measurable set" would have been on the radar. Much more likely, it would have been the idea that $\sigma$-additivity was too strong and resulted in contradictions. Jan 2 at 21:22
• @BrianMoehring Except you don't need to mention $\sigma$-additivity at all to set up this issue: we can ask, for example, whether $\mu^*(A)+\mu^*([0,1]\setminus A)=1$ for all $A\subseteq [0,1]$, where $\mu^*$ is Lebesgue outer measure. Jan 2 at 21:40
• @NoahSchweber If I'm playing devil's advocate here, my counterpoint would be to ask why we're dealing with the Lebesgue outer measure (which is rather defined with $\sigma$-additivity built in) Jan 2 at 21:43
• @BrianMoehring How is it defined with $\sigma$-additivity built in? We just look at the infimum over all covers by open intervals of the sum of the diameters of the intervals in the cover; there's no mention of countability here, and in particular no a priori restriction to countable covers. Jan 2 at 21:44
• @NoahSchweber We're not concerned with countable covers. We're concerned with the fact that the infimum the limit of [the volumes of] a sequence of covers. This sequence is intrinsically linked to $\sigma$-additivity. Jan 2 at 21:51

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 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.

• Great answer. There is a typo in the rhs of your first question, it should be "Must we have $\mu^*(A\sqcup B)=\mu^*(A)+\mu^*(B)$?" Jan 3 at 7:37
• @user159517 Good catch, fixed! Jan 3 at 15:31

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.

Just think about what problems there are with assigning measure to a real interval. We have an infinite number of points, so if we assign a real number to the measure of any point, the measure of the interval is infinity times that real number, which is infinity. But we want the measure of a real interval to be finite. So we say that the measure of a singleton set is zero. But that means that when we add up an infinite number of zeros, we get a finite number! So Borel et al come along and say "Okay, you're not allowed to add up any infinity. Measures only have to be additive for countable sums."

So now we need a partition of a real interval into a countable number of sets. We need to somehow "divide" $$|\mathbb R|$$ by $$|\mathbb N|$$. What does it mean to "divide" one set by another? We want some sets $$A,B$$ such that $$A \times B\cong I$$, where $$\times$$ is the Cartesian product, $$I$$ is a unit interval, and $$B$$ is countably infinite. If we're dealing with a unit interval, there are only finite integers in it, so $$B=\mathbb N$$ doesn't work, so we take $$B= \mathbb Q$$. So now we need a set $$A$$ such that $$A \times \mathbb Q \cong I$$. Then we'll have $$m(I) = m(A)*|\mathbb Q|$$, and if $$m(A)$$ is finite, $$m(I)$$ will be infinite, and if $$m(A)$$ is zero, then $$m(I)$$ will be zero as well, so $$m(A)$$ can't exist.

If we have that $$I \cong A \times \mathbb Q$$ for some $$A$$, then that defines an equivalence relation on $$I$$: two numbers in $$I$$ are equivalent if they can be obtained by taking the same element of $$A$$ and crossing them with different elements of $$\mathbb Q$$. That is, if $$i_1$$ corresponds to $$(a,q_1)$$ and $$i_2$$ corresponds to $$(a,q_2)$$, then $$i_1$$~$$i_2$$. Now remember that we have that $$A \times B\cong I$$; that is, $$I$$ is isomorphic to $$A \times B$$, i.e., there is some bijection between ordered pairs and real numbers. What should that bijection be? The simplest one is to simply take the sum. That would mean that two real numbers are equivalent if they differ by a rational number.

So we take a collection of equivalence classes defined by this relation, and $$A$$ will be a set consisting of exactly one representative of each equivalence class.

One way we can glean some understanding is to read Vitali's 1905 paper Sul problema della misura dei gruppi di punti di una retta. Here's the best translation I can give with modern notation/terms (yes, using more concise notation has shortened the paper, but not by much. It's a remarkably short and easy-to-read paper by modern standards):

The problem of measuring the sets of points of a straight line R is that of determining for each set $$A \subseteq \mathbb{R}$$ a real number $$\mu(A) \geq 0$$, called the measure of $$A$$, so that

1. $$\mu(A+x) = \mu(A)$$ for any real $$x$$
2. If $$A_1, A_2, \ldots$$ are pairwise disjoint, then $$\mu\left(\bigcup_{k=1}^\infty A_k\right) = \sum_{k=1}^\infty \mu(A_k)$$
3. $$\mu((0,1)) = 1$$

For any $$x\in \mathbb{R}$$, let $$A_x = x + \mathbb{Q}$$ and note for any $$x,y\in \mathbb{R}$$ either $$A_x = A_y$$ or $$A_x\cap A_y = \emptyset$$.

Let $$H = \{A_x : x \in \mathbb{R}\}$$ and note $$H$$ is a partition of $$\mathbb{R}$$.

For each $$\alpha \in H$$, we consider a point $$P_\alpha \in \left(0,\frac{1}{2}\right) \cap \alpha$$, and we consider $$G_0 = \{P_\alpha : \alpha \in H\}$$. For any $$\rho \in \mathbb{Q}$$, we will denote $$G_\rho = G_0 + \rho$$. [Here, Vitali seems to have written minus instead of plus, but I have to assume it's a typo as if it's a minus, the following doesn't work]

The sets $$G_\rho$$ corresponding to different $$\rho \in \mathbb{Q}$$ are disjoint, there are countably many of them, and they must have the same measure by condition 1.

The sets $$G_0, G_{1/2}, G_{1/3}, G_{1/4}, \ldots$$ are all subsets of the interval $$(0,1)$$ so their union must have measure $$m \leq 1$$.

But then $$m = \mu(G_0) + \sum_{n=2}^\infty \mu(G_{1/n}) = \lim_{n\to\infty} n \mu(G_0)$$ and so $$\mu(G_0) = 0.$$

But then $$\bigcup_{\rho \in \mathbb{Q}} G_\rho$$ must also have zero measure. But this union is $$\mathbb{R}$$ and therefore should have infinite measure. Therefore we conclude that measuring the sets of points of a straight line is impossible.

There may be objections regarding the set $$G_0$$, but this can be perfectly justified if one assumes that $$\mathbb{R}$$ may be well-ordered. For those who do not want to assume this, our result means this: the possibility of measuring the subsets of $$\mathbb{R}$$ and that of well-ordering $$\mathbb{R}$$ cannot coexist.