Sets of Impossible Size and the Birth of Measure Theory

Everyone understands the concept of a measure or size. Some things are longer, some are shorter. Some things heavy, some light. If I show you two bowls—one with five apples and the other with three apples, it is obvious to you that the bowl with five apples is a bigger collection. In mathematics, this “discrete” way of measuring collections of things is called a counting measure. Given a finite set, i.e. a finite collection of objects, a counting measure assigns it a measure equal to the number of objects in the collection.

Here are some properties of the counting measure that are so obvious that you might not even have noticed them, or spared them a second thought:

1. The measure of the empty set is zero.

Well, duh. An empty bowl has zero apples.

1. The measure of any set is non-negative.

Again, a counting measure of a set is just the “count” of the number of objects in it. So of course, this count is not a negative number.

1. The measure is countably additive.

Additivity of a measure means that the total measure of two disjoint sets (i.e., the sets that do not have any objects in common) is the sum of the measure of the two sets. Suppose we have two bowls—one with two apples and the other with three, i.e. the counting measure of the first bowl is 2 and that of the second bowl is 3. Then the counting measure of the two bowls combined is, well, 2 + 3 = 5. That’s just how we count things! Countable additivity means that the additivity property extends to any countable (possibly infinite) union of things.

I hope you agree with me when I say that any decent way of measuring things should satisfy the above three properties. The mathematicians agree with this assessment too, and that is why they formally define a measure as follows

A measure is any function that assigns a number to every set such that the above three properties are satisfied.

Now let us use the things we learned so far to formally construct a measure out of a concept that I am sure you have encountered countless times before— “length”. Again, you probably didn’t even think about this before, but “length” satisfies all the three properties required of a “measure” in the mathematical sense. For this essay, we will focus on defining the lengths of sets of numbers on the number line.

Consider an interval on the number line, say S = [2, 10]. That is, S is the set of all real numbers between 2 and 10, including both 2 and 10. Going by our physical intuition about length, we would like the length of the set S to be 10 – 2 = 8. More generally, we can define the length measurement of an interval T = [a, b] where a<b to be l(T) = b – a. Defining length like this seems pretty intuitive, right? A nice thing about this definition is that if we move the interval T along the number line by a distance d to left or right, the length of the translated interval does not change. Indeed, suppose Td = [a + d, b + d]. Then l(Td) = (b + d) – (a + d) = b – a = l(T). This property is called translational invariance, and it makes perfect physical sense. The length of an object should not change just because we moved it by some distance in any direction.

So far, we have formally defined what the length of any interval of numbers should be. Let us now extend this definition to any arbitrary collection of numbers by using the three properties of a measure. Consider the set of numbers, A = [0, 1] U [3, 4], which is the union of two disjoint intervals [0, 1] and [3, 4]. The length of A is 2, because T is composed of a disjoint union of two sets of length 1 each, and because we would like the “length” measure to be additive. More generally, we can define the length of a set of real numbers as the sum of lengths of disjoint intervals that the set is made of.

Let us work out a few more examples to get comfortable with the definition of length that we just defined.

Just like in the above examples, we should be able to assign a length to any arbitrary subset of the number line…right? After all, our definition of length aligns perfectly well with our physical intuitions on how lengths should be measured. All we have to do is simply add up the lengths of all the disjoint intervals that the set is made of. What could go wrong? We better be able to measure the length of any set this way, because every set should have a size, shouldn’t it? The stakes are even higher, because other physical notions like “area” and “volume” are extensions of the one-dimensional length measure to higher dimensions, and if we can’t even measure lengths, how can we hope to measure areas and volumes and distances and time and so on!

Unfortunately, we can’t always get what we want. There are sets in this (mathematical) world that cannot be assigned a well-defined measure! There are subsets of the number line that have no length! By “no length” here, I don’t mean zero length. I really do mean no well-defined length whatsoever! Whichever length we assign to such a set is wrong, because it leads to mathematical absurdities like 1 = 2. And these absurdities do not result from sloppy math, like in some proofs of 1 = 2 that you might have seen in high school where we sneakily introduce an illegal operation like dividing by zero. There is absolutely no rigorous mathematical way to assign a length to these sets. These sets are of impossible size!

The first of these sets of impossible size, called the Vitali Set, was discovered in 1905 by Giuseppe Vitali, an Italian mathematician. There are uncountably many such subsets of the number line. Mathematicians call them “non-measurable” sets, for obvious reasons. An interesting thing about these sets is that we can show that they exist, but we cannot explicitly construct them. In fact, any set of numbers that can be explicitly constructed using a deterministic procedure like an algorithm is measurable. Intuitively, this makes sense because if there is a procedure to construct a set, then we could plot the set on a paper or on a computer and then measure its length with a sufficiently precise ruler. You might ask, “How can anyone show that such a size-less set exists, if there is literally no way of constructing it in practice?” By the end of this essay, I will show you how. The answer to this comes from a notorious, yet seemingly harmless principle that pervades modern mathematics called the “Axiom of Choice”.

In order to show that there is a set of impossible size, Giuseppe Vitali makes use of the axiom of choice. Given a (possibly infinite) collection of sets, the axiom of choice says that it is possible to define a new set that contains exactly one item from each of the sets in the collection. Now I don’t know about you, but the axiom of choice seems obviously true to me. And yet, such a seemingly intuitive assumption somehow leads us to non-measurable sets, which blatantly go against all of our physical intuitions about length!

