The unmeasurable set

The diagonal proof is one of the prettiest proofs in mathematics, but there is another proof that I quite like, and it illustrates the use of the fabled axiom of choice.  It's known as the Vitali Theorem, and it proves that not all sets of real numbers are measurable.

What is measure?

But first we need to talk about what it means for a set to be "measurable".  The measure of a set is, on a basic level, the length of the set.  For example the set of all numbers between 0 and 1 has a measure of 1.

However, it is incorrect to say that measure and length are the same thing.  "Length" is an intuitive concept, and it simply doesn't work for all sets of numbers.  For instance, what is the length of the set of all rational numbers between 0 and 1?  Mathematicians need a more rigorous concept so they can have definite answers to these questions.  And so they define measure, which resembles the concept of length, but is not the same thing.

In order for the concept of "measure" to resemble the concept of "length", we will take a few simple axioms:*

1. If we take the set of all the numbers between A and B, then the measure is simply the distance between A and B.
   Example: The set of all numbers between 5 and 7 has measure 2.
   
2. If we take a set of numbers and shift it up or down, then the measure stays the same.
   Example: We can shift the set of all numbers between 5 and 7 upwards by 3.  Now we have the set of all numbers between 8 and 10.  The measure is still 2.
   
3. If we have a countable collection of non-overlapping sets, and we join them together, then the measure of the resulting set is equal to the sum of the measures of each of the smaller sets.
   Example: Consider the set of all numbers between 5 and 7, joined with the set of all numbers between 8 and 10.  The measure of this set is 2 + 2 = 4.

*I am specifically talking about Lebesgue Measure, which is just one kind of measure.  This may not be a complete set of axioms.  For a more rigorous treatment, don't read blogs, read textbooks on real analysis.

With our new concept of "measure", we can answer our earlier question: What is the measure of the set of all rational numbers between 0 and 1?

The number of rational numbers is countable.  That means we can list them one by one, just as we can list all the positive integers one by one:

{0, 1, 1/2, 1/3, 2/3, 1/4, 3/4, ...}

Therefore, we can split this set into a countable collection of sets:

{0}, {1}, {1/2}, {1/3}, {2/3}, {1/4}, {3/4}, ...

Each of these sets has measure zero, because a single point has length zero.  When we put all the points together, we just add all the measures up (by axiom 3), for a total measure of zero.  Therefore, the set of all rational numbers between 0 and 1 has measure 0.

The Vitali Theorem

Vitali's Theorem shows that there exists a set of numbers that is not measurable.  That is, if you try to assign a measure to the set, you will run into contradictions!  We will construct the set as follows:

Take the set of all rational numbers:

{0, 1, -1, 1/2, -1/2, 1/3, 2/3, ...}

Then we shift it upwards by some quantity x, with x being any number between 0 and 1.  Call the resulting set S(x).  So for example,

S(π-3) = {π-3, π-2, π-4, π-5/2, π-7/2, π-8/3, π-7/3, ...}

So far, we have an infinite collection of sets S(x).  But some of these sets will be duplicates of each other.  For example, S(0) = S(1/2), because if you add 1/2 to any rational number, it is still a rational number.  Similarly, S(π-3) = S(π-5/2).  So let's divide the collection of S(x) into many collections, each of which contains an infinite number of duplicates.

The next step is to pick one S(x) from each set of duplicates.  That way, we have a bunch of unique S(x), with no duplicates.  The trouble is, which one do we pick?  Any of them.  It doesn't matter which one we pick!  But how can we pick one from each collection of duplicates?  That would require an infinite number of choices.

And this is where the axiom of choice comes in.  The axiom of choice says that we can make an infinite number of choices, though we can't always write down what all these choices are.  So let's do that.  Now we have a bunch of unique S(x).

The set of all x that we chose is called a Vitali set.  I cannot write down what is and isn't in the set, because I used the axiom of choice to construct it.  However, I will be able to show that the set is unmeasurable.

Suppose that the Vitali set is measurable, and its measure is M.  Now let's shift the Vitali set upwards by a rational number q less than 1.  Take only the fractional part of each number in the set, since we want to keep it between 0 and 1.  Call the resulting set V(q).  By rule 2, V(q) has measure M.

For example, if our original Vitali set was:

{0, π-3, ln(2), e-2, ...}
Then V(1/3) = {1/3, π-8/3, ln(2)-2/3, e-8/3, ...}

The collection of sets V(q) is a countable collection, since the set of rational numbers is countable.  Also, none of the V(q) overlap, because no two elements in the Vitali set have a rational difference.  Lastly, if we join all of the V(q) together, we will get the set of all numbers between 0 and 1.

By rule 3, the measure of the resulting set (ie the set of all numbers between 0 and 1) is equal to the sum of the measures of V(q).  Each V(q) has measure M, and there are an infinite number of V(q).  Therefore:

1 = M + M + M + M + ... ad infinitum

This leads to a contradiction.  If M is 0, then 1 = 0.  If M is not zero, then 1 = infinity.

In conclusion, the Vitali set is not measurable as we first assumed.  If it has length, how did we fit an infinite number of copies into a finite length?  If it has no length, then how did we make a length out of a countable number of copies?

Is the axiom of choice true?

The axiom of choice has been used to derive some strange conclusions, which has led many to ask whether we should really be assuming that the axiom is true.  But that's the wrong question!

Axioms are not true or false.  They simply define a set of ground rules for mathematical analysis.  The best we can hope for is that all the axioms are consistent with each other.  As far as we know, the axiom of choice is consistent with the other axioms of set theory.

But the axiom of choice is not the only axiom that would be consistent.  For example, we could have taken instead taken the axiom of determinacy.  This axiom implies that all sets are measurable, and therefore the axiom of choice is false!  The axiom of choice and the axiom of determinacy are mutually exclusive with each other.  But this does not mean that one axiom is more "correct" than the other, just as flat geometry is not more "correct" than spherical geometry.

The series on infinite sets:
Hilbert's Hotel
Doubling the Sphere
Larger infinities and the Diagonal Proof
Power sets and the Chef Paradox 
The unmeasurable set