Limits of Logic: The Gödel Legacy

Christer asked me, when he invited me, to speak about Gödel, and I thought that maybe I was going to speak not only about Gödel, but about other things that are unknowable, but then I decided that for my presentation this morning I would talk just about Gödel's incompleteness theorem and try to give an overview of it. I'm not going to try to talk very much about philosophical consequences, we can talk about that in discussion, but just to give an overview of what Gödel did. As Marcus said in his presentation, Gödel was inspired by paradoxical statements like this sentence is false, and he took that kind of structure or construction and imported it into mathematics in a way that nobody could have ever expected. I have broken my lecture up into so-called chapters, I don't know what that means, but it's just for the humor of calling things chapters. Mathematics, about four or five hundred years ago, there were no symbols practically at all. It was all done in sentences. There was not even such a thing as an equation or letters of the alphabet used for variable names or constants. Those things were invented. Descartes, I think it was, invented the idea of using letters of the alphabet to represent numbers. Letters at the beginning of the alphabet to represent things that were constant. Letters toward the end of the alphabet to represent things that were variable. There was a Scottish mathematician whose name I've forgotten. His first name, I think, was Robert, but I don't remember his last name, who invented the equals sign four or five hundred years ago. It's kind of hard to imagine mathematics without any symbols at all, but that tells us that we've come a long way. In the 17th, 18th, 19th centuries, mathematics became extremely formal, but a lot of it was done in language, as it is today, but they didn't know exactly what was rigorous and what wasn't. Lots of things that seemed paradoxical were discovered by people like Euler and many other people. These paradoxes gave rise to a lot of concern about the reliability of mathematical reasoning. Even though it was felt very rigorous and very precise, the idea was they wanted to try to pin it down in sort of a formal way so that for once and for all they would know what was mathematical truth. Now, since this is a short lecture, I'm not going to try to summarize any of that. There were lots of people who contributed. I could name people like Buhl, George Buhl, Augustus de Morgan, Gottlob Frege, and David Hilbert, and many, many others, Giuseppe Peano. There were many people, but the people that I want to talk about in particular, this is Alfred North Whitehead, and this is Bertrand Russell, a rather humorous photograph of Bertrand Russell. Their great opus, Principia Mathematica, which came out in three volumes in the years 1910 to 1913, was an attempt to formalize all of what mathematics was and to unite it with logic and to ground mathematical reasoning in logic and the theory of sets. This was a noble attempt, and one of the things that lay at the core of their work was the idea of trying to get rid of paradoxes. As I mentioned earlier, that was troubling to many people. To Russell, it felt as if the root of all paradoxes was self-reference or sentences that could talk about themselves, like this sentence is false, or sets that could contain themselves. He developed what he called the theory of types, which was, I'm not going to go into it, but it was a way of trying to eliminate self-reference from coming into a system. It was a very elaborate and careful bastion created to prevent self-reference from ever coming up, from ever arising in such a system. That was something that was very important, and for many years, this is just a page that I took out of it to show the, I don't know what you would call it, the prickliness of their notation. But for many years, their work was taken as being the realization of this dream, of grounding all of mathematics in logic, and of formalizing it, and of having it be a precise system for once and for all. All mathematics was going to come out of this work, Principia Mathematica. But in Vienna, Kurt Gödel was, in some sense, dubious of this goal, and he felt that there was something wrong about this attempt. I'm going to talk about what he did, but I have to first talk a little bit about the nature of mathematical reasoning and how it worked in not only Principia Mathematica, but in any formal system. The idea of a formal system is that one has a set of axioms, which are written down in a formal notation, which are then manipulated in certain formal ways by things called rules of inference. I'm certainly not going to detail any of that. Here are some axioms that can be taken for number theory, and they're not all of the axioms of number theory, but they illustrate things, and I'll try to decode this notation for you. It really doesn't matter very much, but the upside down capital A means for all, and so this says for all A, this twiddle means not, it's a negation. The capital S means successor of, so this says for all A, it is not the case that the successor of A equals zero. What this effectively says is, I can translate that, I can say there is no number whose successor is zero, successor being the thing you do when you add one every time. So basically this is saying there is no such thing as negative one, there is no negative numbers. This one is sort of defining the property of the number zero. It says for all A, the sum of A and zero is A. Zero is an additive identity. This one says something about the nature of addition. It says for all A and B, if you add A and the successor of B, it's the same thing as taking the successor of the sum of A and B. And that's a rather trivial statement, it would seem, but it's enough to allow addition to get off the ground. Then this is the statement that multiplying by zero, of course, gives you zero, and this is a statement that defines the essence of multiplication. That is, if you multiply A times the successor of B, it's the same thing as taking A times B and then adding A on. And those statements allow you to do a lot. I mean, other axioms are needed, but I don't want to try to go into it in any detail. What I want to stress, though, is that when I say formal, what I mean is, I mean, today in the era of computers, people are familiar with the idea that symbols can be manipulated by machines. Back in 1910, 1913, in the years when Principia Mathematica came out, and in the preceding decades, and in the following decades, there weren't any computers around, even though, what's his name? Why am I blocking on names these days? Lady Lovelace's Babbage, Charles Babbage, yeah. Babbage had invented the concept of computers, and it sort of developed them in a theoretical way, in a marvelous way. So the concept of computers was sort of around, not electronic, of course, mechanical, but still. But back then, the idea of symbols being manipulated formally was new and different. And so it's very important to realize that the idea of these systems was that you didn't pay any attention to the meaning of the symbols. I said that this upside-down A means for all, and that this means not. But in a certain sense, you're not supposed to know the meanings of these symbols. When you perform the operations that I said rules of inference allow you to deduce theorems from axioms, those operations are not supposed to take into account any meaning. They're supposed to ignore the meanings of the symbols. You look only at the symbols themselves, and you say, okay, this sequence of symbols has a certain form that allows me to proceed from it to another sequence of symbols. I don't know what they mean. Okay, so that's the idea of formal systems. And that was the notion that was being pushed in Principia Mathematica. So I'm going to show two proofs. I'm not going to explain the rules of inference being used, but I just want to show you what a proof looks like. This is a very short proof. This is a proof of the statement that says 1 plus 1 equals 2. That is, the successor of 0 added to the successor of 0 equals the successor of the successor of 0. And so here is the proof. It begins with, it makes use of two axioms, and then it uses some rules of inference, which I'm not going to describe. But formal processes allow me to pass from this axiom to this specification of it, to this, to this, to this, to this. The only thing that I want you to notice, I put a red line on the right margin, and I want you to notice that the line sort of goes back and forth. This is a long, a couple of long things, then they get very short, and then it gets a little bit longer toward the end. And that's only a hint of things to come. I just want you to notice that. Now the other proof that I'm going to exhibit is that 1 times 1 equals 1. It's a longer proof, it's more complex, but this is about as short as it could get from the set of axioms that I just showed you and the rules of inference that I was allowing in this system. And I'm not going to go through it at all. It's not important for this purpose. I just, again, want you to look at that, at this wavy shape, and to see that in order to prove a string, this is a string of symbols, that's very short, I had to go through a pathway that involved some pretty long strings. What's the longest one? It's that one there. A lot longer than the result that I was expecting. And that's a very crucial fact in thinking about the nature of proofs. That is, that in some sense, we don't know how long the strings are going to be that we're going to have to manipulate in order to get, in the end, a very short string as our result. Nor do we know how many steps we're going to have to use. We can't predict that in advance. So, Bertrand Russell, of course, was very happy when he was devising, he and his colleague, Alfred North Whitehead, were creating this theory because it was clear that when you wrote down statements about integers, I mean even complicated statements, like a statement that might express Fermat's last theorem that a to the n plus b to the n can never equal c to the n, with a, b, and c being positive integers and n being greater than 2, that kind of a statement can be written down in this kind of a notation, and it clearly doesn't have anything to do with the idea of paradoxical statements like saying this statement is false. That is as far as you can possibly get from such a thing. It's talking about integers, and that's all it's talking about. Or a statement of the Goldbach conjecture, which says any even number greater than 4, is the sum, e greater than or equal to 4, is the sum of two prime numbers, which is still unproven, but everybody believes it to be true. Such a statement, again, has only to do with prime numbers and sums and such things, and how could self-referential statements possibly come up in a system that is only talking about integers and their properties? So that was a very, something that I'm sure made Bertrand Russell very happy that his system was clearly unable to have self-referential statements. Now, I want to distinguish, I've already talked a little bit about theorems, I want to talk about something called well-formed formulas, because they form a contrast to theorems. A well-formed formula is really just, you could say, a grammatical sentence, something that expresses a statement. It could be a true statement or it could be a false statement, but it's just a statement. So let's take a look at them. Here's one that says 1 plus 1 equals 2. That one happens to be true. Here is one that says 0 equals 1. That happens to be false. But they're both equally good well-formed formulas. They express thoughts that are either true or false, and that's all we need to think about. Here's one that expresses the commutativity of addition. And this one says there is no number A whose square is 2, and so forth. If I took away the tilde at the beginning, it would say there is a number A whose square is 2. They're both equally good well-formed formulas. Now, what I wanted to tell you about well-formed formulas is that it's very easy to tell if a formula is a formula meaning a string of symbols. It's very easy to tell if a formula is well-formed or not. I mean, for example, there are some rules. Basically, you just look at its parts and break it up into smaller parts. I mean, for example, here I look at this and I see it begins with a right parenthesis. Well, that tells me I better have a balancing left... Sorry, it begins with a left parenthesis. I better have a balancing right parenthesis. And it doesn't have to be at the end, but it has to be somewhere. There has to be a balance of parentheses. And indeed, that balances, this balances. That doesn't guarantee yet that it's well-formed, but it certainly is part of the test as to whether it's well-formed. Here is... This thing here stands for if-then or implies. And if I read this out loud, it would say if 0 equals 1, then 2 plus 2 equals 4. It's not a very interesting statement, kind of a silly-sounding statement. That's not the point. But we can read it and make sense of it. And this is well-formed in itself. 0 equals 1 is well-formed. And this is well-formed. This is 2 plus 2 equals 4. And then I've combined one statement and another statement with an if-then. And that is also an operation that creates, that takes two well-formed formulas and makes another well-formed formula from them. And when I build up formulas into well-formed formulas, all I do is I take smaller chunks and I build them into larger ones. That's all I do. And so if I want to know if a string of symbols is a well-formed formula, all I need to do is look at its parts. I break it down into smaller parts and I break them down into smaller parts and I keep on going. And it's a very predictable test of well-formedness. I'm contrasting that with theorems. It's not so easy to know if something is a theorem. And that's what that red line on the right margin was trying to tell you, that the definition of theorem is something that has a demonstration, something that has a proof. And in order to know that, you have to make a search among possible proofs. But you don't know how long that search is going to take and you don't know how long the formulas are that are going to be involved in that search. So there's a kind of a degree of unpredictability to it. Whereas, again, the contrast that I'm drawing is there's no unpredictability to the question of how long is it going to take me to figure out whether this formula is well-formed. That's a really trivial question. That contrast is very, very crucial. I guess I've already said this, so I don't need to go through it. It just says test for well-formedness by a recursive breakdown into simpler parts. You break a formula, a possibly well-formed, possibly not well-formed string down into parts and you keep on breaking them into their parts until you finally either arrive at that it is well-formed or that it isn't. That's a very straightforward thing. So here's a string. This actually is an expression of the Goldbach conjecture. In these formal notation, I can sort of tell you what it says here. It says, for all A, there exists a B and a C with the following properties. Basically, it's saying, this here is multiplying 2 times A plus 2, and A can be as low as 0. So A plus 2 is 2, 3, 4, 5, 6, and so forth. So this is any even number from 4 onwards, and it's saying for any A, this is basically an arbitrary even number, and it's saying there exists a B and a C such that A is the sum of these two things, and then over here, it's saying that B and C are prime numbers. I'm not going to decode it for you, but basically this is an expression of the Goldbach conjecture. As I said, still today, not known whether it is true or false, although everyone believes it's true. So is it a well-formed formula? Just look at it and you'll know. It'll take you a few seconds to realize that this is a well-formed formula. There's nothing hard about it. Is it a theorem? Well, try to prove it, and hundreds of years of mathematicians working on it have not yielded that. Okay, so you can see that although both properties, being well-formed and being a theorem, are formal properties that involve the properties of symbols, one property is a very simple property that can be detected in a predictable amount of time. The other property is one that is much subtler and more elusive. So to sum it up here, on the left side, it says well-formed formulas are built up recursively by putting smaller pieces together. This idea of this picture is that you take small things and you put them together and you get a big thing. The build-up grows. You can reverse it trivially, breaking well-formed formulas into parts. Whereas for theorems, they are arrived at by you only know something is a theorem if there exists a proof, a demonstration of it, that is, starting with the axioms and following the rules of inference, combining axioms, and combining previously proven theorems into new theorems. And that can be a process that involves getting longer and longer strings, shorter strings, longer, shorter, you never quite know where you're going, and it can take any amount of time and you're not sure. So that's a very big contrast between two kinds of structures. Okay, now we come to two types of numbers. And this is an analogy that I'm going to use to try to get you to understand, I mean, many of you already do, but those of you who aren't familiar with Gödel's work, to understand the idea behind his construction. Fibonacci numbers, well, you know what they are, but I'll just mention them. The Fibonacci numbers are the numbers that you get when you take sums of the previous two numbers. 1 plus 2 is 3, 2 plus 3 is 5, etc. 13 plus 21 is 34. Everybody these days is pretty familiar with the Fibonacci numbers. Now, if I were to ask you about, if I were to give you a number and say 672, is that a Fibonacci number or not? You wouldn't say, oh my God, I have no idea how to figure that out. What you would do is you would generate the Fibonacci numbers up to that size. What did I say, 672? Up to that size or close to it. And you would say, well, it looks like it's not because the next one is going to be above, it's going to be about 900 and something, 987. And that's all, I've already gone and I'm never going to get smaller. The Fibonacci numbers always get bigger. And if I've passed 692, well, or 672, whatever it was that I said, then I guess it's not. But if I had said instead 377 and you hit it, you'd say, yes it is. So it's very easy to know if a number is or is not a Fibonacci number. It's a very simple test. Similarly, you could say that for primes. Do I, you know, is 691 prime or not? You divide it by a series of numbers and eventually when you hit the square root of 691 and you haven't found a divisor, you know you're done and you know it's a prime. Or if you found a divisor in that period, then it's not a prime. And so there are lots of properties of numbers that can be tested very quickly and very predictably. In contrast, I'm going to talk about, I'm not even going to show this, you get the idea. I'm going to talk about a famous conjecture made by Collatz, Lothar Collatz, in the 1930s. He was a mathematician whose specialty was differential equations, but he probably is going to be known more for his conjecture than for anything else that he did, although he was a good mathematician. So I'm going to phrase it in a way that is a little bit different from the way he phrased it, but it's equivalent. It's the same thing. It's just sort of looking at it from the backwards perspective. Start with n equals 1. We always start with 1. And then we have two things we can do. We can always jump from n to 2n. We can always double. Anything we have, we can double. And if the number has the form 3k plus 1, such as, for example, 7, or 22, then we are allowed to jump from this big number, let's say 22, down to 7, because 22 is of the form 3k plus 1. It's 3 times 7 plus 1, so I can jump from 22 downwards because it's of the form 3k plus 1. I can't do that with 23 because it's not of that form. I can't do it with 24 because it's not of that form. But with 25, I can do it. I can jump from 25 down to 8 because it's of that form. All right, now, so I have these two rules that allow me to do things to numbers that I have. I can go 1, double it, get 2, double it, get 4, double it, get 8, double it, get 16. Now, 16 is of the form 3k plus 1, so I can go down now. I can go down to 5. If I wish to, I could also just double it. But I decided that I would use the other rule, and I would go down to 5. Then I can go to 10. Then I can go to 20. Then I can go to 40. Oh, look, 40 is of the form 3n plus 1, 3k plus 1, so I can go down now. I can go down to 13, and I can go up to 26, and so forth. I can take pathways in the set of numbers. What destinations can I reach? Here is actually the shortest pathway to 7. It's a very kind of funny pathway. I get bigger. Then I get smaller. Then I get bigger. Then I get smaller. Then I get bigger. Then I get smaller. Then I get bigger. Then I get smaller. Then I get bigger. Then finally I wind up at 7. It's kind of a chaotic pathway, and it's the shortest pathway to reach 7. Now, you can see that if I say, is a given number, I'll call these call-outs numbers, is a given number a call-out number is not so trivial as determining whether it's a Fibonacci number because I don't know how long the pathway is going to be to get there. Can you get to 3? Here is checking it out, and in fact I can get to 3, but I have to, you know, if I take all the possible routes starting with 1, and I start going all sorts of different ways, it turns out this is the promising route, but we didn't know in advance that this was the route to take. What about 27? This is a famous case. That is the shortest route to get to 27, and it goes all the way up. I put this number in green and made it larger. It goes all the way up to 9,232. You can only go, that's the shortest route to get to 27. You have to go all the way up to 9,000 in order to come back down to get to 27. That is really quite astonishing. So here's a sort of a picture of it. I don't know why it's not, it's cut off a little bit at the bottom, but I guess that's okay. Can you see the graph? That idea is that it goes kind of chaotic, jumps, then it goes way up to that, then it comes down, then it goes way up, then it comes down, and it jumps, and finally we get to 27. That's an interesting picture. And so I've already said all of this. It's not a test by recursive breakdown of the simpler, smaller cases, and it's not guaranteed to succeed. We don't know. If I say, what about getting to 542 using this rule? Well, we don't know how long it's going to take, or even if we can get there in advance. So, now Gödel, although he wasn't familiar with Collat's numbers, because they were only invented after his work was done, but he understood, yeah, yeah. Oh, the conjecture states that every possible positive integer can be reached in this fashion. Every positive integer can be reached by following this process. And it's been tested all the way out to many billions, and it's always been found, but every number works, but it's never been proven. So, I want to come back to Gödel now. Gödel had a deep insight. I mean, in the preceding centuries, people used numbers to stand for all sorts of things. And, I mean, everybody knew, for example, that you could model the physical world. I don't mean everybody, but people in science knew that you could model the physical world by using equations that the coordinates of, say, the center of gravity of planets could be thought of as numbers, and that there were equations that governed their evolution in time. And so it was understood that numbers could simulate the world. But what Gödel saw was that numbers could also, integers, in fact, not real numbers, could very easily simulate some things that people had never thought of as being mathematical objects. It seemed maybe clear after Kepler and Newton that planets moving in orbits were sort of mathematical objects, and that they could be simulated by real numbers following differential equations. But the idea that formal systems of the sort that Russell and Whitehead had invented was itself a mathematical system was not something that anybody had thought about. They didn't think of the process of creating a proof as being a mathematical process. It was somehow not thought of in terms of numbers. What Gödel realized was that essentially the manipulation of symbols was a mathematical operation and therefore could be modeled using integers. So, well, here is a picture of a piece of music, a piece by Bach, and you can imagine encoding this piece into one very large integer. The method by which you encode it into a very large integer is not relevant to this discussion. But you can imagine that you could encode this in a very large integer and then you could ask questions about that integer which would amount to asking questions about the piece of music. Even though it seemed to be asking questions about the integer, it would be asking questions about the piece of music also at the same time. So, for example, the question is how many notes are in the piece? That's a mathematical question which you could answer by looking at this big integer that stood for it. What is the key signature of the piece? Is it by Bach or not? That's a little bit harder to imagine a mathematical operation that will take a big integer and tell you whether or not the piece that it stands for was written by Bach. But you could imagine, maybe, maybe it's a mathematical question, what nationality was the composer? That gets a little bit tricky. So, I just wanted to raise some of the kinds of issues that you could imagine asking such questions. Some of them seem trivial, how many notes are in the piece and some of them seem a little bit harder. So, if you did the same thing to strings of cymbals, like the Goldbach conjecture is a string of cymbals. I don't know how many it contained. The way I wrote it out, I guess it probably contained about 30 cymbals. And you could imagine now that you could encode it in some fashion as a large integer. And I'll explain how Gödel did that, how he encoded them as integers. But imagine that you have a big integer that in some sense stands for this string. Then you could ask how many cymbals are in the string? And that should be something you could be able to figure out. Is this a fact from the times table? That is, is it a mere multiplication like 2 times 2 equals 4 or 9 times 8 equals 72? Is that what this string is expressing or is it expressing something else? How about whether it's true or false? Is this a true statement or a false statement? Can you apply a mathematical operation to the large integer and know whether it's a true or false statement? Does it follow directly from another statement? Is it a theorem of Principia Mathematica or not? And so forth and so forth and so on. Alright, so let's see how did he do it. Oh, I have a picture of Gödel with an unidentified peasant. So Gödel mapped strings into large integers by taking advantage of the fact that any integer can be factored in a unique way. So here, 6 is 2 to the 1 times 3 to the 1. 25 is 5 squared. 37 is a prime, so it's already factored into its own thing. Now, here is a large integer, fairly large, 1700. We factor it into 2 squared times 5 squared times 17. That is its prime factorization. And the exponents here of the primes that are involved, well, up to the biggest prime. The biggest prime involved is 17. The intermediate primes are 2, 3, 5, 7, 11, 13, and 17. Those are all the primes up to 17. Each of them in this factorization has an exponent. Most of them here are zeros, but 2 squared, 3 to 0, 5 squared, 7 to 0, etc. And so I have a sequence of integers being coded by this large integer. A sequence of small integers being coded by this large integer. This is what Gödel saw. He said a large integer can stand for a sequence of small integers. An arbitrarily long sequence of small integers. And so he then recast all of what was being done by Whitehead and Russell in Principia Mathematica as a sequence of operations on large integers. Instead of seeing it as operations on strings, it was operations on large integers. So let's take an example. Let's look at just one string so that we see how Gödel could encode it as a large integer. The string I've taken is that axiom that was the first axiom. For all a, it is not the case that the successor of a equals 0, which basically is saying there are no negative numbers. Okay, that's a sequence of how many symbols? 1, 2, 3, 4, 5, 6, 7, 8 symbols. So we'll take the first eight prime numbers and we'll put them to various powers. What I have written here is I've actually put 2 to the upside-down capital A, but that may not look like it's an integer. But if you think of upside-down capital A as being a digit in Martian, this is just Martian notation. And upside-down capital A might be 7 in Martian notation. And lowercase a might be 9. And each of these symbols is really just an integer in Martian notation. So when I do this, I'm just creating a large integer. That's all I'm doing. And if I want to know what formula I was doing it for, all I need to do is take that large integer, factor it, and then look at the sequence of exponents. And I can spell out the exact string that I was encoding in the large integer. So Godel had this way of encoding strings into large integers. Now, it thus creates a kind of an ambiguity. Is this large integer, is it a number? Well, yes. Is it a formula? Well, in a sense, yes, it's a formula. That is a formula of Principia Mathematica. Yes, it is. It's a formula in the sense that it stands for this formula. And if we are dealing with it in the context of these formal operations that allow us to pass from one string to another or from one number to another, according to certain rules, then it can be thought of as a formula. It's just a formula written in a funny notation. This actually is the integer that stands for one of the axioms in Principia Mathematica. It's a big integer because the axiom is a complicated statement and it requires a lot of symbols. There are many ways of doing what is called Gödel numbering. This is using Gödel's actual system. I mean, there are many other ways of doing it which would make it simpler. But I just thought it's amusing to see that this one large integer is standing for one of the axioms of Principia Mathematica. And you could figure out that it was by just factoring it. It might take you a while to factor it, but once you factored it, you could exactly map out symbol by symbol exactly what this axiom says. However, it's another thing to figure out if it's a theorem. Well, if you recognize that it's an axiom, you're done. But anyway. Does a given integer, not that one in particular, but just a given integer, stand for a well-formed formula? That's easy question. Very easy question because you just, you know, you can just look at the exponents and then you look at that formula and you know how to break it down. You can do this with, you can bypass the translation into the notational system of Principia Mathematica. You can just operate on the integer itself. You can have rules that will tell you how to break that integer down into smaller pieces and into yet smaller pieces and they will tell you whether that integer stands for a well-formed formula or not. It's just as mechanical and isomorphic to the process of breaking down a string and asking whether it is a well-formed string. So it's the same question just asked in a different notation. Does an integer stand, a given integer stand for a theorem? Well, there's no obvious way to know that because proofs are like zig-zagging Collatz pathways. And this is sort of one of the crucial slides of this lecture. All I did was I took the proof that, this is a proof of, beginning with the axioms, let's see, this is a proof of the commutativity of addition. It says at the end for all D and C, C plus D equals D plus C. So that's the commutativity of addition and it begins with axioms and uses rules of inference. It's a fairly long proof. I mean, it's actually very short, but for our purposes it seems fairly long. And it requires getting some fairly long statements there as well. And it's a bumpy route in order to derive the commutativity of addition. But in the end we do derive it. But notice that we don't know how long this proof is going to be in advance, and we don't know how long those strings involved in the intermediate stages are going to be. There are two completely unknown things. And notice how similar this feels to the Collatz numbers. And if we think of these things not as strings now, but as integers, because remember we can encode strings as integers, we're basically doing the very same thing. We're taking some smallish integers, mathematically manipulating them in various ways, getting some very big integers, the analog of 9232. Then we do some more manipulations, we get some other big integers, and finally at the end we wind up with the thing that we were hoping for. So this is what Godel saw, that the question about whether something is a theorem is potentially a very complex question, unlike whether it's a well-formed formula, which is not a very complex question. Okay. So well-formed formula numbers, the numbers that stand through Godel numbering for well-formed formulas, they're like Fibonacci numbers. You can test very easily. Theorem numbers, numbers that stand for theorems in the Principia Mathematica are not so simple. They're more like Collatz numbers. So a way of putting it is well-formed formulas, they're the numbers that correspond to them. To make such numbers, you just increase the pathway, it goes from smaller integers to larger ones, and that's all there is. It's just a monotonically increasing pathway. This kind of thing, theorem numbers, is not a monotonically increasing pathway. It jumps back and forth in chaotic ways. All right. Well-formed formula numbers are isomorphic to well-formed formulas through Godel's mapping. And the pathways that get you to well-formed formula numbers are monotonic and thus monotonous. Nothing very interesting. Theorem numbers are isomorphic to theorems, but again, since theorems, the pathways that get you to theorems are not predictable, the same holds for theorem numbers. So that's just reiterating what I told you earlier. Theorem number pathways follow unpredictable zigzags. Okay. So Godel was able to show that the notion of a theorem number was as mathematically precise as the notion of, let's say, prime number. In other words, a prime number is clearly a mathematical notion. Right? It just involves asking, you know, when I factor this number, do I get anything in between one and itself as a factor? And that's a very mathematical notion. What Godel showed was that being a theorem number is also a perfectly mathematical notion. That is, you begin with, you begin with, by stating that a certain set of numbers are theorem numbers. Which ones are those? The ones that stand for the axioms. The axioms are all, by definition, theorem numbers. The axiom numbers are all theorem numbers. And so you're just given those outright. You're told these five or these ten, whatever, however many axioms there are, these numbers are all theorem numbers. And then you're given some formal rules that allow you to manipulate these numbers. And from those numbers you can create new numbers that are big, sometimes bigger and sometimes smaller, but you will get new numbers. Those are called the theorem numbers. And those numbers are just as mathematical as the Collatz numbers, just as mathematical as the prime numbers, just as mathematical as the Fibonacci numbers. So what Godel was doing was bringing a discussion of provability into the domain of discourse that Principia Mathematica dealt with. What is Principia Mathematica dealing with? It's dealing with statements about integers. Is this integer prime or not? Is this integer a Collatz number or not? Is this integer a Fibonacci number? Is this integer a well-formed formula number? All of these are mathematical questions. Is this integer a theorem number? Another mathematical question. And yet, in code, it is saying, is this particular theorem, is this particular string, a theorem or not? If you ask, is this a theorem number, you're saying, effectively, is this string a theorem of Principia Mathematica or not? And so, despite the fact that Russell and Whitehead were under the illusion that self-reference was not possible in their system, Godel had snuck it in by the Trojan horse of Godel numbering. Because once you have numbers that are acting isomorphically to the structures in Principia Mathematica, then you're able to talk about all the structures of Principia Mathematica numerically. And so, he was, I'm not going to explain how he did this exactly, but he was not only able to import the notion of theorem number into Principia Mathematica, into the system itself, but also he was able to write down a very special string that expressed this following statement. It was a particular integer, g. It said the integer g is not the number of a theorem, is not a theorem number, where a theorem number is just a mathematical notion. You like saying the integer 641 is not prime, which incidentally is false. It is prime, but that's not relevant. It's just a mathematical statement. The integer g is not the number of a theorem, is not a theorem number. However, it turned out that the integer g was actually the exact number that corresponded to the string that expressed this statement. So, the g, this is Godel's formula, says this thing in the notation of Principia Mathematica. It says g, this lowercase number, this lowercase letter g, is not a theorem number. So it says this number has a certain number theoretical property, and it also says that by doing that it says that the formula that it stands for is not a theorem. But it happens that this formula is actually that exact statement. So he actually created a statement that said about itself that it was not a theorem. And that's what Marcus put up. He said this statement is not provable. So, I guess I just added this little thing. These are the same assertion just understood in two different ways. A certain number has a certain number theoretical property, or a certain formula is not a theorem of Principia Mathematica. Identical statements. I guess, oh, I see I've already done in effect. Well, I didn't really, because this is my last slide. Well, let me just conclude then by mentioning the consequences, not the, but some of the consequences of this construction. Because the construction creates a statement that speaks of itself, which is the thing that inspired such terror in Bertrand Russell's mind. Self-reference to his mind was the source of all paradox. And he had striven so hard to make sure that it was not part of Principia Mathematica. And Gödel had actually brought it inside Principia Mathematica by this Trojan horse of Gödel numbering. Now, the statement that Gödel created said of itself that it was not provable. Well, if it was, let's think about that. Supposing that it was provable, then it would be a false statement because it states that it is not provable. But if it were provable, then a false statement would be provable. Oh, that seems horrible. We don't want there to be any false statements provable. That would be the destruction of Principia Mathematica. Nobody believed that there were any false statements would be provable. So, we have to go back and reject our assumption, which was that it was provable. So, it's not a provable thing. But that's what it says. That's exactly what it says. It says that it's not provable. So, it turns out that what it says is true and precisely for that reason it is not provable. It's like, here's the real paradox. It's the exact reason that it is not provable is that it is true. That's the exact opposite of what mathematicians like they think that they want provability and truth to be synonymous. The exact reason that this string is not provable is that it is true. Very, very strange. And this construction that showed that there was a statement that was true but not provable in Principia Mathematica didn't apply only to Principia Mathematica. It applied to any system of this structure. It didn't depend on any of the details of Principia Mathematica's way of the particular axioms that it used or the particular rules of inference that it used. All it depended on was the idea that there was some axioms and some rules of inference. And it showed that in any system that was rich enough to get the truths of number theory in it, there were statements that were true and not provable. And this would, you could then throw this in as a new axiom but that wouldn't help anything because that's a new system that has a new set of axioms and you just apply the good old procedure to that system which is a little larger and you get another string which is not provable but true. And you can keep on going forever. And so there are an infinite number of holes and they can't be systematically all filled. I guess the last thing I want to say is that it has been shown in the last few decades that although these number theoretical statements, I mean Gödel's statement says certain number has certain kind of property but it seems like a very artificial kind of a property. That is it's constructed using this mapping that Gödel created and so forth. And it might seem like it's such a very, very esoteric kind of formula that even though such things exist that they are very remote from anything a mathematician would ever actually talk about. But it's been shown that that's not the case at all. And in fact, John Conway and colleagues were able to show that if you consider the Collatz problem as one of a family of problems that are all of that sort that basically involve multiplying or dividing integers and just going up and down in that way. I'm not going to try to define the exact family but you can imagine it. I mean the Collatz problem is often called the 3n plus 1 problem and you can imagine a 5n plus 1 problem or a 5n plus 2 problem or something like that. If you just consider all of those problems together it's been shown that there are problems of that sort that are undecidable for Gödelian reasons. That is, that the Gödel construction includes, you can prove that the Gödel construction is equivalent to a Collatz problem of some sort. And so in fact that's a very, very normal number theoretical kind of question. It's not something that seems obscure or strange or non-mathematical or artificial. It's a very natural mathematical kind of question. It's also been shown that the Diophantine equations are, there exist unsolvable, undecidable Diophantine equations and those are equations of the, basically the form some integers to some powers equal a set of, sum of integers to powers equals another set of integers to, sum of integers to powers. It's a very, very simple basic algebraic kind of equation and those too, there exist ones that are undecidable. So it turns out that as a result of, as a consequence of Gödel's work that there are questions of very standard mathematical form that have been shown to be undecidable and so the undecidability doesn't just apply to very, very weird remote regions but to very standard kinds of constructions and that's really an astounding, somewhat scary thought and with that I think I'll conclude.