YTread Logo
YTread Logo

Gödel's Incompleteness Theorem - Numberphile

Jun 02, 2021
I've been quite obsessed with Gödel's

incompleteness

theorem

for many years because it imposes an extraordinary limitation on what we could know in mathematics. In fact, it's a rather puzzling

theorem

because it essentially says that there could be conjectures about numbers, for example something like the Goldbach conjecture, that could actually be true. So, it could be true that every even number is the sum of two primes. but perhaps within the axiomatic system that we have for mathematics, there is no proof of this. The real concern is what if there is a true claim I'm working on that actually has no proof.
g del s incompleteness theorem   numberphile
Now, yours is a great revelation for mathematics because I think since the ancient Greeks we believed that any true statement about mathematics would have a proof. It could be quite difficult to find Fermat's Last Theorem, as it took 350 years before my colleague at Oxford, Andrew Wiles, found the proof. But I think we all have this kind of feeling that surely every true statement has a proof, but Gödel shows that there is actually a gap between the truth and the proof. I wrote it here because it's pretty cute. So it's one of these cards: "the statement on the other side of this card is false." So let's assume that's true.
g del s incompleteness theorem   numberphile

More Interesting Facts About,

g del s incompleteness theorem numberphile...

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 must be false. So it means that the one on the other side is also fake. Oh, but we assume that was true, so that's false. So the other side is true, which means that... and you go into this kind of infinite loop. Verbal paradoxes are fine because every verbal sentence is not expected to have a truth value. But then when I went to university, I realized that in mathematics you can't have those;
g del s incompleteness theorem   numberphile
However, when I took this mathematical logic course and we learned about Gödel's

incompleteness

