## Non-measurable Sets That Go Bump in the Night

It’s Halloween! Which means that we here at Infinity Plus One get to do something spooky!

That’s right, we’re going to talk about sets of numbers so weird that even the very idea of length breaks when looking at them.

In the last few posts, we’ve been talking about how to measure the lengths of sets, even ones that are weird.

In How Long is Infinity?, we introduced how we measure things — by covering up a set with little intervals, and then calling the length of our set the smallest lengths of intervals that cover our set.

Using this length, it turns out that any countable set, like $\{1, 2, 3, \cdots \}$, or even the set of all rational numbers, has zero length.

In The Cantor Set, we showed that, though uncountable sets like [0,1] (all the numbers between 0 and 1) have positive length, there are uncountable sets with zero length. The Cantor set is the main example.

In this post, we want to look at non-measureable sets. Sets which are so weird that they break our “ruler” and make it impossible to make any sense at all of their length.

As a technical caveat, the “ruler” we’ve been discussing so far is technically the “outer Lebesgue measure,” which is not really the same as the “Lebesgue measure” that mathematicians use. However, the difference is buried in technical details that would distract from the story, so we’ll bury those important details for this post.

So what does an non-measureable set look like?

It’s gotta be weird. The definition of length, or measure, that we have is pretty robust. It can handle some pretty weird sets, like all the decimals with a 7 in them, and spit out a length.1

So, in order to come up with a non-measureable set, we’re going to have to work hard.

What we’re going to do is come up with a weird set, and we’ll prove that if we add up infinitely many copies of it, somehow that total length will end up between 1 and 3. But that can’t be right, since adding up infinitely many of the same number always gives either 0 or infinity!2

To start, we’re going to split all the real numbers into groups.

The first group is all the rational numbers, i.e., any number that can be written as a fraction of integers, like 2/3 or -712/2341. We’ll call this set $\mathbb{Q}$, for “quotient.”

The other groups are all copies of the rational numbers, but shifted left or right by a different real number. For instance, we could have the group $\pi + \mathbb{Q}$, which is the set of all numbers which are $\pi$ plus any rational number you want. Or you could have $e + \mathbb{Q}$, which is the set of all numbers which are $e$ plus any rational number you want.

There are a whole lot of these groups, and every real number is in one of them. On the other hand, there is more than one way to name which set you’re talking about.

When we gave the two examples of these groups, we used $\pi + \mathbb{Q}$ and $e+\mathbb{Q}$ to define them. In other words, we picked a particular number, $\pi$ or $e$, that happened to be in the group, and used it as a representative of that set.

But there’s more than one number in $\pi+\mathbb{Q}$, and we could have used any of them to represent the set, not just $\pi$. For instance, $(\pi-1/3)+\mathbb{Q}$ is the exact same set, with the exact same numbers in it. So is $(\pi+712/2341) + \mathbb{Q}$ or $(\pi+17) + \mathbb{Q}$

…though $\pi/2+\mathbb{Q}$ would not be the same, since $\pi$ and $\pi/2$ do not differ by a rational number.

As long as our representatives differ from each other by a rational number, the sets are exactly the same.

Using these groups of numbers, we can now construct the unmeasureable set.

Let $V$ be the unmeasurable set. To construct it, look at each of the groups of numbers we came up with earlier. From each one, pick a single representative that happens to be between 0 and 1. For instance, from the set $\pi+\mathbb{Q}$, we could pick the representative $\pi-3$, which is between 0 and 1. From the set $\mathbb{Q}$, we could pick 0 or 1 or 1/2 or any rational number between 0 and 1.

Now that we’ve chosen one representative from each group, it turns out that $V$ is unmeasurable!

Here’s how we’ll prove it.

Similar to how we took $\mathbb{Q}$ and moved all the numbers by $\pi$ to make $\pi+\mathbb{Q}$, we can take our set $V$ and move all the numbers by a rational number $q$, and make a new set $q+V$.

To make things clearer, this means that if a number $x$ is in $V$, then the number $q+x$ is in $q+V$. And, in the opposite direction, if a number $y$ is in $q+V$, that means that $y-q$ must have been in $V$.

