Mathematicians love simplicity. Back around 1900, their dream was to create a world of math that was cleanly split in two. True statements would all be provable from axioms. The false statements, none of them would be provable from axioms.

Kurt Gödel destroyed that dream with a single sentence. He found a statement which was true but not provable. Very roughly that statement was this statement is not provable. It seems simple but the details are far from it. Let’s dig into how this strange loop with its seemingly simple bit of self-reference destroyed the dreams of many mathematicians, but opened up a whole new world of mathematics.

Logicians Frege, Russell, Whitehead, and Zermelo all tried to avoid paradoxes and keep mathematics consistent. Their goal was to complete Hilbert’s program and find a set of axioms from which all known mathematical truths would follow. In short, to provide a foundation for all of math while avoiding this minefield of paradoxes that had popped up. Repeatedly, one of them would think they’d reach the goal and somebody else would dash their dreams. Gödel ended the string and showed that Hilbert’s program was futile. No axiomatic system was possible. That was the end result of Gödel’s work. On the other hand, as often happens with these paradoxes, his work revolutionized mathematics. And it spurred research in new directions. Let’s take a look where Gödel came from.

Kurt Gödel was born in Brün, Austria-Hungary in 1906. It’s around the same time Russell and Whitehead were writing Principia Mathematica and Albert Einstein was revolutionizing physics. He was German-speaking. His citizenship changed as various forces took over. It’s now part of the Czech Republic. He was Czech when he was 12 years old. He became an Austrian citizen before moving to Vienna at 18 to study at the University of Vienna.

In 1928, Gödel attended a talk by David Hilbert. It was in Bologna, Italy at an international math conference. At the ICM, Hilbert talked about some of the great unsolved problems. And he made an important distinction between statements that were true within a system and statements that were provable within that system. Hilbert’s program included the search for axioms that avoided paradoxes, like Russell’s paradox, and could prove all of the known mathematical truths.

In 1931, just three years after Hilbert’s talk, Gödel had proved this Hilbert’s program was impossible. He did that when he published “On Formally Undecidable Propositions in Principia Mathematica and Related Systems, Part One.” It was an attack on Russell and Whitehead’s axioms in the Principia.

This work contained Gödel’s first groundbreaking result, Gödel’s first incompleteness theorem. It’s a very technical result written in very challenging language, but basically it says any axiomatic system strong enough to include basic arithmetic will necessarily include a statement which is true but not provable within that system. It will always include one of these sentences, which is true, but you cannot prove using that system.

There’s a second big result in this paper. But first, to understand Gödel’s work we really have to understand the world Hilbert’s program would have ushered in. You know, if all mathematical statements could be divided into two kinds, true and false, that was his dream. The true ones, like 2 + 2 = 4, they would all be provable from a few simple axioms ike the Zermelo-Fraenkel with choice axioms. False statements, like 2 + 2 = 5, none of those statements would be provable from these axioms. It would be consistent, there’s no contradictions, and complete, all true statements would be provable.

What Gödel did is he managed to encode in mathematics a version of the sentence this statement is not provable. Its simplicity is really as amazing as its depth. And yet it hides this great complexity which we’re going to uncover today.

Why does this destroy Hilbert’s program? Well, let’s ask two questions about this sentence, this statement is not provable. It’s usually called a Gödel sentence. First of all, is it true and is it provable in whichever axiom system you have?

Let’s answer both of these. Let’s actually take the second one first. Is it provable? Well, if it were provable, then you could use it to prove that the Gödel sentence is not provable because that’s what it says. It says that the sentence is not provable.

Well, if you’re in a consistent system, you can’t prove both a statement and its opposite. And therefore, the statement must not be provable. But if it’s not provable, then it’s true because that’s what it says. It says that it is not provable. That’s correct. Again, you can’t prove it. It’s a contradiction. And therefore, it must be true. Gödel showed there’s no way to split up the world into all true and provable things and all false none provable. His statement was true but not provable. There must be some sort of gray area. The Hilbert program is dead. No perfect set of axioms for mathematics exists. Every such system has its flaws.

