Gödel’s Incompleteness Theorem – Numberphile

[Marcus du Sautoy] 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, that 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 his is 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. It might be quite difficult to find like Fermat's last Theorem took 350 years to, before 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 shows 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, which means that –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 realized that [in] mathematics you can't have those; yet when I took this course on mathematical logic, and we learned about Gödel's incompleteness theorem, he used 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 have been kind of inspired by certain kind of 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 you– the challenges well is that set in this set or not? Actually, a really nice kind of version of this is another sort of mathematical Kind of verbal Paradox is all those numbers that can be defined in less than 20 words so for example [1729] which is the taxicab 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 less than 20 words So then you define the following number then the smallest number which cannot be defined in less than 20 words Now I think if you count add 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 — 20th century [his] 23 big on 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 math 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 called axioms which are the kind of things we believe are [the] way numbers, geometry works, so for example if I take six and I add seven to that I don't think it's going to be different from taking seven and adding six to that. That seems so blindingly obvious and that's one of the axioms [of] the way numbers work. So 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 what we haven't actually captured the whole of mathematics and that was somehow the — 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 through 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 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 the thing we now called the Gödel Coding. So he showed that any statement about numbers has its own particular code number. In fact you use 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 and 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.

OK so what do these code numbers look like? They're obviously whoppers. 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 a computer [have] zeroes and ones. Very good. So if I'm typing away and I write the name 'Gödel' that 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 within — mathematically to say that something is provable is to say for example that it's 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. It is 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 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 can 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 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 he 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 Gajillion 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 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 Gazillion 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 talks 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 ahh 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 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 is actually an undecidable statement within the axioms of mathematics If you're watching this video thinking you've got even more questions about Gödel 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 du Sautoy's recent book which has a whole bunch of extra stuff about Gödel incompleteness and other stuff that science maybe just can't know To think that you 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 [it] is still quite an intriguing one

You May Also Like