But there’s something funny about $q+V$. No matter how small $q$ is, $V$ and $q+V$ never overlap!

Remember, each of the groups we came up with earlier had infinitely many different representatives we could have picked. But the representatives had to differ from each other by a rational number if they were supposed to represent the same group.

If $V$ and $q+V$ overlap, that means there would be a number $x$ in $V$ and $q+V$. That means that $x-q$ would also have to be a number in $V$. Thus there are two numbers ($x$ and $x-q$) that are both in $V$, but differ by a rational number.

But remember that the numbers in $V$ are representatives of our groups, and so if they differ by a rational number, they represented the same group.

But we only picked one representative from each group to put in $V$.

And so $V$ and $q+V$ can’t overlap!

Next step: Put the rational numbers between -1 and 1 into some order. There are infinitely many of them, but they’re still a countable set, so we can do it. There are more details in the earlier post The size of infinity, but here’s the kind of ordering we could use to make sure we get them all.

Since we have an ordering for the rational numbers between -1 and 1, we’ll call $q_1$ the “1st” rational number, $q_2$ the “2nd,” etc., and $q_k$ the “k-th” rational number. Then, we can come up with a whole bunch of copies of $V$ moved around. We’ll call $V_k$ the the set $q_k +V$, i.e., the set $V$ moved up or down by $q_k$.

Just as before, none of the $V_k$ overlap. Also, since $V$ only had numbers between 0 and 1, and $q_k$ is between -1 and 1, then all the numbers in $V_k$ are between -1 and 2.

The more difficult part is to recognize that if you put all of the $V_k$ together (“take their union”), then together, they contain every number between 0 and 1.

To see this, pick any number $x$ between 0 and 1. No matter which number we pick, it’s in one of the groups we made earlier, perhaps $\pi + \mathbb{Q}$. But, when we made $V$, we picked one representative $r$ (between 0 and 1) for each of these groups. Since the representative $r$ and the number $x$ are in the same group, they have to differ by a rational number, and since they are both between 0 and 1, that rational number they differ by has to be between -1 and 1. That means that $x$ is in the set $V_k$ that happens to be $V$ moved by $q_k = x-r$, which is a rational number!

Yeah, it’s kind of hard to keep all these sets straight, but we’re almost done.

To finally see that the set $V$ can’t be measured (i.e., is non-measurable), let’s pretend that we can measure it, and show that something impossible happens.

If we can measure $V$, the sets $V_k$ have the same length, since they’re really the same set, just moved up or down on the number line.

Since, put together, the $V_k$ contain all the numbers between 0 and 1, their total length has to be at least 1. And, since the $V_k$ only have numbers between -1 and 2, clearly their total length has to be no bigger than 3. If we wrote $L(V_k)$ to represent the length of $V_k$, we could write that like this:

$1 \leq L(V_1) + L(V_2) + L(V_3) + \cdots \leq 3$

But, again, the set $V$ has the same length as each of the $V_k$, and so, really, we’re saying:

$1 \leq L(V) + L(V) + L(V) + \cdots \leq 3$

But we’re adding up infinitely many of the same number! If the length $L(V)$ were 0, adding up infinitely many zeros gives zero length. If the length $L(V)$ were any number bigger than zero, adding up infinitely many of them would give infinite length!3

And so, since 0 and $\infty$ are not between 1 and 34, we have shown something impossible. Thus $V$ cannot be measurable. We have broken our ruler.

So, yeah, non-measurable sets are weird. And we had to do a lot of work to come up with one.

But, in the end, it might seem like a waste of effort. I mean, it’s just a weird set that no one in their right mind would care about anyway.5

But there are some weird things you can do with non-measurable sets.

The most famous is the Banach-Tarski paradox. There is a way you can take a sphere, cut it up into a few pieces, and rearrange them, and end up with two spheres, exactly identical to the original.

But that’s for next time!

Happy Halloween!

<– Previous Post: The Cantor Set
First post in this series: How Long is Infinity?
–> Next Post: Double for Nothing: the Banach-Tarski Paradox