Stating this Gödel sentence, it hides the real difficulty in Gödel’s work. We can’t give a complete explanation of it. I once took an entire semester course just on this one theorem. But we can give an idea of what the challenges were that Gödel had to overcome and what his ingenious solutions to those challenges were. In doing so, I’m following a really excellent book by Nagel and Newman called Gödel’s Proof. The goal here is to use the axioms of Principia Mathematica to encode the sentence within the language of the axiomatic system itself.

The Gödel sentence, the sentence is not provable, needs to be encoded within the system. There’s two really big hurdles to this. First, encoding. How do you write this sort of idea, these words, when you only have a world with numbers. And the second is self-reference. When we say this in English, wesay this. This sentence is not provable. Somehow we have to find a way to do this in a very technical language.

Let’s look at Gödel numbering first. Gödel used a really ingenious method of encoding mathematical statements as numbers. And in doing so, he needed to use the primes. Remember, one of the methods we used to show that the rationals were countable, back in lecture seven, had to do with the primes and the prime number factorization, which was unique.

Here’s the key idea how he did this. These axioms were written in the language of quantified statements. Here is a version of a quantified statement. It says, roughly, there exists a number which is 1 greater than y. Mathematicians would read this as there exists an x so that x = y + 1.

Logicians might say this means that the number y has a successor, has something that’s one more than it.

Gödel’s idea was to assign a number to each one of these symbols, the backwards e, which we read is there exists, maybe it got the number 4 and x got the number 13. And the left parenthesis was 8. And maybe y got the number 17. We’ll use that again in a minute.

And now we sort of put these all together. To put these numbers together, we use their symbol numbers as exponents on the primes. So if we label the statement, p of y, it now has a single number that encodes it. You take the primes in order and raise them to the power where the powers are the symbol numbers, 2 to the 4th, 3 to the 13th, 5 to the 8th, 7 to the 13th, on and on.

When you encode this entire statement, you get an enormous number which has 20-30 digits. Let’s call it m so that we don’t have to read off these digits. The point is that this process is reversible because of unique prime factorization. If I gave you this monstrous number, in theory you could factor it into its primes. You could reverse the encoding and you could come up with the statement p of y. You could come up with there exists an x so that x = y + 1.

Gödel actually had to take this one step further. If you were given, say, five separate statements, he could encode each one to get five enormous numbers.

And then he used each one of those as an exponent on a prime number. The resulting numbers are unfathomably large.

And one unfathomably large number could encode all five of these statements. Using these, Gödel could now encode the following sentence just as an example. Axioms 2, 4, and 7 prove that there are infinitely many sizes of infinity. In fact, in writing out that sentence he could have written out everything that axioms 2, 4, and 7 said. He could write out all of that and the fact that they prove that there are infinitely many sizes of infinity, that entire idea could now be represented as one single monstrous number, a single number representing an incredibly complicated idea.

With this complicated system, called Gödel numbering, he could now talk about proving statements using numbers. You see, Gödel had found a way to talk about an axiomatic system for numbers from within that system.

He could just encode the statements about that system as numbers and that system by its design talked about numbers. And so now that system would talk about those statements.

Gödel needed one more tool, and this is called substitution, the idea of replacing one symbol with another. We do this sometimes in math classes.

Sometimes in calculus you substitute u for y. We do u substitutions in calculus frequently. When you do substitute u for y, you would replace all the instances of y with u. Gödel’s idea is to replace all the y’s in the statement with something else.

But to do this not to the variables but to the numbers, the Gödel numbers of a statement. You might write this as a substitution of m, 17, and k. And the idea would be to take a statement with Gödel number m and replace all of the 17s with k’s. That is, number 17 represented y. So you would replace all the y’s with whatever k was the number for.

For instance, if you take our statement p of y, which is there exists an x so that x = y + 1. If you were to replace the y’s with x’s, you would take the substitution of m with 17 and 13. You go through m and find all the places 17 is used as an exponent and replace them with 13. 13 is the code for x. Turns out there’s only 1, and so you replace that 1 with a 13. What you get—this is important—what you get is not a statement. What you get is a new number.

It’s the Gödel number of a statement where the y is replaced by x. So it would now be the Gödel number of the statement there exists an x so that x = x + 1.

