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

## Kurt Gödel’s Story

It is my impression that, even among mathematicians, mathematical logicians are a bit weird. Kurt Gödel was no exception.

Gödel is famous for proving foundational questions about mathematics. He asked questions like, “Can I prove that math is consistent?” and, “If I have a true statement, can I prove that it’s true?” and, “Can I prove that it’s impossible to prove the statement ‘This statement is unprovable’ is provable?”

Yeah, not exactly the most obvious questions to ask, but important ones, I promise.

Gödel was born in 1906 in what is now Brno, Czech Republic, but was then in Austria-Hungary. His family called him Herr Warum (“Mr. Why”), which is impressive given how fond children everywhere are of that question.

By the time he went to the University of Vienna at 18, he had already mastered university-level math. During this time, he came across Russell’s work on the foundations of mathematics, and met Hilbert, who, around that time, was thinking deeply about axioms and logical systems, and whether it could be shown they had no contradictions, and whether all true statements could be proven.

By 23, Gödel finished his PhD in mathematical logic. Two years later, he published his seminal work on his incompleteness theorems. These papers have the answers to the questions I introduced, but I want to finish talking about Gödel. We’ll discuss the details next time.

Two years after that, in 1933, Gödel became a lecturer at the University of Vienna. He also traveled to the US, where he met Einstein, who became his good friend.

During this time, Hitler came to power in Germany. A few years later, the professor who had originally interested Gödel in logic was assassinated by one of his former students, essentially because he was friends with Jews.1 This caused a “nervous crisis” in Gödel. He became paranoid, fearing that he would be poisoned. These symptoms continued later in his life.

In 1938, Nazi Germany annexed Austria. Gödel’s job title was eliminated, so he had to apply to a new job. However, since he had been friends with Jews, they turned him down.

Things got worse the next year. Germany found him fit for conscription, and World War II began. Within the year, Gödel left for Princeton, at the Institute of Advanced Study, where Einstein was.

And, being Gödel, he decided that an Atlantic crossing was too much. So he took the obviously less strenuous route of a train ride across Russia to Japan, a boat ride across the Pacific, then another train ride to Princeton, New Jersey.2

He was very productive during his time in Princeton, proving some other results about the foundations of mathematics.

In 1947, Einstein took Gödel to his US citizenship exam. Gödel, being a constant logician, told Einstein he had discovered an inconsistency in the US constitution that could allow the US to become a dictatorship. Einstein was concerned… not about the possibility of a dictatorship, but that Gödel’s eccentric behavior might endanger his citizenship application.

Einstein was right to fear.

During Gödel’s hearing, the judge asked what kind of government they had in Austria. Gödel replied that it was a republic, but that the constitution was such that it was changed into a dictatorship. The judge expressed his regret, then said that this could not happen in this country.

Gödel replied, “Oh, yes, I can prove it.”

Fortunately, the judge was an acquaintance of Einstein’s, and said, “Oh God, let’s not go into this.”2

Anyway, Gödel kept on working. Among other things, for Einstein’s 70th birthday, Gödel created a spacetime which… breaks general relativity. Well, at least, it has all sorts of things go wrong. For instance, there are “closed timelike loops” through every point of spacetime, meaning that anyone and everyone can time travel. He also expanded Leibniz’s “proof” of God’s existence.

Later in his life, his paranoia recurred. He had an overwhelming fear of being poisoned, and would only eat food that his wife prepared for him. When she was hospitalized for 6 months, he refused to eat, eventually starving to death. At the time of his death, he weighed only 30 kilos.

In the next post, we’ll get to talk about Gödel’s completeness and incompleteness theorems, and come face to face with the inherent limitations of mathematics!

(For those of you who enjoyed this, you might also enjoy my articles on Georg Cantor and Karl Schwarzschild!)

1.  Though Schlick was not a Jew, his murder became a cause of celebration, which fed the growing anti-Jewish sentiments in Vienna. When Germany annexed Austria, the murderer was released, having only served 2 years of a 10 year sentence.
2.  To be fair, his exit visa explicitly stipulated the trans-Siberian route. The Atlantic crossing was dangerous during the war. More details can be found here
3.  The constitutional problem that Gödel found was never recorded, but a good guess is that he was referring to Article V, which allows the constitution to be amended. Though it is very hard to pull off, you could, in theory, change the constitution to allow amendments relatively easily, say by a majority of both houses of congress. This is essentially what the constitution of the Weimar republic (pre-WWII Germany) said. Once the constitution is easy to change, it is a (relatively) simple matter to make the president a dictator. Germany’s Reichstag (congress) made Hitler a dictator in this way.

## Where do axioms come from?

In the last post, we talked about what math is. To me, math is a quest of understanding what must be.

The basis for this quest are the axioms and definitions of mathematics. Definitions describe what we are talking about, while axioms describe what we assume those objects can do.