theorem, he used this type of self-referential statement to really undermine our belief that all true statements could be proven. There was a feeling that we should be able to show that mathematics is something called consistent. That mathematics will not give rise to contradictions. This was inspired by certain kinds of little paradoxes that had occurred to people like Bertrand Russell. People may have come across this idea of ​​"the set of all sets that do not contain themselves as members" and then you...the challenges, is that set in this set or not?
g del s incompleteness theorem   numberphile
Actually, a very good version of this is another type of mathematical paradox, type of verbal paradox, is all those numbers that can be defined in less than 20 words, so, for example, what is the taxi number that they talked about? Ramanujan and Hardy, you can define it. In less than 20 words? It is the smallest number that is the sum of two cubes in two different ways, so it has less than 20 words. Then you define the next number and then the smallest number that cannot be defined in less than 20 words. Now I think if you count sums, I just defined that number in less than 20 words and that's it.
That's a little worrying because it's surely some kind of number. We could define the smallest number that has a certain property. So there was a real sense that these paradoxes, these paradoxes of set theory, were starting to be a real challenge to mathematics in the early 20th century and David Hilbert one of his great problems with which he challenged mathematics in the 20th century...23. big on unsolved problems, the second was to demonstrate that mathematics was in fact consistent and included in that that every true statement should be provable, but what a surprise, actually 30 years later comes this Austrian logician Kurt Gödel who ruins this idea that we can show that mathematics is consistent out of water and show that there are true statements that cannot be proven within any mathematical system.
How does mathematics work? We set out things we call axioms, which are the kinds of things we think are numbers, geometry works, so for example, if I take six and add seven to it, I don't think it's any different from taking seven and adding seven to it. six to that. That seems so blindingly obvious and is one of the axioms of how numbers work. So maybe somewhere that's wrong, but I don't really care, I'm interested in a math where that's true for all numbers. And I have rules that allow me to make deductions from those axioms.
And that's how math works. Every time we make these logical deductions we expand the conclusions of these axioms. We can add new axioms if we feel like we know what we haven't really captured as a whole in mathematics and that was kind of... the mission was that we want to have a set of axioms that are strong enough and that we think are basic. . about numbers from which we can deduce through statements that we will have a proof and then there was a feeling that well, yes. Well, maybe we don't have all the axioms and if we have a true statement that can't be proven, we could add it as a new axiom and it will expand what we can prove in mathematics.
So this is very important for Gödel. because we are trying to show that there will be a set of axioms from which we can deduce all the truths of mathematics. Gödel did something very clever because he devised a way to allow mathematics to speak about itself. So what he produced was what we now call Gödel Codification. He then showed that any statement about numbers has its own particular code number. In fact, he uses prime numbers to perform this encoding. So every statement about mathematics could be converted into a number, so that, for example, the axioms of mathematics from which we try to make all our deductions would have code numbers and true statements about mathematics, so, for example, Fermat's last theorem will have a code number, also false statements like "17 is an even number" will have a code number.
Well, what do these code numbers look like? They're obviously fantastic. They are absolutely huge, but it is a single encoding, so each 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 around: every mathematical statement will have a unique number associated with it. It's a bit like most things on a computer with zeros and ones. Very good. So if I'm typing and I type the name 'Gödel', it will be changed to ASCII code. It will have an associated number. So Gödel invented this, but why is it useful?
Because now you can talk about proof in mathematics using these numbers. Then you can start talking about mathematics using mathematics. So, for example, you might want to know well: can this particular statement be proven from the axioms? That's... I'm going to simplify this completely, but it will give you an idea. Essentially, it's a bit like saying that 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 a good one because it means we can now talk about internal 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 proven from the axioms we have for our mathematical system." So this is actually something that has a code number. We can talk about proof using numbers, so it will be a statement that can be converted into a mathematical equation. . Now this means that because it is an equation in mathematics, it is either true or false. So let's start by saying that the claim is false. That means that "This statement can be proven from the axioms" is true, but a provable statement must be true.
So now we start with something that we assumed was false and now we have deduced that it is true, so we have a contradiction and we assume that mathematics is consistent, so we cannot have contradictions; This is important, which means it cannot be false. This means that it must be true because a mathematical statement is either true or false. It's not like those linguistic paradoxes that simply have no truth value. It's a mathematical equation. Either it is true or it is false. We have just shown that if it is false, that leads to a contradiction. This means that this statement must be true.
Oh great. We have a true statement, but now let's reinterpret what it says. He says: "This statement cannot be proven from axioms." We now have a true statement that cannot be proven from the axioms of mathematics. And that is exactly what Gödel wanted. Now he has a mathematical statement that is true but cannot be proven. And wait, how did we prove that was true? We have just proven that it is true. And it is very important to articulate what we have done within a system of mathematics with certain axioms, we find a true statement that cannot be proven within that system.
We have proven it to be true by working outside the system and looking inside. because now we can add that as an axiom. It's a true statement, so it won't make something that is consistent inconsistent. So we could add that as an axiom and you say, well, now we have a proof because it's just an axiom. It's one of those types of infinite regressions. Gödel says that won't help you because I can still invent within this new system another statement that is true but not provable. So it's a kind of infinite regression that says that no matter how much you expand mathematics, adding axioms, something is always missing, a bit like if you remember the proof that there are infinitely many prime numbers.
You say, suppose there are a finite number of primes, then you show that some primes are missing from that list and you say, well, I'll add them and Euclid. keeps playing the same trick. Well, that's still not good enough because there are still some things missing. Gödel has a similar feeling that you could try to expand your mathematics to add that as an axiom, but that won't help because you can keep playing the same game. It seems like this problem is restricted to this little self-referential corner, it doesn't seem like this puts Goldbach out of his reach and other things out of his reach.
It's just this little game you can play with references to yourself. This was what mathematicians were hoping for, well, there are some weird Gajillion logical sentences that you really care about because they don't actually have much mathematical content. And I think people were just hoping that things like Goldbach weren't one of these, but that hope was really dashed in 1977, mathematicians came up with some statements about numbers that you think are like the Goldbach nature and you think well, Yes, that's something I'd like to be able to prove to be true. And they showed that these were sentences that were true, but not provable within a fairly standard system for mathematics.
So now we've discovered that we can't expect just billions of weird, self-referential sentences to be eliminated. . It could be Goldbach. They could be Goldbach's twin cousins, they could also be something like that. Gödel even talks about the Riemann hypothesis. We might have trouble proving it, but only because we haven't expanded the axioms of mathematics to a level that makes it provable. Now there are some sentences like Riemann's that are intriguing because if Riemann turns out to be a mathematical statement that does not have a proof, if we could prove that, that it does not have a proof strangely this would prove that the Riemann hypothesis must be true.
Now you say, why? Because if the Riemann hypothesis is false, this means that there is a zero outside the line, which means that there is actually a constructive way to find it. You can turn off the computer and eventually, after a finite process, if it is false, it will find the reason why it is false. So if it's false, it must be demonstrably false. So if we find that Riemann is actually undecidable, it cannot be proven from the axioms of mathematics. there is no way it can be false because it will be provable, so it must be true.
So this is a really strange way to prove that the Riemann hypothesis is to show that it is actually an undecidable statement within the axioms of mathematics. This video thinks you have even more questions about Gödel's incompleteness. Don't worry, me too and there's plenty of additional interview material. Click on the links on the screen or in the video description. Also in the video description you will find a link to Professor du Sautoy's recent book which has a lot of additional things about Gödel's incompleteness and other things that science perhaps simply cannot know. Thinking that you already know, it's stillIt's interesting to explore things that could always transcend our knowledge, and of course religion simply gives these things too many properties that they should never have, but I think that rather abstract idea of ​​the unknown is still quite an intriguing one.

If you have any copyright issue, please Contact