Now, just to be clear, this statement is false. There is no number which is one more than itself. But that’s what you would get if you do this substitution. So that’s a quick overview of this Gödel numbering scheme, which is fairly complex but really ingenious. So let’s move on to the second big challenge.

Now, the second big challenge was self-reference. You see, in English, we use words like “this” to accomplish self-reference—as in, this sentence is false, or this sentence is not provable. How do you accomplish that sort of self-reference when our language is limited to things like and, or, if, then, there exists for all. That was Gödel’s second big challenge.

In the book Satan, Cantor, and Infinity, Raymond Smullyan gives an excellent nontechnical explanation of the key ideas, and we’re giving a modified version of that here. To understand this explanation, we need to draw a distinction between the use of an expression and the mention of it. Consider the sentence my book contains the phrase “my book” 42 times. In the sentence, the word phrase “my book,” it’s used twice. The first time it is used—and when I say that, I mean the meaning of the words is key—my book contains the phrase. We’re using my book to mean something physical—my book. The second time, the phrase is only mentioned. It uses the phrase “my book” 42 times. When I mention it, the meaning is really unimportant. I’m just putting the words there. You have to match those characters up and see that it occurs in the book 42 times.

We’ve seen before how Cantor used diagonalization to prove that the real numbers weren’t countable and to prove that the power set has a larger cardinality than the original set. We can define a language version of this diagonalization now. If I want to take the diagonalization of a phrase, what I get is the phrase followed by the mention of the phrase. That sounds a little strange, but let’s give you an example. If I take the diagonalization of “I read,” the result is I read “I read.” That is a weird but perfectly good sentence. It’s saying that I read. And what is it that I read? I read the phrase “I read.” You see, the phrase “I read” is both being used first and then being mentioned.

Let’s see if we can use these tools to write the self-referential sentence “Raymond is reading this sentence” without using this linguistic crutch, the word “this,” which makes the self-reference really easy. Now, you might guess that we could do something like this—Raymond is reading “Raymond is reading.” But the sentence, it describes Raymond as reading something which is different from the sentence itself. So that doesn’t work. However, note this sentence, it’s the diagonalization of the phrase “Raymond is reading,” because the sentence is Raymond is reading “Raymond is reading.”

These sentences are going to get long quickly, so let’s introduce some notation to simplify this. Let’s let R be the statement “Raymond is reading,” and let’s let D be the diagonalization of. So sentence 1, Raymond is reading “Raymond is reading,” we can write that as R“R.” And that’s the same thing as DR. It’s the diagonalization of the sentence fragment R. We have one more layer of complexity here. Note that by itself, RD isn’t a sentence. It says “Raymond is reading the diagonalization of,” but it doesn’t complete.

However, RD can be used in a sentence. It can be mentioned. You can’t use it, because it’s not a complete sentence, but you can mention it. The incomplete phrase RD, you’re not using it.

So what is the diagonalization of RD? Well, if we diagonalize RD, we get RD“RD.” Remember, the diagonalization of y would be y“y.” The claim that I’m going to make is that the sentence RD“RD” says “Raymond is reading this sentence” without using the word “this.” Let’s see if we can see why that’s true. You see, RD“RD”—this is a sentence that Raymond is reading something. That’s what it says. Raymond is reading something.

What is he reading? He’s reading the diagonalization of RD. And what is the diagonalization of RD? Well, it’s RD followed by the mention of RD. It’s RD“RD.” That’s the original sentence. In other words, this sentence is saying that Raymond is reading it. It’s reading this sentence. RD“RD” is a very tricky way to encode the idea that’s expressed in English as “Raymond is reading this sentence.” The key here is the idea of D, the diagonalization. That’s what’s producing this strange loop. That’s the self-reference. That’s what’s bending around and giving us this strange loop.

So what did this look like for Gödel? Seem Gödel used his numbering scheme to create self-reference. And here’s what he wanted to write down.

“It is not possible to prove this statement.” The analog of the diagonalization is the substitution function. If we take the substitution of M with 17 and W, that takes the statement was Gödel number M and replaces all the instances of y—remember, y was 17 in our code—with the number W, whatever that represents. The self-reference, it comes when you do something strange like this—the substitution of M, 17, M. You see, this says take the statement with Gödel number M and replace all the instances of Y with M. And there is the real mind bending part, the real brilliant, the strange loop. Now we use the substitution function like this.

