Last week, we considered the problem of measuring all subsets of a given finite or countably infinite set. Today, we will investigate the problem of measuring subsets of an uncountable set. In fact, we will focus on a particular uncountable set, which happens to be one of the most important sets in all of mathematics: the set of real numbers, .
There are certain subsets of which we have a very natural and well-behaved method for measuring: the intervals. Recall that, if are real numbers, then:
- is the set of all real numbers such that . Such a set is called an open interval.
- is the set of all real numbers such that . Such a set is called a closed interval.
- In either case, and are said to be the endpoints of the interval.
The most natural way to measure an interval is simply to subtract the lower endpoint from the upper one, i.e., if , then . Note that, as a result of this, any one-element subset of is assigned a measure of , since, if , then .
There’s no reason to stop at intervals, though. Consider a set that consists of two disjoint intervals, i.e. intervals and such that . The natural measure to assign to is, of course, . Extrapolating, if is a natural number and consists of pairwise disjoint intervals, i.e. intervals such that, for all , , then we should set .
There’s no reason to stop at finite unions of intervals, either. As those of you who have taken calculus courses will know, there is a well-developed theory of infinite sums of positive real numbers, so it makes sense to measure sets that are unions of countably infinitely many pairwise disjoint intervals in the same way. More precisely, if is the union of countably many pairwise disjoint intervals , then we can let .
Note, in particular, that if is a countable subset of , then . This is because can be considered to be a countable union of pairwise disjoint intervals, each consisting of precisely one element. Since one-element sets are given a measure of , we then have .
Let be the collection of all subsets of that can be written as countable unions of pairwise disjoint intervals. In other words, consists of precisely those sets to which we have assigned a measure. (Those of you with some prior knowledge might object here that, as I’ve made it this far, I may as well just keep going and define the measure on the collection of all Borel sets rather than this clearly unsatisfactory collection . You might be right.) This measure, , that we have constructed has some very nice properties. We list some of them here.
- For all , .
- and .
- For any , .
- (Monotonicity) If and , then .
- (Countable additivity) If is a collection of pairwise disjoint elements of , then .
- (Shift invariance) If and , then, if is the set we get by “shifting” over by , i.e. , then .
Take a minute to think about these properties. I hope you will agree with me that they are all natural properties that one would like to require of a reasonable measure of subsets of .
There is a small problem, though. Our measure, , does not measure all subsets of , only those in . And there are many subsets of that are not in . One can see this just by counting: there are only members of , whereas the number of all subsets of is , which is strictly larger than . Compared with the vast expanses of the full power set of , our set looks positively puny.
So this raises a question: Can we extend our measure so that it measures all subsets of while still maintaining the nice properties 1-6 listed above? Interestingly, the answer, discovered by Italian mathematician Giuseppe Vitali in the early 20th century, is no.
(You may be initially disappointed by this answer, but I would argue that this makes life much more interesting. Vitali’s discovery came in an era of great upheaval and progress in mathematics, and his discovery, along with others of the time, laid the groundwork for some of the most important and fascinating achievements of the 20th century.)
Let us reconstruct Vitali’s argument. Suppose for the sake of a contradiction that we have a measure satisfying properties 1-6 that measures all subsets of . First, we will define an equivalence relation, , on the interval by setting if and only if is rational. I’ll leave it to the reader to check that this is an equivalence relation, recalling that an equivalence relation must satisfy the following requirements:
- (Reflexivity) For every , we have .
- (Symmetry) For every and , if , then .
- (Transitivity) For every , and , if and , then .
For each , let denote the equivalence class of , i.e. the set . Since is an equivalence relation, the equivalence classes partition into pairwise disjoint sets. In particular:
- For every , .
- For every and in , either or .
Let be the set of equivalence classes, and pick a choice function on , i.e. a function such that, for every , . Let and note that, for every , . If is a rational number, let denote the set shifted by , i.e. the set .
Claim 1: If and are distinct rational numbers in , then .
Proof: Suppose for the sake of a contradiction that there is a real number in . Then there are such that . But then . Since and are rational, is rational, so . Moreover, since and are distinct, , so . But then contains at least two elements of (namely, and ), contradicting the fact that intersects each equivalence class in only one element and finishing the proof of the claim.
Claim 2: Let . Then .
Proof: We first show . To this end, fix . By construction, we can find a real number in . Let . Since , is rational. Since , we must have . But then and , so . Since was arbitrary, we have .
To see that , fix . There is and such that . Since , this means . Thus, . This ends the proof of the claim.
Since measures every subset of , it must measure for every and . By shift invariance of (requirement 6), it must be the case that for every . By countable additivity of (requirement 5) and Claim 1, we must have . By Claim 2 and monotonicity of (requirement 4), we must have .
But these things together yield a contradiction! Let . Then . If , this sum is , so . If , this sum is infinite, so . In either case, is not in the interval , as it is supposed to be. Therefore, we have identified a set (namely, ), that cannot be measured by , which is a contradiction to our assumptions.
Closing remark: Getting our set required an application of the axiom of choice, and it turns out that this use of choice is necessary to find a non-measurable set. In one of the great achievements of modern set theory, Robert Solovay proved in 1970 that it is consistent with ZF (i.e. all axioms of set theory except the axiom of choice) that there is a measure satisfying requirements 1-6 and measuring all subsets of the reals. In fact, the measure that works is the one that has become the canonical measure on the reals: the Lebesgue measure, introduced by Henri Lebesgue in 1901 and the subject of the next installment of this series.