(Source)

Armed with the axiom of choice, let us now embark on our quest to find the elusive beast, the Vitali set, the set that must not be measured! The Vitali Set, denoted by V, is a subset of the unit interval U = [0, 1]. First, let us organize all the numbers in [0, 1] into a collection of bins. Two numbers in U go in the same bin if their difference is a rational number. For example, √2+3 and √2+5 go in the same bin because their difference is 2, a rational number. √2+3 and 3 belong in different bins because their difference is √2 which is not rational. There will be an infinite number of such bins, but that is not a problem for the axiom of choice! Just pick one number from each bin and put each of them together to form a set V. Now V is our Vitali set! Notice how we did not explicitly construct V, because we did not specify which number is picked from each bin. Nevertheless, we know that such a set V can be defined because we believe in the axiom of choice.

Now, we will show that V is non-measurable using proof by contradiction. Suppose we are wrong in claiming that V is non-measurable. Then V must have some length, say t. The rest of the proof goes into showing that t cannot be any real number. Let q1, q2, q3, … be the sequence of all the rational numbers in the interval [-1, 1]. It is possible to list all the rational numbers in this way because there are only countably many rational numbers. For i = 1, 2, 3, …, let Vi be the set of all numbers in V shifted to the right by qi. (If qi is negative, then Vi is a copy of V shifted to the left by -qi.) In mathematical notation, we can write this as,

Since Vi is just a shifted version of V, its length is also t, the same as that of V. Since qi is in the interval [-1, 1] and since V itself is in the interval [0,1], Vi belongs in the interval [-1, 2]. Another interesting fact about the sets Vi is that they are all disjoint. That is, for any i ≠ j, Vi and Vj do not have any numbers in common. To see this, suppose on the contrary that c is a number that is both in Vi and Vj. Then c = a + qi = b + qj, where a and b are two distinct elements of V. Rearranging the previous equation, we have that a - b = qj - qi. So, the difference between a and b is a rational number and this implies that a and b both belong in the same bin. Recall that we only picked one element from each bin when defining V. Hence, it cannot be that a and b are both distinct elements of V that belong in the same bin. Therefore, Vi and Vj cannot have any element in common for any i ≠ j.

Let us now define a new set Z as the union of all the sets Vi for every i. In mathematical notation, we can write this as,

What is the length of Z? Recall that Z is the disjoint union of sets Vi, and that all the sets Vi have the same measure t. Hence, Z is an infinite union of non-overlapping sets, all of which have the same length t. If t = 0, then Z has to be of length 0 as well. On the other hand, if t>0, then Z has to be of infinite length. Any other length for Z is impossible!

We are now in the last leg of the proof. So far, we have narrowed down the options for the length of the set Z to just two options: zero and infinity. We will now show that Z cannot have a measure of either zero or infinity. This will give us the contradiction that we have been waiting for, and proves our initial assumption that V is measurable must be false.

Can Z have a measure of infinity? Recall that Vi is contained in the interval [-1, 2] for all i. Since Z is the union of all such Vi’s, Z also must be contained in [-1, 2]. We know that the length of the interval [-1, 2] is 3. Hence, the length of Z, whatever it may be, cannot be greater than 3. Therefore, Z cannot have a measure of infinity.

We will now eliminate the last remaining option for the length of z, which is 0. Pick any number x in the interval [0, 1]. It must be in one of the bins that we defined at the start of the proof. Let y be the element of V that we picked from the same bin as x. Then x - y must be a rational number. Moreover, x - y must be in the range [-1, 1] because both x and y are in [0, 1]. So, x = y + qi where qi is some rational number in [-1, 1]. Hence, x must be in Vi which in turn is in Z. Therefore, we have shown that any number x in the interval [0, 1] must belong in Z. That is, Z must have a length greater 1, the length of [0, 1]. In effect, we have eliminated the last remaining option for the length of z, which is 0! Check and mate!

Look at what we have done! We summoned a set that cannot have a size! We have broken the concept of length! And we did all that with some basic algebra and set logic combined with the innocent-looking axiom of choice. What now? How do we deal with the uncomfortable fact that there are some sets that just cannot be measured? This is where measure theory comes in.

Measure theory is a field of mathematics that deals with measures like “length”, “area”, “volume” and many more in the abstract. In measure theory, the specific notion of “length” of sets on the number line that we discussed in this essay is called the Lebesgue measure in one dimension. Lebesgue measure formalizes the intuitive notion of length of one-dimensional objects. It is a fact that certain subsets of the number line, like the Vitali set, are not Lebesgue-measurable. In measure theory, whenever we define a measure m on the objects in a set U, we also specify a collection of subsets E of U that are measurable with respect to m. Here, E may not always be the collection of all possible subsets of U (called the power set of U), because it may be the case that certain subsets of U are non-measurable like the Vitali Set was for Lebesgue measure. The triple (X, E, m) defines a “measure space”, which is a fundamental object in measure theory.

And that is all for this essay. It is unlikely that you will encounter such pesky little non-measurable monsters like the Vitali set in the physical world. But if you do, remember to accept the sets that cannot be measured, measure the sets that you can, and strive for the wisdom to know the difference!