Let’s gradually work up to this. So Gödel could now encode something like “prove x, z,” meaning that the statement x proves the statement z. You can prove the statement z using the statements x. And then we could append “there exists” to the front of that and get “there exists x, prove x, z.” There is a set of statements x that proves z. Or we could write its negation by putting a negation in front. There is no proof of z. There does not exist an x that proves x, z.

Finally, instead of just any statement z, we could write something more complicated. “There exists an x. Prove x. And then the substitution of Y, 17, y.” There is no proof of the statement obtained by taking the statement with Gödel number y and replacing all of the variables y with the number y. Note the diagonalization here. We’re using y in two different ways.

And here’s the real self-referential trick. This last statement, it still has an unknown variable. It still has a y in it. But that statement also has a Gödel number. We could use this prime trick and get some number. Let’s say that Gödel number is R. What do we get if we plug in R, the Gödel number for this whole statement, for y? Inside, we would get the substitution of R, 17, and R. So we’re taking a sentence that has a variable y, and that sentence has a Gödel number R, and we’re replacing all the variables y with the number R. What do you get? “There does not exist an x, so that prove x substitution of R, 17, R.”

Now, that seems complicated, and it is. But here’s what I claim—this is it. This is the statement that says “This statement is not provable.” Let’s call this statement G and dig in and see why it is that it works. So I think what’s clear is that G says there does not exist a way to prove some statement. What statement is that? It’s that the substitution of R, 17, and R. What happens when we do that substitution? Well, take the statement with Gödel number R. That’s, “There does not exist an x to prove x substitution of y, 17, y.” Now replace all of the y’s with Rs, and what you get is the statement G. So G says “There is no way to prove the statement G.” It’s brilliant. It’s self-reference without using the word “this.” The statement G, which is deeply encoded with a lot of mathematics, means “This statement is not provable.”

Just to remind ourselves what the big implication of that, it’s this—is the statement provable? No. It states that it isn’t, and therefore, it must not be provable. And it says, I am not provable. And therefore, it must be true. This ingenious method is using the axiomatic system of Russell and Whitehead, which they had carefully constructed to avoid contradictions—they wanted to avoid Russell’s paradox and things like that—and it’s constructed within that system a statement that showed that their axioms couldn’t prove everything that was true.

Now, you might think that you see a way out of this Gödel’s trap. He found a statement that the axioms couldn’t prove. You might think that we just include it as another axiom, and then its proof would be easy. You would just say see that one axiom. This objection should remind you of the common attack on Cantor diagonalization. Remember, we played dodgeball and we found a real number that was not on that list. Could we just add that as the first number on the list? This was back in Lecture 7 on countability. The power of diagonalization, this Cantor argument, was that it covered every possibility. Cantor showed that you put that one on the list, you could just diagonalize the remaining list. He showed that there’s always something that’s not on that list. No one-to-one correspondence can ever be found.

And Gödel’s proof did the same thing for axioms that purported to give a foundation to arithmetic and the idea that they could prove every statement that was true. Gödel showed not only that Russell and Whitehead’s list of axioms was missing something in the sense that there would be some statement that would be true but not provable. He showed that every axiom system would have the same problem. Every system has a Gödel sentence.

You add a new axiom, Gödel’s process would find another unprovable statement which was true.

This task of finding exactly the right axioms, Gödel says it’s a Sisyphean task. It won’t end well. This is an amazing mathematical achievement, and one that really changed the course of the field. You see, things everyone had believed to be possible were suddenly proved to be impossible. Unlike with Cantor’s work on infinity, there was no controversy. People quickly realized the importance and the correctness of Gödel’s work. For mathematicians, the way things seemed to be just all of a sudden changed. What was turned into an allusion. We can create objects like that. You swear you’re seeing a figure one way, and it takes looking at it in exactly the right way to realize it’s an illusion. That takes us today’s Quick Conundrum.

