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

What about larger infinities? We’ll talk about that more next time.

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)$

## Gödel’s Incompleteness Theorems

In the last couple of posts, we’ve talked about what math is (a search for what must be) and where the foundational axioms and definitions come from.

Mathematics tries to prove that statements are true or false based on these axioms and definitions, but sometimes the axioms prove insufficient. Sometimes the axioms lead to paradoxes, like Russell’s paradox, and so a new set of axioms are needed. Sometimes the axioms simply aren’t enough, and so a new axiom might be needed to prove a desired result.

But in both cases, the paradoxes and inability to prove a result are the result of picking the wrong axioms.

Right?

Unfortunately, it’s not true!

Gödel’s incompleteness theorems show that pretty much any logical system either has contradictions, or statements that cannot be proven!

The questions Gödel was trying to answer were, “Can I prove that math is consistent?” and, “If I have a true statement, can I prove that it’s true?”1

Gödel’s first step in this project was in his PhD thesis. That result seems to imply that you can prove any true statement. This is called Gödel’s completeness theorem.

For a particular set of axioms, there are different “models” implementing those axioms. A model is an example of something that satisfies those axioms.

As a non-mathematical example of a model, let’s say the axioms that define being a “car” are that you have at least 3 wheels, along with at least one engine that rotates at least one of the wheels. A standard car clearly follows those axioms, and is therefore a model for the “car axioms.” A bus would also be a model for the car axioms.

Of course, there are models that are very non-standard…

Mathematical axioms work the same way. There are axioms for the natural numbers, and their addition and multiplication, called “Peano arithmetic” (pay-AH-no). The normal natural numbers, $\{1, 2, 3, \cdots\}$ follow these axioms, so are the standard model for them. But there are non-standard models that still follow the Peano arithmetic axioms.

Each model is a bit different. There may be some statements (theorems) that are true in some of the models, but not true in another model.

Even if a statement is true, though, you want to be able to prove it true, using only the axioms that your model satisfies.2

Gödel’s completeness theorem answers the question, “Using the axioms, is it always possible to prove true statements are true?”

His completeness theorem says you can prove a statement is true using your chosen axioms if and only if that statement is true in all possible models of those axioms.3

This result seems very promising for mathematics.

Unfortunately, math is not that simple.

Two years after Gödel published his completeness theorem, he published his incompleteness theorems.

These theorems relate two concepts: consistency and provability. A logical system (a set of 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 lots of 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 logical system (i.e., a set of axioms with no contradictions) in which you can do a certain amount of arithmetic4, then there are statements in that system which are unprovable using just that system’s axioms.

In other words, as long as your logical system is complicated enough to include addition and multiplication, then your logical system is incomplete. There are things you can’t prove true or false!

Gödel’s second incompleteness theorem gives a specific example of such an unprovable statement. And the example is quite a doozy.

The theorem says that inside of a similar consistent logical system (one without contradictions), the consistency of the system itself is unprovable!5

You can’t prove that math does not have contradictions!

In the next post, I plan on giving an outline of the proof of these theorems, but for this post, let’s talk about their fascinating consequences.

Remember what I said I thought math is?

Math is the quest to decide what must be. But Gödel’s incompleteness theorems put fundamental limits on that quest!

David Hilbert, among others, felt that any true statement should be provable, and that math should be provably consistent.

In 1900, he gave a famous list of open problems in mathematics, the most important ones for the next century. His second problem was, “Prove the axioms of arithmetic are consistent.”6

Gödel’s theorems show that Hilbert’s hope was exactly… wrong.7

As long as your mathematics is complicated enough to include the natural numbers (which, I think we can agree, is not a particularly high bar), then it must have statements which cannot be proven true or false. They are unprovable.

Of course, to “fix” this you could try to add that statement as an axiom.8

Then, since the statement is an axiom, it is trivially provable. (The proof is: “This statement is an axiom. Thus it is true.”)

Yeah, it’s kind of cheating. But the problem is, you can’t even cheat enough to win!

See, your new mathematical system, with your shiny new axiom, is still a mathematical system complicated enough to include the natural numbers. Gödel’s theorem still applies, and shows that there is some new statement that is unprovable! It’s worse than trying to kill a hydra.

Looking at the proof, the vaguest idea of an unprovable statment is “This statement is unprovable,” which seems… silly, and not worth your time. You might hope that all unprovable statements are like that: unprovable, but totally uninteresting.

Unfortunately, mathematicians have found statements of the kind that you might hope to prove, that are unprovable in standard mathematical systems. For instance, it is impossible to prove or disprove that the real numbers have the smallest uncountable cardinality9 inside of standard set theory. There are lists of other such important, but unprovable, statements.

So, in pretty much any mathematical system, there are things you’ll want to prove, but can’t.

And that’s just the first incompleteness theorem.

The second incompleteness theorem says that, within your mathematical system, you cannot prove that you can’t have contradictions.

If you’ve proven the statement “there are no contradictions in the system”, your system cannot be consistent because the second incompleteness theorem proved that since your system is complicated enough to include arithmetic, there must be contradictions in the system. Which means–since you’ve proven there are and are not contradictions in the system, your system is inconsistent.

Thus, if you can prove there are no contradictions, then the second theorem says that your system does have contradictions!

Now, using a more powerful system (one with more axioms), you can often prove the consistency (lack of contradictions) of a less powerful system (one with fewer axioms). For instance, Peano arithmetic, which covers essentially the natural numbers and addition and multiplication, can be proven to be consistent with standard (ZFC) set theory, a more powerful system. But Peano arithmetic can’t prove itself consistent.

This leads to a philosophical problem: How do we know standard set theory is consistent? Sure, there are even stronger systems that can prove it’s consistent, but then we have to ask about their consistency. If we keep on adding axioms to prove consistency, have we really proven consistency? We may have inadvertently added contradictions as well!

One last weird thing.

Gödel’s completeness theorem implies that a statement is provable using a set of axioms if and only if that statement is true, for every model of the set of axioms. That means that for any unprovable statement, there has to be a model of those axioms for which the statement is false.

But, if the consistency of the set of axioms is unprovable, that means there has to be a model of your axioms where the consistency statement is false.

Which hurts my head to think about.

Anyway, next time I’ll explain the basic idea of the proofs of these results. It should be fun!

1.  Man, these sound kind of weird, even to me. I mean, the statement is true, right? So isn’t it obvious?
2. A statement can be true, even if you can’t prove it as such. (Usually it just means you’re not clever enough.)
3.  This formulation is not Gödel’s original formulation, but it is very closely related. More technically, the axioms should form a “first-order theory” with a “well-orderable language,” but there’s not need to go into details here. We’ll leave these for you to explore on your own
4.  In particular, it needs to include Peano arithmetic, which includes addition and multiplication of the natural (counting) numbers.
5.  Technically, there is a particular statement of the consistency of the system that is unprovable. There can be several inequivalent such statements.
6.  His first problem was the continuum hypothesis (“Are the real numbers the smallest uncountable infinity?”) which has always confused me. Shouldn’t the consistency of mathematics go first? Kinda fundamental, right? Bah.
7.  To be fair, there are mathematical logicians that disagree with me, but I think most mathematicians agree with me.
8.  You should worry that the logical system is still consistent with that statement as an axiom. However, since you can’t prove it true or false, it has to be consistent if you add the unprovable statement.
9.  We talked about uncountable sets and cardinality in earlier posts.