1. For all decimals between 0 and 1 that have a 7 in them, the length it gives is 1. In other words, virtually “every” number has a seven in it!
2. The name for the set we’ll be constructing is a “Vitali set.” You can read more on the Wikipedia page
3. Importantly, there are only countably many sets and lengths that we’re considering, so there’s no funny business going on. Adding up countably many numbers or sets works the way you think it “should.”
4. Citation needed.
5. Of course, mathematicians are not really known for ever being in their right mind…

## The Cantor Set

In the last post, How long is infinity?, we described how to very carefully define the length (technically the measure) of any set of points on the number line. You cover up your set with intervals, then add up the lengths of the intervals. That gives you an upper bound for how long your set can be. The actual length is then the smallest upper bound you can get this way.

Using this definition, we proved the surprising result that any countable set has length zero.1

For the counting numbers $\{1, 2, 3, \cdots\}$ this isn’t so weird. After all, they’re nice and spread out, even if there are infinitely many of them.

But I want to emphasize again how weird it is that countable sets have zero length. For example, consider all the rational numbers (numbers that are fractions, like 2/3) between 0 and 1. They’re packed in there like sardines.

Now, if we want to estimate their length, we could count them, putting an interval of length 1/4 on the first rational number, an interval of length 1/8 on the second, then 1/16, then 1/32, etc..

In this way we could cover all of those rational numbers by intervals with total length $\frac14 + \frac 18+\frac1{16} + \cdots = \frac12$. Somehow, despite the rational numbers being everywhere inbetween 0 and 1, and us covering every single one with its own interval, somehow we only managed to cover half the numbers between 0 and 1!

Yeah, it’s pretty bizarre.

So, countably infinite sets don’t have any length, while many uncountably infinite sets, like the interval [0,1], all the numbers between 0 and 1, usually have positive length.

Does every uncountably infinite set have length?

Now seems a good point to mention that adding up uncountably many things behaves… badly.

When we had a countable set, you could argue that the total length had to be zero because each individual point has length zero, and $0+0+0+\cdots$ must clearly be zero, so the total length had to be zero.

But for an uncountable set, adding up lengths just doesn’t work.2

For instance, no matter how we try, the argument we used for countable sets to show that their measure is zero simply cannot work. To remind you, we put smaller and smaller intervals around each point of the countable set. As we made the sets smaller and smaller, we found we could get as small of total length as we wanted.

Now, suppose we try to put smaller and smaller intervals around the points of an uncountable set, like we did with a countable set. Thus, each point has an associated interval length. If we add up all those interval lengths, we are adding up uncountably many numbers that are each greater than zero.

Since we can add up sequences and sometimes get finite numbers, like $1+\frac12+\frac14+\frac18 + \cdots = 2$, this might not seem like a problem. But when you add up uncountably many positive numbers, you always get infinity!

The argument goes like this: split up the (uncountably many) intervals we are using to cover our uncountable set based on their length. Put all the intervals with lengths between, say, 1 and 1/2 into one group, and all those with lengths between 1/2 and 1/4 into another, and all those between 1/4 and 1/8 into another, etc..

We’ve now split our uncountably many intervals into countably many groups. (There are countably many groups since we can count them — here’s the first group, the second group, the third group, etc..) But uncountably infinite is larger than countably infinite, so we can’t fit the intervals into the groups nicely.

At least one of the groups has to have infinitely many intervals!

Each of these groups, though, has a minimum length. Even if the group with infinite intervals had lengths between $1/2^{1000}$ and $1/2^{1001}$, infinitely many of them still add up to infinite length.

So, we need to come up with some other way of showing an uncountable set has zero length.

Fortunately, our good friend Georg Cantor came up with a set that will help us out.

Cantor’s set3 is perhaps the simplest example of a fractal, by which we’ll, informally, mean a shape or set that is more or less self-similar as you zoom in closer.

To start, take the interval $[0,1]$, all the numbers between 0 and 1.

Then, remove the middle third of the set.

Now, we have two smaller intervals, each with length 1/3. From each of those, remove the middle third again.

Now, we have four intervals. We continue this process infinitely many times. What’s left over is the Cantor set!

