Gödel's Incompleteness Theorem - Numberphile

I've been quite obsessed with Gödel's incompleteness theorem for many years because it kind of places this extraordinary limitation on what we might be able to know in mathematics. In fact it's quite an unnerving theorem because at its heart it says there might be conjectures out there about numbers, for example something like Goldbach's conjecture, which might actually be true, so it might be true that every even number is the sum of two primes, but maybe within the axiomatic system we have for mathematics there isn't a proof of that. The real worry is what if there's a true statement that I'm working away on which actually doesn't have a proof. Now this was a big kind of revelation for mathematics because I think ever since the ancient Greeks we believed that any true statement about mathematics will have a proof. We might be quite difficult to find, like Fermat's last theorem took 350 years to perform. Or my colleague in Oxford, Andrew Wiles, found the proof. But I think we all have this kind of feeling like well surely every true statement has a proof. But Gödel showed that actually there's a gap between truth and proof. I wrote it down here because it's quite cute. So it's one of these cards. The statement on the other side of this card is false. So let's suppose that's true, so it means that the statement on the other side of the card is false. So we turn it over and then it says the statement on the other side of this card is true. Well that's meant to be false, so it means the one on the other side is also false. Oh but we suppose that that was true, so that's false so the other side is true, and you get into this kind of infinite loop. Verbal paradoxes are fine because you don't expect every verbal sentence to have a truth value to it. But then when I went up to university I realised that mathematics, you can't have those. Yet when I took this course on mathematical logic and we learnt about Gödel's incompleteness theorem, he'd use this kind of self-referential statement to really undermine our belief that all true statements could be proved. There was a feeling like we should be able to prove that mathematics is something called consistent, that mathematics won't give rise to contradictions. This had been inspired by certain little paradoxes that people like Bertrand Russell had come up with. People might have come across this idea of the set of all sets that don't contain themselves as members, and then the challenge is, well is that set in this set or not? Actually a really nice version of this is another sort of mathematical verbal paradox is all those numbers that can be defined in less than 20 words. So for example, 1729, which is the taxi cab number that Ramanujan and Hardy talked about, you can define that in less than 20 words, it's the smallest number which is the sum of two cubes in two different ways. So that's less than 20 words. So then you define the following number, the smallest number which cannot be defined in less than 20 words. Now I think if you count that up, I've just defined that number in less than 20 words, and you go, well that's a bit worrying because surely that is a sort of kind of number we might define, the smallest number which has a certain property. So there was a real feeling that these paradoxes, these set theoretic paradoxes, were beginning to be a real challenge to mathematics at the turn of the 20th century. And David Hilbert, one of his big problems that he challenged mathematics with in the 20th century, his 23 big unsolved problems. The second one was to prove that mathematics was in fact consistent. And included in that was that every true statement should be provable. But what a shock he got actually, 30 years later, along comes this Austrian logician Kurt Gödel, who blows this idea that we can prove maths is consistent out of the water and shows there are true statements which can't be proved within any mathematical system. How does mathematics work? We set down things we call axioms, which are the kind of things we believe are the way numbers, geometry work. So for example, if I take 6 and I add 7 to that, I don't think it's going to be different from taking 7 and adding 6 to that. That seems so blindingly obvious and that's one of the axioms of the way numbers work. You know, maybe somewhere out there that goes wrong, but I don't really care. I'm interested in a mathematics where that is true of all numbers and I have rules which allow me to make deductions from those axioms and that's how mathematics works. Each time we make these logical deductions, we expand the conclusions from these axioms. We can add new axioms if we feel like, you know, we haven't actually captured the whole of mathematics. And that was somehow, the mission was, we want to have a set of axioms which are strong enough and that we believe are basic about numbers from which we can deduce all true statements that we will have a proof. And so there was a feeling like, well, yeah, well maybe we haven't got all of the axioms and if we've got a true statement which can't be proved, we could add that as a new axiom and it will expand what we can prove within mathematics. So this is very important for Gödel because we are trying to prove that there will be a set of axioms from which we can deduce all truths of mathematics. Gödel did something very clever because he cooked up a way of allowing mathematics to talk about itself. So what he produced was this thing we now call the Gödel coding. So he showed that any statement about numbers has its own particular code number. He in fact used prime numbers in order to make this coding. So every statement about mathematics could be turned into a number. So for example, the axioms of mathematics from which we are trying to make all of our deductions, they would have code numbers. True statements about mathematics, so for example Fermat's Last Theorem, for example, will have a code number. Also, false statements like 17 is an even number will have a code number. So what do these code numbers look like? They're obviously whoppers. Yeah, they're absolutely huge but it's a unique coding. So every code number can be worked backwards into a statement. Not every number will have a meaningful mathematical statement but it's more interesting the other way. Every mathematical statement will have a unique number associated with it. A bit like how most things in our computer have zeros and ones in them. Very good. So if I'm typing away and I write the name Gödel, that would be changed into ASCII code. It will have a number associated with it. So Gödel cooked this up but why is that useful? Because you can now actually talk about proof in mathematics using these numbers. So you can start to talk about mathematics using mathematics. So for example, you might want to know, well, is this particular statement provable from the axioms? That, I'm going to completely simplify this but it'll give you a feel for it. Essentially, it's a bit like saying any statement whose code number is divisible by the code number of the axioms will be provable from the axioms. That's an incredible simplification but it's good because it means now we can talk about proof mathematically. To say that something is provable is to say, for example, that its code number must be divisible by the axioms. So now Gödel challenges you with the following statement. This statement cannot be proved from the axioms that we have for our system of mathematics. So this is actually something that has a code number. We can talk about proof using numbers. So this will be a statement that can be changed into a mathematical equation. Now this means because it's an equation in mathematics, it's either true or it's false. So let's start by saying that the statement is false. That means that this statement is provable from the axioms is true. But a provable statement must be true. So now we've started with something which we assumed was false and now we've deduced that it's true. So we've got a contradiction and we're assuming that mathematics is consistent. So we can't have contradictions. This is important. So that means it can't be false. This means it must be true because a mathematical statement is either true or false. It's not like these linguistic paradoxes which just don't have a truth value. If it's an equation of mathematics, it's either true or it's false. We've just shown if it's false that that leads to a contradiction. This means that this statement must be true. Ah, great, we've got a true statement. But let's now reinterpret what it says. It says this statement cannot be proved from the axioms. We have now got a true statement which cannot be proved true from the axioms of mathematics. And that's exactly what Gödel wanted. He's now got a statement of mathematics which is true but cannot be proved. And you go, well, hold on. How do we actually prove that was true? We just proved it's true. And it's very important to articulate what we have done is within a system of mathematics with certain axioms, we found a true statement within there which can't be proved true within that system. We've proved it's true by working outside the system and looking in because we could now add that as an axiom. It's a true statement, so it won't make something which is consistent inconsistent. So we could add that as an axiom. And you say, well, now we've got a proof because it's just an axiom. It's one of these kind of infinite regresses. Gödel says that's not going to help you because I can still cook up within this new system another statement which is true but unprovable. So it's a sort of infinite regress thing that it says that no matter how much you expand mathematics adding axioms, they will always be missing something. A little bit like if you remember the proof that there are infinitely many primes, you say suppose there are finitely many primes, then you prove that there's some primes missing from that list. And you say, well, I'll add those and Euclid just keeps playing the same trick. Well, that's still not good enough because there are still some things missing. Gödel has a similar kind of feel to it that you might try and expand your mathematics to add that as an axiom, but that won't help because you can keep on playing the same game. It feels like though this problem is just restricted to this little self-referential corner. Like it doesn't feel like this puts Goldbach out of reach and other things out of reach. It's just this one little game you can play with referencing to itself. This was mathematicians' hope that, okay, there's some weird logical Gödelian sentences which who really cares about because they don't really have much mathematical content. And I think people just hoped that things like Goldbach would not be one of these, but that hope was really blown away. In 1977, mathematicians came up with some statements about numbers that you think of a kind of like Goldbach nature that you think, well, yeah, that's something I'd want to be able to prove is true. And they showed that these were sentences which were true but not provable within quite a standard system for mathematics. So we've now discovered that we can't hope that it's just weird self-referential Gödelian sentences that are going to be knocked out. It could be Goldbach. It could be Goldbach. Twin primes might also be something like that. Gödel even talked about the Riemann hypothesis. We might be having trouble proving it, but just because we haven't expanded the axioms of mathematics to such a level that it is provable. Now, there are some sentences like Riemann which are intriguing because if Riemann turns out to be a mathematical statement which doesn't have a proof, if we could prove that, that it doesn't have a proof, weirdly, this would prove that the Riemann hypothesis must be true. Now, you go, oh, no, no. Why? Because if the Riemann hypothesis is false, this means that there's a zero off the line. This means there's actually a constructive way to find that. You can set a computer off and eventually, after a finite process, if it's false, it will find the reason why it's false. So if it's false, it must be provably false. So if we find that Riemann is actually undecidable, cannot be proved from the axioms of mathematics, there's no way it can be false because that will be provable. So it must be true. So this is a really weird way that you might prove Riemann hypothesis, is to prove that there's actually an undecidable statement within the axioms of mathematics. If you're watching this video thinking you've got even more questions about good or incompleteness, don't worry. So did I. And there's a whole lot of extra interview footage. Click the links on the screen or in the video description. Also in the video description, you'll find a link to Professor DeSoto's recent book, which has a whole bunch of extra stuff about Godel incompleteness and other stuff that science maybe just can't know. I think it's still interesting to explore the things which might always transcend our knowledge. And of course, religion just gives these things far too many properties they should never have. But I think that rather abstract idea of the unknown is still quite an intriguing one.