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

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!

1. The proof is in the post A bigger infinity. It’s really cool that there is more than one size of infinity. In fact, there are infinitely many different sizes of infinity. For each size of infinity (like the size of the real numbers), there is a larger infinity. We talked more about that in the post An even biggerer infinity
2. Intervals containing their endpoints are called closed, while those not containing their endpoints are called open
3. Well, technically not any set of points — there are unmeasureable sets, but they’re weird and unusual. In fact, you can’t even prove they exist using some standard sets of axioms. I’ll probably talk more about these sets in a later post.
4. In other words, the infimum of the sum of interval lengths, where the infimum is taken over all (countable) collections of intervals that cover the set.
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.

## How Gödel Proved Math’s Inherent Limitations

Gödel’s incompleteness theorems are the kind of theorems that break your brain.

In the last post, we discussed the theorems themselves, and their consequences. In short, they show the inherent limitations of mathematics.

The first theorem relates two concepts: consistency and provability. A mathematical system (a set of assumptions which are called axioms) is consistent if there aren’t any contradictions. In other words, you can’t prove a statement both true and false.

Inside of any logical system, there are many statements, i.e., things you can say. I could say something like “All prime numbers are smaller than a billion.” It’s a false statement, but I can say it.

But just because I can say a statement doesn’t mean that I can prove it true or false. Most of the time, the statement is just very difficult to prove, and so you don’t know how to do it. But it’s also possible to have statements which are impossible to prove either true or false. We’ll call these kind of statements unprovable. Any logical system (set of axioms) with unprovable statements is called incomplete.

Gödel’s first incompleteness theorem says that if you have a consistent mathematical system (i.e., a set of axioms with no contradictions) in which you can do a certain amount of arithmetic, then there are statements in that system which are unprovable using only that system’s axioms.1

In other words, math is incomplete. It is impossible to prove everything.

The most basic idea of the proof of the first incompleteness theorem is to think about the statement, “This statement is unprovable.”

If you could prove this statement true, it is by definition provable. But the statement itself says that it is unprovable, and so, since it is true, the statement is also unprovable! But it can’t be both provable and unprovable. Thus the statement must be only unprovable.

While this is the basic idea we’ll employ, the problem is that there isn’t an obvious formal way to say “This statement is unprovable” inside of math. What do you mean by provable? What does “this statement” refer to? Using which axioms?

Gödel’s proof has to make all of that perfectly precise.

The first step is to show that any precise mathematical statement can be transformed into a number, and vice versa.

This step is clever, but not particularly complicated. At some point, you’ve probably come across a code where each letter is exchanged for a number. If we do a to 1, b to 2, etc., for instance, the word “math” would be “13-1-20-8.” Computers use a similar scheme to store text as 1’s and 0’s.

The number Gödel assigns to a precise mathematical statement uses a similar encoding. There are several ways to do this, but I’ll mention a way similar to how Gödel originally did it.

First, associate each mathematical symbol (in your particular mathematical system) with a unique counting number.2 For instance, maybe “0” is saved as 1, while “=” is saved as 2 and “+” is saved as 3.

An mathematical statement is just a list of these symbols. Equivalently, the statement is a list of the numbers we used to encode the individual symbols. For instance, $0=0$ is equivalent to $(1,2,1)$.

To encode the statement as a single number, we set the Gödel number equal to the the product of the first few primes, raised to the powers in the corresponding position in the list. Thus, the Gödel number of $0=0$ is $2^1 \cdot 3^2 \cdot 5^1 = 90$.

For a statement $S$ like “$0=0$”, we’ll use the notation $G(S)$ to refer to the Gödel number of that statement. Thus, $G(0=0) = 90$.

As you can imagine, Gödel numbers can get very large, very quickly, for even moderately long statements. But size is not an issue — we don’t need to write down those numbers, just know they exist.

The key issue is that we can take a number and go backwards to get a mathematical statement.

Every number can be broken up into primes in a unique way. So, $145530 = 2^1\cdot 3^3\cdot 5^1\cdot 7^2\cdot 11^1$, and so the number 145530 represents the statement $0+0=0$.

Any precise mathematical statement can be translated into a number this way. Even a proof is just a bunch of statements strung together. (“A” implies “B,” and “B” implies “C,” so “A” implies “C”.) That means we’ve shown that all of math3 can be written in terms of just numbers.