If we calculate how much length was left at each step, we started with length 1. After the first step, we had 2 intervals of length 1/3, for a total of $2\cdot \frac13$. After the second step, we had $4 = 2^2$ intervals of length $1/9 = 1/3^2$, for a total of $2^2 \cdot \frac1{3^2} = \frac49$. Then $2^3 \cdot \frac1{3^3} = \frac{8}{27}$, and so on. After $n$ steps, the total remaining length would be $\left(\frac{2}{3}\right)^n$. As we do this process infinitely many times, this remaining length goes to zero.

Thus, the Cantor set has zero length!

Of course, at first glance, this set doesn’t seem like there’s much there. After all, we removed “everything,” right?

But let’s look a bit closer.

First of all, the endpoints of each interval along our process is in the Cantor set. For instance, the points 0, 1/3, 2/3, and 1 were never removed.

At first glance, these endpoints seem like the only points left. I mean, we keep on cutting out the heart of every remaining interval!

And, if the endpoints are all that’s left, that would only be countably many points, since we can count them. (Just order them up in the same order we cut out the intervals.)

But, if you look even closer, it turns out that the Cantor set does have uncountably many numbers in it. But to figure out why, we’ll need the ternary representation of the numbers.

The ternary expansion is the base 3 version of decimal expansion. For decimals, 0.012 represents 0 tenths, 1 hundredth, and 2 thousandths. In base three, the ternary expansion 0.012 represents 0 thirds, 1 ninth, and 2 twenty-sevenths. In other words, the ternary places are powers of 3 instead of powers of 10. In ternary expansions you only use the digits 0, 1, and 2.

Yeah, definitely weird the first time you see it.

But ternary expansions are perfect for the Cantor set. For instance, the points 0, 1/3, 2/3, and 1, in ternary, are represented by 0, 0.1, 0.2 and 1! In fact, the endpoints of the intervals are all numbers whose ternary representations stop after a finite number of digits.

So, what about those intervals we removed?

The first one was all the numbers between 1/3 and 2/3, or, in ternary, between 0.1 and 0.2. In other words, except for 0.1, we have removed all the numbers whose ternary expansions have the digit 1 in the first slot, the “thirds.”

The second set of intervals was [1/9, 2/9] and [7/9, 8/9]. In ternary, those are [0.01, 0.02] and [0.21, 0.22]. Thus, except for the endpoints 0.01 and 0.21, we have removed all the numbers whose ternary expansions have the digit 1 in the second slot, the “ninths.”

We can carefully continue this pattern. At each step, we are removing the numbers whose ternary expansions have ones in them.4 And these are the only numbers which we’re removing.

Thus, the Cantor set is all numbers whose ternary expansions have only the digits 0 and 2, except, perhaps, a terminal 1.

So what did we gain from all this complication?

In addition to the endpoints, which are all decimals that end, we also have a whole bunch of numbers that don’t end, like $0.0200022222002020202222\cdots$. We’ve found the extra points!

These numbers look a lot like normal decimals, just a bit restricted. In fact, they’re so similar, that, like normal decimals, there are uncountably many of them. You can even use the same argument we used in the post A bigger infinity for the normal decimals to show that the Cantor set has uncountably many numbers in it.

So, there we have it. Every countable set has length, or measure, zero, but uncountable sets can have length zero as well.5

Of course, any uncountable set is still much bigger than any countable set like the counting numbers $\{1, 2, 3, \cdots\}$, so it seems unfair to lump them together. So, one of these weeks, we’ll show that the Cantor set is different than a countable set. They may both have length zero, but it turns out that the Cantor set is not a zero dimensional set!

Figuring out what that even means will be half the fun!

But, before that, I want to talk about sets so weird that you can’t even measure them. And I don’t mean that their length is zero — That would still be measuring that they were length zero.

I mean sets so weird that you can’t make sense of what it means to measure them. They simply break our method of measuring sets.

<– Previous Post: How Long is Infinity?
First post in this series: How Long is Infinity?
–> Next Post: Non-measurable Sets That Go Bump in the Night