Where do those axioms and definitions come from?

Since math is taught so authoritatively, it can seem that the definitions and axioms of mathematics are part of what must be. That may be true to some extent, but that is not how math is done.

As we try to increase our mathematical understanding, our needs change. We realize that certain ideas or definitions we used before weren’t quite precise or rigorous enough to deal with the questions we want to ask now. Sometimes, we find out that our previous understanding was simply lacking.

In this post, I’d like to give some of the motivating reasons for the axioms and definitions we commonly use in mathematics. The reasons are general and overlap, and are probably not exhaustive.

The first of these reasons is trying to codify intuitive ideas.

For an example we can go back to calculus.

The idea of a “continuous function” is fairly simple; a function is continuous if, when you graph it, you don’t have to lift up your pencil.

For many purposes, that intuition is sufficient. But, if you needed to, how could you make this definition precise?

Though calculus was invented in the mid 1600’s, it wasn’t until 1817 that Bernard Bolzano gave the modern definition of continuity. His “epsilon-delta” definition also demonstrates another common occurrence for new, precise mathematical definitions. Even though the intuition for them is fairly clear, the technical details can be very confusing.

The more intuitive way to say his definition is “A function $f(x)$ is continuous at a point $x_0$, if inputs near the original input $x_0$ give outputs near the original output $f(x_0)$.” This makes more precise what we mean when we say a continuous function has no jumps.

But the precise way of stating this is “A function $f(x)$ is continuous at a point $x_0$ if, for any $\epsilon >0$, there exists a $\delta>0$ so that, if $|x-x_0|<\delta$ implies that $|f(x)-f(x_0)|<\epsilon$.”1

One of the first jobs of any math major beginning his or her “proofs” classes is to really internalize this definition. It, and its variations, come up all over the place.

Axioms and definitions are sometimes invented trying to answer the question, “what makes this proof work?”

It almost feels like cheating–you know the outcome you want, so just assume the things that makes it work!

If you’ve taken calculus, probably the most important theorem you learned was the Fundamental Theorem of Calculus. One way to state this theorem is “If $F(x)$ has a (continuous) derivative, then $F(b)-F(a) = \displaystyle\int_a^b F'(x)\,dx$.” In other words, the integral of the derivative is the original function.

But the assumption that $F(x)$ has a continuous derivative is stronger than really necessary. For instance, the theorem still works for $F(x) = |x|$, even though $|x|$ does not have a derivative (i.e., a well defined slope) at $x=0$.

So what property does a function need to make the fundamental theorem work? Somewhere in the proof, at some point you need to use that $F(x)$ has a continuous derivative. But if you look closely, you find you don’t quite need that condition. Instead, you need something a bit weaker. That precise condition is just given a name, absolutely continuous. (You can see the definition here on Wikipedia.)

Absolute continuity is not a basic, obvious definition or idea. It’s not very elegant in anyone’s view. It’s simply the condition that makes the proof work.

“What makes it work” might not be very elegant, but it is how math is done.

If we don’t know how to prove the theorem we want to, we’ll often ask, “What extra condition could we assume that would make it possible to prove this theorem?” And then we assume that condition holds, and often give it a name like “tame” or “well-behaved.” The conditions aren’t special or elegant–but they work.2

Another way that definitions are invented is when mathematicians want to generalize an idea to a more general situation. Another way to say this is that mathematicians are trying to somehow identify the intrinsic something of an idea.

This is a major theme of modern mathematics. “What does it mean to be a shape?” “What does it mean to multiply things?” These two questions lead to the complete reformulations of branches of mathematics.

Until Bernhard Riemann, a shape was always visualized in the plane or in space (or perhaps a higher dimensional $\mathbb{R}^n$.) But what makes a shape a shape? Riemann asked this question, and decided that the property that makes a shape a shape is that, at any point of the shape, you can travel in a certain number of directions. (In 3 dimensions, this would be up/down, left/right, and forward/backward.)

The usual visualization of shapes in space was a crutch that distracted us from the intrinsic properties of that shape. These “many-fold quantities,” as Riemann called them, or manifolds, as we call them now, have become the basis for geometry. (We’ve talked extensively about manifolds in this blog, starting here.)

Multiplying numbers has been done for as long as math has been done. More recently, multiplication of matrices has become useful. But what makes multiplication multiplication?

Answering that question leads to the idea of a group, the basis of the field of abstract algebra. A group is a bunch of things that you can multiply. You don’t really care what these things are (matrices, functions, numbers, shapes, symmetries, etc.), as long as you know how to “multiply” them. The general rules for what multiplication must do are the axioms of a group.3

These kinds of generalization often seems weird and/or useless when you’re first introduced to it. Even worse, it always feels like you’re adding a layer of complexity to something that is already complicated enough.