Akiyoshi Kitaoka is a psychology professor in Kyoto, Japan. He’s made these optical illusions that I think are really fresh and interesting. With most optical illusions, I see the trick quickly, but these, I just can’t help seeing the illusion. Here’s one called Bulge. If you know illusions, you can sort of guess what the surprise is. Turns out all of the lines in this picture are vertical or horizontal. The placement of the smaller squares rotate the lines in our mind.

Here’s one that fools me even now. They’re black and white spirals, but you can also see these spirals alternating white and black tiles. But it turns out they’re not spirals at all. They’re just circles. See, Kitaoka has figured out how to do the reverse of what Gödel did. Gödel took a seemingly simple world where things are true or false, provable or not provable, and he showed that it has great complexity. Simplicity was the illusion. Kitaoka, with these really fantastic optical illusions, took what we think are simple things and made them seem complex. Here, the complexity is the illusion now.

Let’s go back to 1928. The young Gödel was at the talk by Hilbert. In that same talk, Hilbert optimistically claimed that others had proved that number theory and analysis were consistent and didn’t contain any contradictions.

Again, within three years, Gödel proved Hilbert to be dead wrong. That was the second incompleteness theorem.

In sort of musical terms, the second theorem represents a coda to his 1931 paper, a mathematical bonus to an already ground breaking opus.

The main theorem was the first incompleteness theorem. Every axiomatic system that contains basic arithmetic must contain a statement that is true but unprovable. So let’s look at what the second incompleteness theorem says. Basically, many things an axiomatic system can prove—again, one that includes basic arithmetic. It can prove that an axiomatic system can’t prove any contradiction? No. It can’t do that. That’s what the second incompleteness theorem says. It cannot prove its own consistency. It actually says something slightly more specific. If a system does include a proof of its own consistency, then the system is, in fact, inconsistent, that it proves both p and not p. And Gödel proves this in yet another incredibly ingenious way.

See, first he proves the following statement within this axiomatic system. We’ll call it statement a. If the system is consistent, than the Gödel sentence is provable. Now, he’s already proven earlier in the paper that the Gödel sentence is not provable. If the system could prove its own consistency, then the statement a, which is an if then statement, would have its hypothesis proven true. And therefore, the conclusion would be proven. But we know the conclusion can’t be proven. The conclusion says that the Gödel statement is provable. Thus, no system can prove its own consistency. If you’re struggling a bit to follow this, you shouldn’t worry.

Gödel’s work is incredibly complicated. It contains many, many layers, even more than I’ve discussed here. What I really hope you get out of this discussion is a few key points. Gödel was using self-reference, which has been a key in so many of the paradoxes we’ve seen, to show us surprising results about axiomatic systems. And in doing so, Gödel opened up new areas of study.

Now that we know something about Kurt Gödel’s work, I want to tell you a story that shed some light onto the kind of intellect that is required to dream up these amazingly complex ideas. It was in 1946. After he had transferred citizenship several times as a youth, Gödel was working in Princeton, and he applied for US citizenship. He was goaded by his friends, including Albert Einstein, because he studied really hard for the citizenship test. They thought he didn’t really need to, and he probably didn’t. Now, before his exam, he confided to a friend that he had found a loophole in the US constitution that would legally transform the government into a dictatorship. His friend said, that will never come up in a citizenship test.

But the day of the test, it was Einstein and a friend who picked up Gödel and drove from Princeton to Trenton. They got to the place, and the examiner recognized Einstein. And so all three of them came in instead of just Gödel.

Now, before the actual exam questions started, the examiner was just making small talk. Mr. Gödel, where are you from? Austria. What kind of government did you have there? Well, it was a republic, but the constitution was such that it changed into a dictatorship. Remember, this is just post World War II. Ah, the examiner said. That’s very bad. That couldn’t happen in this country. And Gödel started to blurt out, yes it could, and I can prove it. Thankfully, the examiner cut him off and moved on. But you can really imagine Einstein getting a good laugh out of this.

This is really illustrative that Gödel had this incredible obsession with systems and rules and how they fit together, their implications. When he was thinking about the constitution, he was probably saying that the hole was something like this—not only can you change the constitution, but you can change the rules for changing the constitution. When it comes to mathematics, his obsession with rules gave us the stunning results that revolutionized this field.