1. Briefly, a countable set is one that is infinitely big, but you can count, like the counting numbers, $\{1, 2, 3, \cdots\}$. A less obvious example is that all rational numbers (numbers like 2/3 or 17/28) are countable also. An uncountable set, which we’ll get to in a second, is a set with so many things in it that you can’t count them. An example would be the interval [0,1], all the numbers between 0 and 1. The fact that these are different is not at all obvious. If you’re interested in learning more about the different sizes of infinities, you could read the first few posts of this blog, starting with Infinity plus one
2. If you learn all this “measure theory” carefully, you’d find out that it is by definition that you can only add up the lengths of countably many sub-lengths. That part of the definition is exactly to avoid the contradictions with uncountable sets of the type we’ll describe here.
3. Really, there are many similar sets that are given this name, but we’ll start with the most common one.
4. Except, perhaps, as the very last digit. These, as we’ve mentioned represent some of the endpoints. Of course, recall that in base 10, $0.0999\cdots = 0.1$, and similar, so we could actually get rid of these terminal 1’s by replacing them with the digits $\cdots 0.02222\cdots$. Thus, we have no 1’s at all!
5. To be clear, “most” uncountable sets don’t have zero length. The Cantor set is one exception. Intervals like [0,1] are uncountable and have length.

## How Long is Infinity?

In our very first posts we talked about how big infinity is, and how there is more than one size of infinity — countable infinity, which is infinite but you could count it, and larger, uncountable infinities, which are so large that you cannot count them.

The standard example for countable infinity is the counting numbers (1, 2, 3, etc.). Clearly infinite, but also you can clearly count them. For uncountable infinities, the standard example is all the numbers, say between 0 and 1. This is also clearly infinite, but no matter how you arrange it, you can’t count all of those numbers.1

But the size of infinity, which is measured by directly comparing which things are in which sets, is different than the length of infinity.

We want a normal kind of length — The length of all the points between 0 and 1 should be 1. Similarly, a single point should have zero length.

So, somewhere between a single point and all the points between 0 and 1, we go from length zero to length one. Where did it happen? Two points has no more length than one point, and the same goes for 10 billion points. Similarly, if I take all the numbers between 0 and 1, and take away a single point, the length of all those points should still be 1.

The famous non-mathematical version of this is the sorites (so-RITE-eez) paradox. If you have a heap of sand, and take a single grain away, you still have a heap of sand. But if you keep removing one grain at a time, eventually you will only have a single grain remaining, and that’s clearly not a heap. So when did it stop being a heap?

How do we measure the length of infinity?

As commonly occurs in math, the answer is to carefully define what we mean by “length.”

Let’s start with what we can all agree on — the length of an interval.

An interval is all the numbers between two endpoint numbers. For example, $[0,1]$ is all the numbers between 0 and 1, including 0 and 1, while $(-17,4)$ is all numbers between -17 and 4, not including -17 and 4.2

Whether or not an interval contains its endpoints, we can all agree that the length of that set should be the right endpoint minus the left endpoint. For example, the length of $(-17,4) = 4--17 = 21$.

Great, now for the complicated part.

We need to use intervals to define the length of any set of points.3 What we’ll do is estimate the length of the set using intervals.

For any set, we can cover it using intervals. For instance, if our set was the single point 0, we could cover it with the interval $[-1/2,1/2]$.

If our set was $\{1, 2, 3\}$, we could cover it with the intervals $[1/2,3/2]$, $[7/4, 9/4]$, and $[23/8,25/8]$.

Since we’re using intervals, the total lengths of these intervals is easy to calculate. In the first case, the length was 1, and in the second case the total length was $1+1/2+1/4 = 7/4$.

The intervals we choose contain the set we care about, and so the length of the set should be less than the length of the intervals containing it. So, the length of the single point 0 should be less than 1, and the length of $\{1, 2, 3\}$ should be less than 7/4.

Of course, we could have picked other intervals to cover the sets. The interval $[-1/4,1/4]$ or $[-1/8,1/8]$ would also contain the point 0, and so the length of zero should also be less than 1/2 and less than 1/4.

The length, or measure, of a set is defined to be the smallest interval length (or sum of lengths, if we use more than one interval) that contains the set we care about.4

Going back to the single point example, the point 0 is contained in $[-1/8,1/8]$, but also in $[-1/10^8, 1/10^8]$ or $[-1/10^{100}, 1/10^{100}]$. In other words, we can cover it with intervals of smaller and smaller lengths, heading towards zero. Thus, by our definition, the measure of the set $\{0\}$, the single point 0, is zero. In other words, a single point has no length.

