[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