But stripping away the extra details and focusing on the core ideas turns out to be very valuable. First, sometimes it makes it easier to prove results you care about. Second, by unifying very disparate ideas (such as matrix multiplication and rotations and normal multiplication), if you can prove a theorem about groups in general, than it applies to all of these very different situations.

Finally, sometimes we have to come up with new axioms because our old ones were just plain wrong.

Because math is an investigation into what must be, we really don’t like when there are contradictions. In fact, we feel like there shouldn’t ever be contradictions. After all, we proved everything, right?

But contradictions and paradoxes come up all the time.

Usually they’re just an indication that you made a mistake somewhere in your reasoning. (I’m intimately familiar with that one…)

And often, mathematical theorems or examples can seem paradoxical, but really the only problem is with your intuition.

But occasionally, real problems are found.

One of the most prominent examples of this is Russell’s paradox.

Intuitively, a set is any collection of objects you can define. For instance, the integers between 1 and 5 are a set, $\{1, 2, 3, 4, 5\}$. All the natural numbers is a set. You can have more complicated sets, like the set of all sets of numbers.

Georg Cantor, among others, had enumerated what things you could do with sets.4 But a naive interpretation of sets, which works well enough for most purposes, leads to contradictions.

Russell’s paradox is this: Consider the set $R$, which is the set of all sets which are not in themselves.

Yeah, that’s weird. Maybe an easier one to get your head around is “the set of all sets.” Since it’s a set of all sets, and it is a set, the set of all sets has to contain itself.

The set $R$, the set of all sets which are not in themselves, is even weirder. But (naively) $R$ is a set because we can define it.

Is $R$ in itself?

If $R$ is in $R$, then $R$ is a set which contains itself. But that means (since $R$ is the set of all sets which are not in themselves) that $R$ can’t be in $R$.

Got a headache yet?

Okay, so maybe $R$ is not in $R$. If it isn’t, though, the definition of $R$ (again, the set of all sets which are not in themselves) means that $R$ must be in $R$!

In other words, $R$ can’t be in $R$, but that means it must be in $R$, but that means it can’t be in $R$, but that means it must be in $R$, but that means…

This is a lot like the infamous statement, “This statement is false.”5

This is a proper paradox.

In order to clear up Russell’s paradox, along with a family of other paradoxes that come along with a more naive approach to set theory, new axioms were needed.

Over the next few decades, the now-standard Zermelo-Fraenkel axioms of set theory were developed. These axioms are designed to allow you to do most things you think you should be able to do with sets, like combine them and compare them and such, but they avoid paradoxes that can creep in if you try to allow everything.

To conclude, axioms and definitions are invented for many reasons, ranging from an attempt to make precise an intuitive idea to an attempt to remove paradoxes.

But math works, as long as we pick reasonable axioms, and we can use it to learn everything that must be.

Right?

Actually, it’s not quite so simple. There are fundamental limits on what we can use mathematics to understand. The only other option is that math is self-contradictory.

That is the content of Gödel’s incompleteness theorems. And that’s what we’ll talk about next time.

Sorry for the delay for this post. We’ve been writing posts weekly for six months. Unfortunately, that turns out to be an unsustainable pace with all the other things we have to get done. We’ll continue to post, but it will be less often than before. Feel free to subscribe to get an email when we post!

1. And this is not the most confusing definition. Another definition (often, but not always equivalent) is “The inverse image of an open set is open.” I don’t want to define those terms here, but this definition, though very useful, is even less intuitive than Bolzano’s.
2. My impression is that this is how “Hilbert spaces” got their name. Hilbert spaces are infinite dimensional vector spaces, with a way to measure lengths of vectors, and angles between them. That is all very natural. But Hilbert spaces have the additional property that they are “complete,” essentially meaning that there are no “vectors missing” from the space. This condition is very important in being able to prove anything about infinite dimensional vector spaces. Hilbert had a number of papers about these complete vector spaces, and others found them useful, and so started calling them Hilbert spaces.
3. There are four axioms of a group. 1. Multiplication of things in the group have to stay in the group. 2. Multiplication is associative, i.e., $(a\cdot b)\cdot c = a\cdot(b\cdot c)$. 3. There is a “1,” meaning anything you multiply by “1” stays the same. 4. Everything has an inverse, so that if you multiply them together, you get “1.” There are lots of examples of groups, such as the positive numbers, or invertible matrices. But there are less obvious examples, like the set of all rotations in space, $SO(3)$. These are a group since, if you do one rotation, then another, that is the same as doing one big rotation. (Doing one rotation, then another, i.e., composition, is the “multiplication.”) The “1” rotation is the rotation of zero degrees, i.e., doing nothing. And the inverse is undoing the rotation you just did.
4. I don’t say “wrote down axioms” because he never actually wrote down precise axioms for his set theory.
5. Perhaps even more accurately, the set $R$ is like “the smallest number that can’t be described in less than 13 words.” It seems to make sense, but, looking closer, there’s obviously some sort of problem with this number.