Similarly, there is a arithmetical way of checking whether a string of statements (as represented by a Gödel number) is a proof of another statement (as represented by another Gödel number.)4

While translating any mathematical statement into a number seems like an interesting trick, it turns out to be the key to the proof.

The reason it is so important is that it lets us turn any questions about proofs and provability into an arithmetic question about numbers. Thus, we can use only numbers and their properties in order to prove any (provable) statement.

For instance, consider the statement, which I’ll call $Unprovable(y)$. The statement is “$y$ is the Gödel number of a statement, and there does not exist a number $x$ which is the Gödel number of a proof of that statement.”

Thus, $Unprovable(y)$ essentially says “The statement represented by $y$” is unprovable. But, instead of a question about proofs and statements, it is a statement entirely about numbers, and some arithmetical relationship between them!

The exact arithmetical relationship is very, very complicated, but it can be precisely defined. An analogous, but much simpler statement to $Unprovable(y)$ could be $Prime(y)$ which we’ll call the statement “$y$ is a prime number.” Thus $Prime(y)$ makes a claim about a number, but that claim can be entirely decided just by some (relatively) simple arithmetic.

We’re coming into the homestretch now.

The original idea for the proof was the statement “This statement is unprovable.” With the precise mathematical statement $\latex Unprovable(y)$, we can make that imprecise statement perfectly precise.5

To come up with a precise version of “This statement is unprovable,” we’ll use the “diagonal lemma.” (A lemma is just a theorem you use to prove another theorem.6) The diagonal lemma shows that, in the kind of mathematical system we’re using for this proof, there is some statement $S$ which is true if and only if $Unprovable(G(S))$ is true.7 (Remember, the input to $Unprovable(y)$ is a number representing the Gödel number of a statement. In this case, that statement is $S$.)

To be clear, the lemma doesn’t prove that either $S$ or $Unprovable(G(S))$ is true, only that they are either both true or both false. But what does this mean?

Again, the diagonal lemma shows that $S$ (some unknown mathematical statement, probably quite long) is true if and only if $Unprovable(G(S))$ is true. But $Unprovable(G(S))$ being true means that $S$ is unprovable. (That was the definition of $Unprovable(y)$.)

So, if we were able to prove the statement $S$ true, then the diagonal lemma shows that we can prove $Unprovable(G(S))$ true. But $Unprovable(G(S))$ says that $S$ is unprovable! Thus $S$ is both provable and unprovable, a contradiction.

Thus $S$ must actually be unprovable.

The statement $S$ is the precise version of the statement “This statement is unprovable.” that we were looking for. Thus, not every statement can be proved.

Poor, broken math…

1. There are a few more technical assumptions about the mathematical system, such as that it must be “effective,” also known as “recursively enumerable.” Those assumptions are vital to the proof, but are more technical than I’d want to mention in the main body of the text for the lay reader. I’ll explain why the system needs to be effective in a later footnote.
2. The axiomization of arithmetic, Peano arithmetic, does not explicitly mention all of the natural numbers. In fact, it only mentions 0. Instead, it has the “successor function” $S$, which just calculates the next number. Thus $S(0)$ is the definition of 1, while $S(S(0))$ is the definition of 2. Because of this, when translating mathematical statements into their Gödel number, our code only needs to have numbers associated to 0 and to $S$, and not to all the numbers individually. That means our encoding has only finitely many symbols to worry about.
3. Well, any math that can arise from our axioms and choice of symbols.
4. In the last post, we ignored a lot of important technical assumptions. One of them comes into play right here. The assumption is that your mathematical system (i.e., your set of axioms) is effective. This essentially means that there is a computer program that could, in principle, list all the theorems in your mathematical system, without listing any not-theorems. This is true for Peano arithmetic, which is the basic mathematical system the incompleteness theorems were investigating, as well as the standard (ZFC) set theory. There are systems which are not effective, but they tend to be useless or not very interesting. For instance, one such system takes as its axioms “all true statements of arithmetic.” Thus, everything true is an axiom, and is thus trivially provable. The assumption that your mathematical system is effective is vital in showing that this arithmetical proof-checking works.
5. Gödel found a way to say this statement directly. We’re going to take a slightly different, though easier to understand, path. The main thrust of the proof is the same, though.
6. Lemmas are usually relatively easy to prove, as is the case with the diagonal lemma. However, the proof is technical, and not particularly enlightening.
7. The diagonal lemma works for any statement with a number you can plug in, not just the special statement $Unprovable(y)$