The same kind of argument works for any finite set of points. You take smaller and smaller intervals around each of the points, and so the total length of the intervals go to zero.

This shows that the measure of any finite set is zero.

What happens if we move to infinite set?

The simplest infinite set is the counting numbers, 1, 2, 3, etc.. If we try the exact same thing we did with a finite number of points and cover each point with an interval of the same length, no matter how small each individual interval is, the total length of intervals would be infinite.5

This is not wrong, per se, but remember that our sum of interval lengths is supposed to be an estimate of the length of our set. It’s possible the counting numbers should have infinite length, but let’s see if we can do better than that.

To try to improve our estimate, we’ll put smaller and smaller intervals around each subsequent number. So, we cover 1 with $[1/2, 3/2]$ (length 1), cover 2 with $[7/4,9/4]$ (length 1/2), cover 3 with $[23/8,25/8]$ (length 1/4), etc.

Thus, we managed to cover all the counting numbers with a collection of intervals of total length $1+\frac12+\frac14+ \cdots + \frac1{2^i} +\cdots =2$.6 That means the measure (i.e., length) of the counting numbers is less than 2.

Of course, we didn’t have to start with an interval of width 1. We could have covered 1 with $[3/4, 5/4]$, 2 with $[15/8, 17/8]$, etc. In this case, we’d have a total length of $\frac12 + \frac14 + \frac18 +\cdots = 1$. So the measure of the counting numbers is less than 1.

Continuing this idea, we could start with smaller and smaller intervals, and end up with a total length of 1/2 or 1/4 or 1/8 and so on. By our definition, the length of the counting numbers has to be zero!

In fact, this same idea works for any countable set, i.e., any set you can count. You cover the first point with a small interval, the second point with a smaller interval, etc. until you’ve covered them all. Then, you try again with even smaller intervals. Thus, the measure of any countable set is zero!

Now, this doesn’t seem very interesting when worded like this, but let me give you a slightly more amazing example.

A rational number is a number that can be written as the fraction of two counting numbers, maybe with a minus sign. So, 3/4 and -12374/421 are rational numbers, but $\pi$ is not. Since any number can be approximated by a rational number (e.g. $\pi \approx \frac{22}{7}$), the rational numbers are everywhere.

There are so many rational numbers that, no matter which two numbers you pick, there are infinitely many rational numbers between those two numbers.

It’s surprising, then, that there are only as many rational numbers as there are counting numbers! More details are available in The size of infinity, but the basic idea is that you can line up the rational numbers so that you can count them. In other words, you can list them in a definite order — a first rational number, a second, a third, etc.

But since we can order them in this way, we can put an interval of length 1 on the first rational number, an interval of length 1/2 on the second, an interval of length 1/4 on the third, etc. Thus, the length of all the rational numbers is no more than 2.

And, of course, we can use smaller and smaller intervals, and thus show that the rational numbers have no length at all!

Bizarre, right? Numbers can be dense (which is the technical way to say they’re everywhere, no matter how far you zoom in), but still be so close to nothing that they have no length at all!

The length of (countable) infinity is always zero!

5. Importantly, you cannot just think of each point as having length zero, and then adding up infinitely many zeros to get zero. That… doesn’t make sense. What you’re trying to say is that the length should be $\infinty \cdot 0$. But anything times zero is zero, and anything times infinity is infinity. So what should $\infinity \cdot 0$ be? Zero or infinity? Or something else? The fact of the matter is that we need more information. Sometimes it makes sense to say it is zero, sometimes infinity, and sometimes some other number, like 7. We need to carefully use our definition of length in order to know which one is correct for this circumstance.
6. In case you’ve never seen this before, suppose that $1 + \frac12 + \frac14 + \cdots$ added up to some number $s$. Well, then if we multiply that number $s$ by 2, that’s the same as multiplying all of those numbers together and then adding them up. Thus $2s = 2 + 1 + \frac12+\cdots$. But, $2s-s = s$, so if we subtract the two sums, the 1’s cancel out, the 1/2’s cancel out, the 1/4’s cancel out, etc., and we’re left with $s = 2$. Thus this sum is 2.