In Our Time - Godel's Incompleteness Theorems

Episode Date: October 9, 2008

Melvyn Bragg and guests discuss an iconic piece of 20th century maths - Gödel’s Incompleteness Theorems. In 1900, in Paris, the International Congress of Mathematicians gathered in a mood of hope and fear. The edifice of maths was grand and ornate but its foundations, called axioms, had been shaken. They were deemed to be inconsistent and possibly paradoxical. At the conference, a young man called David Hilbert set out a plan to rebuild the foundations of maths – to make them consistent, all encompassing and without any hint of a paradox. Hilbert was one of the greatest mathematicians that ever lived, but his plan failed spectacularly because of Kurt Gödel. Gödel proved that there were some problems in maths that were impossible to solve, that the bright clear plain of mathematics was in fact a labyrinth filled with potential paradox. In doing so Gödel changed the way we understand what mathematics is and the implications of his work in physics and philosophy take us to the very edge of what we can know.With Marcus du Sautoy, Professor of Mathematics at Wadham College, University of Oxford; John Barrow, Professor of Mathematical Sciences at the University of Cambridge and Gresham Professor of Geometry and Philip Welch, Professor of Mathematical Logic at the University of Bristol.

This BBC podcast is supported by ads outside the UK. Thanks for downloading the In Our Time podcast. For more details about In Our Time and for our terms of use, please go to BBC.co.com.uk forward slash radio four. I hope you enjoy the programme. Hello, in 1900 in the German city of Kernigsberg, the International Congress of Mathematicians gathered in what could be called a mood of hope and fear. The edifice of maths was grand and ornate,

but its foundations, called axioms, were shaking with inconsistent and lurking paradox. And so at that conference, a brilliant young German mathematician called David Hilbert set out a plan to rebuild them, to make them consistent, all-encompassing, and without any hint of a paradox.

Hilbert was one of the greatest mathematicians that ever lived, but his plan failed spectacularly, and it did so because of the incompleteness theorems. These were the work of Kurt Gerdle, and they changed the way we understand maths, took us to the very limits of logic, and sent challenges spilling out into the world of physics, philosophy and beyond. With me to discuss Gerdles Incompleteness theorems,

John Barrow, Professor of Mathematical Sciences at the University of Cambridge, and Gresham Professor of Gehrusham Professor of Mathematical Logic at the University of Bristol, and Marcus Usoitoy, Professor of Mathematics at Wadham College, University of Oxford. Marcus DeSotoi, as I mentioned in the introduction, foundations of mathematical systems are called axioms. So perhaps you could give us foundations for this programme by explaining what axioms are. Yeah, this goes really to the heart of what mathematics is about, out. You start with things that you're happy with. The axioms are somehow the basic things of

mathematics, things that are obvious. For example, if you take a point, two points, there's a line that you can draw through those two points. So that's one of the axioms of geometry, or numbers, for example, the fact that if I add six and seven together, it doesn't matter if I then add seven and six, I get the same answer. So the axioms are somehow the things that we all accept as somehow blindingly obvious. And from there, you build mathematics. So you use logic to then make logical deductions from what these axioms to sort of build up theorems. And from theorems you get more mathematics.

So in some sense, the axioms are the foundations, the things that we're happy with. And then you use the rules of deductive logic, things like Aristotle is a man, all men are mortal, therefore Aristotle is mortal. That's a deduction from two things to get a sort of theorem. So you use the axioms as your starting point, and from there you develop the fact, for example, Euclid proves that there are infinitely many primes from these basic axioms. And could we say, just for conversationally, it started with Euclid?

I would say it started with the ancient Greeks. I mean, you see a lot of mathematics being done in ancient Babylon and Egypt, but it's the Greeks who really start mathematics off as a sort of formal system where you're deducing things from the axioms. And Euclid's elements is somehow the climax of this, where he writes down the axioms for geometry and numbers and starts to deduce some of the first great theorems of mathematics. But because of these taken axioms, mathematics assumed the apparel of that discipline above all,

which got a truth, which penetrated truth, the truth of being of the universe, and gained a great, great status because of that. Exactly. I mean, you look at the theorems that the Greeks proved in the elements. They are as true today as they were 2,000 years ago, and no other science really has that certainty to it. So the idea of axioms and proof are fundamental to what, why mathematics gives you what we feel like is 100% certainty. And it really marks mathematics out as different from the other sciences

where theories get knocked down from one generation. We build on the shoulders of giants, as it were, as Newton said, because we take anything that's proved within these axioms is true and therefore can be built on in the next generation. But by the time I've come around to 1900, sorry about the 2,000-plus, 2,200-year leap. axioms are seemed to be under some sort of threat Euclis axioms

Yes I mean the point is The whole truth and nothing about the truth Well the nucleus axioms were Seemed to be only part of the story This is what mathematics was beginning to develop so much That we were starting to see very new things appearing One of them was new geometries Non-Euclidean geometries

So we found geometries which actually didn't satisfy One of Eucliz axioms About parallel lines but they looked totally consistent and that we realised that there were just many sorts of geometry but there was a worrying field are they really consistent maybe these things

have contradictions in them somehow because they look kind of weird and new these are geometries where parallel lines might meet or there are many parallel lines and also at that time we see the idea of new sorts of infinities impairing infinity was a concept that in the past was something you couldn't

understand but Cantor at the end of the 19th century, it's suddenly saying, no, we can understand this. There are many different sorts of infinity. You compare one against the other. But these new bits of mathematics started to raise questions about, you know, gosh, well, this looks very sort of worrying sort of area. Might this produce sort of contradictions or inconsistencies? And we began to ask questions about our subject. Well, into this breach, step David Hilbert, as I said in the introduction, John Bauer, brilliant young German mathematician. and in a lecture to the International Congress of Mathematicians in 1900.

He set out an optimistic vision called the Hilbert Program. Can you give us broad outlines of that vision and why it seemed the salvation and so important to mathematics? Something very dramatic had happened at the beginning of the 19th century, as Marcus alluded to, that long ago at the time of Newton and back to the Middle Ages, people thought that mathematics and particularly Euclid's geometry was the absolute truth of things. This described how the universe really was.

It wasn't just a game like chess that had rules and axioms. But all of a sudden at the beginning of the 19th century, people discovered that there could be other geometries. Geometries that described lines and points and behavior on curved surfaces. And all of a sudden Euclis geometry wasn't the absolute. truth. It was just one possible geometry. And so mathematicians began to view their subject as a collection of self-consistent stories or games. And you didn't give any one of them a special status because it was actually true or a description of the real world. And so people had many, many geometries to think about and a different way of approaching mathematical structures developed. How?

how did you test whether some new geometry or new logic that someone proposed was self-consistent? How do you know that it didn't have some horrible fallacy lurking upstream that if you kept reasoning, the whole thing would collapse? And Hilbert was a very great mathematician, probably one of the two greatest mathematicians of his day, who worked on a huge range of topics. And one of his areas of interest was the foundations of mathematics and trying to put it on a very firm foundation.

And he was what became known to us as a formalist. He thought that we should just specify the starting axioms, specify the rules of the game, and then the definition of mathematics would be all the deductions that you could make from those starting axioms using the rules. And he thought this is absolutely foolproof. No erroneous deductions can creep in if we do it right. It's like starting with a henhouse full of hens and chickens,

come back later on there can only be hens and chickens in there, assuming the fox can't get in. So this was Hilbert's very sort of pedantic, almost Germanic approach to mathematics. He wanted it nailed down as a formalistic system. And in this lecture specifically, he listed 23 problems that needed fixing or solving. We're going to focus on the second problem, which asks, I'm quoting here, can we prove that the theory of numbers is free of contradictions and that every statement about numbers can be proved within that system?

That was the challenge he set himself and everybody else and he worked on that for the next 30 years. Yes, Hilbert thought this was obviously true and it was just a matter of plugging away at this to show that it was the case. And so that was the thing that was vitally important to him to prove this. He thought if he did this, he'd got the whole thing in order, he'd got the equivalent of Leibniz's logic machine.

Yes, he'd started work on a slightly simpler problem a couple of years before, and that was to rigorously lay out what were all the axioms of Euclid's geometry. I mean, Euclid had actually missed some out, and there were certain very obvious things you couldn't prove with Euclid's axioms that were evidently true. And so he first of all did this for geometry, and he showed that geometry, was a complete and decidable system.

What that means is that if you make a statement about geometry using the words and the concepts, you can decide whether this is a valid statement of geometry and you can decide step by step whether it's true or false by reasoning from the starting assumptions. And so he thought that just by adding a few more rules, geometry would turn into arithmetic and we could produce the same proof

that arithmetic was also decidable. Philip Welch, how did the development called set theory play into what Hilbert was doing? Well, set theory had been more or less invented by the German Gero Cantor in 1873.

We can almost date precisely the time and day where he discovered there were different kinds of infinities. What Cantor was trying to do was to think about just infinity or infinite sets. in the abstract. Previously to that, people had always thought of sets as being given by some rule or by some function. But Cantor was interested in just the overall global concept of what a set might be. Can you tell the listeners what a set might be?

So we think of a set in mathematics as just being a collection of objects. And what we find is, in fact, this can be really rather general. We think of a set as just being an aggregate of its members without any other properties. other than just being this collection. Is there any way you can objectify that a little more? So the set of people in this room consists of the four of us around the table here, and that is just a collection, and in mathematics this will be a set. We could have a set of points on the plane,

we could have the set of decimal numbers along the real line, we could have the set of counting numbers. All of these things are mathematical sets. What Cantor was trying to do was to try and give a system in which one could just reason about a mathematical set. And how did that run up against the idea that Marcus developed at the beginning of the program, about axiom? Well, Cantor himself didn't actually lay down a formal system of axioms. And this is obviously one of the things that Hilbert would have liked,

is that there should be something formally giving us a system for set theory. It wasn't until Zamello in 1908 actually laid down a formal axiomatic system there. But there were already rather cracks appearing in this edifice of set theory. And after 1900 in Hilbert's announced speech of these problems, Russell discovered a paradox in set theory. This is Bertrand Russell, yes. This is Bertrand Russell. Russell was working from a slightly different direction.

He was making a critique of the German philosopher Gottlob Frege's attempts to reduce arithmetic, just purely logical principles. Now this was a different programme from Hilberts. It was called the Logist Programme. And this was what Frege was essentially, this was his magnum opus, was to actually try and achieve this objective. Now Russell discovered that there was actually a paradox.

in Frege's system that one couldn't just simply define willy-nilly a class of objects and that this would be a set. So there seemed to be problems about defining sets in general. So how did this paradox, as it were, if I say this correctly, there wouldn't be flaw a flaw the set system. Can you walk us through this paradox?

So the paradox is roughly similar to a paradox called the Barber paradox. So one imagines for the story of the sake of the barber's paradox that there is an island and on this island all the adult males are shaven. Some shave themselves and others are shaven by the barber. There's only one barber in this island and the barber shaves every male on this island who does not shave himself and only those males. So he shaves all and only those people who don't shave themselves.

So the barber being a male, you ask the question, does the barber shave himself or not? And either way you try and work it out, it comes to a contradiction. Can you work it out a little bit? Tell us how about it. If the barber does not shave himself, by definition he's supposed to shave all of the men

who don't shave themselves, so he must shave himself. But if he does shave himself, then he's not supposed to shave himself because he's supposed to shave himself, because he's supposed to shave himself. only those people who don't shave themselves. So either way this comes to a contradiction.

Now, Russell's paradox is the equivalent version of this. What Russell did was say, well, if I can define sets in general, just by any kind of description, why don't I define the set of all of those sets that are not members of themselves? Now, the set of these people in this room is an abstract object, right? It's not a person in this room.

so the set of people in this room is not a member of itself so Marcus is a member of the set of people in this room so am I, so are you, it says John but one could consider those possible realm of sets which are not members of themselves

if you consider all of those that class of sets and then you ask is that class of sets if that set is a member of itself or not it's supposed to be the collection of all of those sets that are not members of themselves, so it can't be a

member of itself. But if it's not a member of itself, then it must be, because it's the collection of all of those things that are not members themselves. I'm glad you started with a barber on the island. Right, Marcus, let's move on to 1931, another gathering on mathematicians, again at Kernigsberg,

another brilliant man, young man delivering a lecture, this time Kurt Gödel, he delivered a lecture, curious enough, the day before he Hilbert's lecture. Hilbert not knowing. Well, yeah, anyway, never mind, that doesn't matter. Well, it's kind of curious, coincidence.

Let me finish the bit. Sorry, yeah, absolutely. And then you can talk for the rest of the program. And that destroyed Hilbert's vision. And his lecture was about the incompleteness theorem. So we've got to the subject. Right. Exactly. Right. So Hilbert actually was receiving the citizenship

of Kernigsberg, the day after Gerdl gave this lecture. And he really summed up again the belief of most mathematicians with a talk he gave, which says, we will know we must know there was a feeling like that any true statement we should be able to prove and we should be able to prove that mathematics is a self-consistent system

but what Girdle had done the day before is to show that both of these projects were totally flawed first of all you cannot prove that a logical system for number theory you cannot prove within that system that it is consistent that it doesn't have contradictions

So it's impossible to prove within a system for number theory that there won't be contradictions. Secondly, he proved in sense this is what the incomplete is, there will be true statements about numbers, which within that system you will never be able to prove. And this went really against what Hilbert believed. Hilbert finished, mentioned in his address in 1900, that there are no unknowables in mathematics. but Gödel was saying, no, it's an intrinsic part of mathematics

that within number theory there will be statements about numbers, true statements, which will never be able to prove within that axiomatic system. So it was incomplete, it was almost put some sort of uncertainty at the heart of mathematics, which meant to be a subject which could prove 100% truths and prove all truths. John Barrier, can we continue on that, as it were, the clash of these two theories, most curiously in two days. And just take, not take us vote, address yourself to that as Marcus has just done.

Yes, I think there was only one person in Gerdell's audience who really understood the impact of what he was telling them, and that was John von Neumann, who took up the idea so quickly that within a few days he had deduced the second theorem of Gerdels and but then was disappointed when Gerdel told him that he'd in fact already prove that one too. So what Girdle was really showing, a sort of a pictorial addition of this that I like to think of,

is if we think of a game board like chess where the rules of the logic are like the moving of the pieces, then what Hilbert was imagining is that if someone showed you a configuration of pieces on the board, you would always be able to tell whether that was a configuration that you could reach from the starting stage. of the game and whether it was also an allowed configuration on the board. So if you look at a chess board when all the pieces are on there and the two white bishops

are both on white squares, that's clearly not allowed. But what Gerdel's theorem is really saying is that there are configurations on the board which you cannot decide whether you could have reached those from the starting state or not following the rules

of the game. How did Hilbert find out about Girdle's ideas and how did you react? Well, Bernice, who was an associate of Hilberts, spoke to him about this. And apparently his first reaction was anger. He didn't want to hear about it.

Eventually he seemed to come round to believing that Gerdl really had proven what he'd said. But there was still some resistance on his part. And in fact, he never published again on this subject. So did he, that... I acknowledge that Gerdl had driven... I don't think he actually ever said anything in print about this, but I think the assumption is that since he didn't work on this project anymore,

that he must have realised that Gerdl had done this. John referred to the fact that the only one man there who understood it, but he got working on it. Presumably it spread right across the mathematical establishment community very quickly. Well, I think not. I think that people were rather slow to react. I mean, von Neumann took these results back to Princeton and talked about them there.

Other people seem not to really have absorbed the results very quickly. Russell's reaction was, although he'd not been working in mathematical logic for some time, his reaction was, oh, we supposed to now believe that 2 plus 2 equals 4.001. And then he said, oh, I'm glad I'm no longer working in mathematical logic. Zamello, who'd formalized said theory, was now rather often a world where he didn't work in first-order logic, which is the logical system which these results are proven in. He was off in a slightly different world of his own working in a so-called second-order logic,

and he really didn't want to understand too much about these theorems, I think. The French really didn't seem to pay very much attention to them immediately. the Borbaki group seemed for some years not to have really understood what Gerdl was talking about and still thought in print that the Hilbert system

was still up and running. Before we move on and try to and go more into this theorem John Barrett, it might be worthwhile for our listeners to say the difference between these two characters

was part of the interest because of the difference between the two of them. Can you just briefly sketch their differences? Hilbert was rather unusual. I mean, he was a German professor, so you might have expected that he will be very much in the hair doctor, professor, highly formal Germanic mode, whereby professors didn't have anything much to do with younger people, younger lecturers and certainly not with students.

But Hilbert was famous for not being like that. A bit of a scandal. So he was very interactive with young people and he would have students to his home. And so one of the reasons I think his whole program became rather well known and why we're talking about it was because he did interact with a lot of people and he became a focus for an awful lot of mathematics. Gerdle, on the other hand, was completely reclusive, very, very strange person. He had no collaborators, he had no research group. He worked on his own.

He did very difficult things and he thought about them for a very, very, very, very long time before he published anything. People said when they met him at Princeton that he was really rather terrifying because if you went to talk about anything, you would soon discover within a matter of moments that he had thought through every implication of what you were going to say long ago, you know, and saw immediately to the end of any argument that you were about to start. One of you know that's calling the greatest logician since Aristotle. Anyway, so they had very different personalities,

even though they came from the same sort of Germanic tradition. They were very different sorts of people. Although Gerdl did work in one other area rather than logic, he worked in the general theory of relativity and found a rotating universe solution of Einstein's equations that allowed time travel to occur. So this astonished Einstein. Again, very remarkable that he was able to find an exact,

solution of Einstein's equations. A very difficult thing to do. And so Hilbert also was involved in the foundations of general relativity. So culturally, temperamentally, they're really very different sorts of people. Can we just stay with these theorems for a few minutes longer, Mark as you so, sorry, to I. Because they are very important. Now we're going to try to track their effect and their importance. Can you just talk a little bit more about how Gerdle illustrated his sense?

theorems and... Yes, I think it's really important to show how he proved these things because I think it's quite remarkable. In a way he takes one of these sort of linguistic paradoxes and encodes it inside number theory. He takes the statement

this statement cannot be proved and what he does is to produce something called the girdle coding which translates that sounds like a statement about language or a sort of meta statement but he produces something called a girdle coding which actually uses my favourite numbers, the prime numbers,

to change that into a statement about pure number theory. Now... So we've got this statement can not be proved. Yes, is now just a statement about numbers, meaning something about numbers,

using this girdle coding. Now, this statement about numbers... How does it work, though? How does it work? Yeah. It works by translator... Gosh, now you're really pushing me. It works by sort of translate...

Every... Every symbol inside... within that logical statement that I've said, can be translated into some sort of numerical value, which has relationships between them according to their logical connections, and so it can be translated into therefore a statement

about numbers and not about the logic itself. So I don't want to be pushed further on that one, because we're going to go for... I don't want to... I don't want to go any further. Okay, we've got to... The hands are going up right around the day. When Mark is finished...

Yeah, I'm going to finish. And then you can explain a little bit more about how the girdle coding works. Because this is now a statement about numbers, and therefore is either true... or false. Now let's look at the implications of this. If this statement is true, let's reinterpret it back. It says that this statement cannot be proved. Sorry, I want to do this false. If it's false, it says this statement cannot be proved. So that means it's false, which means it can be proved,

but if something can be proved, it's true. So that's contradiction. So the assumption that the statement was false, must be false, which means the statement must be true. We reinterpret that back to the statement about language. It says, this statement cannot be proved. So that is now a true statement, and therefore Girdle has proved that there are statements which cannot be proved. Thank you, Philip. I'm calling in, Philip. And then John. I think it's important to note that actually the incompleteness theorems are really about syntax.

They're given a syntactic statement. They're not really, and Gertel was careful to phrase these things in terms of syntax. So by syntax, I mean the nuts and bowl. of the actual formal system, the way the axioms are written down, the language that it's written in, the finite set of deductive rules that you might have to work with the axioms.

So the girdle coding gives a mapping of these axioms, which can be an infinite set. They don't have to be a finite set of axioms, a mapping of the set of axioms into the numbers itself. And this is done in a sufficiently clever way so that formal things about moving the marks down on paper, then become just

simple operations on the code numbers. It's not really about semantics or truth, although you've given a very nice kind of explanation in terms of truth. But what Gerdl wanted to do was to actually talk about Hilbert's formal consistency program. And for that, he just needed to produce, we had to produce something that was just syntactic rather than semantic. And he couldn't appeal to notions of truth

to actually prove the theorem. So it's important to note that the theorem is just stated in terms of syntax rather than semantics. John wants in, now we come back to Marcus. John? Yeah, just to amplify a bit. I mean, so what Goetl managed to do was to set up this one-to-one correspondence between mathematics and statements about mathematics. And Marcus's prime numbers help you because one of the great theorems of mathematics is that if you take any number, I suppose six,

you can express it just as the product of the prime numbers that divide it. So two times three. And there's only one way to do that for every number. And so he decided that if he had a formula or a statement like 2 plus 2 is 4, that he would attribute a prime number to each ingredient of that statement. So to the 2, as it were, in inverted commas, the plus and the other two, the equals and the four, and then he could multiply those prime numbers together and get a number which uniquely characterised that statement. And so then he's got a way of using numbers to encode

statements about numbers, and that allows him then to follow through on Marcus's sort of paradox to get the contradiction. And this paradox, I think it's a bit like those cards that people, listeners might know, we say the statement on the other side of this card is true, and you turned it over and it says the statement on the other side of this card is false. And you can't make any sense of that one. But the wonderful thing is that when you, when Gerdle looks at this thing, you can make sense of it. And the implications are that there are true statements about numbers which cannot be proved within that formal system. How radical did this come to be thought of as being? I hope that sentence is syntactically approved by Philip Ler. Mataga.

Well, I think in some ways mathematicians, I mean, I'm a mathematician, so I'll talk from a mathematical point of view on the philosophical one. I don't think it really had very much impact because mathematicians are really just getting on with their subject. It worked. It didn't seem to have any contradictions in it. It seemed to be consistent. The sort of things that you wanted to prove eventually you seem to be able to prove. So on the whole, I think mathematicians felt, well, okay, we may not be able to prove that number theory. is consistent, doesn't have contradictions, but the more we do it, the more that gives us evidence

that it's not going to give us contradictions. There was one interesting point, which is this guy Cantor, who looked at infinite sets. He asked a question which was actually Hilbert's first question, which was, is there an infinite set between the set of counting numbers and the set of infinite decimal numbers?

There are two different sorts of infinity. One, three, four, five, six, and then pi. Yeah, one, two, three, four, five, six are the counting numbers. So that's the sort of first sort of infinity. And then Cantor discovered that if you take things like pi square root of two, that these are a different quality of the infinity bigger than the whole numbers. And Cantor asked, is there a set infinite set of numbers which is strictly bigger than the counting numbers

and strictly smaller than all the infinite decimal numbers? And this was actually Hilbert thought this was so important that he chose this as the first problem on his list. Now, the amazing thing which Gerdl contributed to, but was eventually proved by Paul Cohen in the 60s, we came to the realization that both answers could be true. There could be an infinite set there, and there also couldn't be,

that you could actually add a statement into, as an axiom, that there is an infinite set between these two, and the system would remain consistent, and we could add its negation. And this was in a way, showing us in a similar way that the non-Nuclidean geometries showed us there are many sorts of geometries. We suddenly came to the realization there are actually many,

different sorts of mathematics and quite often you have to make a statement about which axioms you're using are you using something called the continuum hypothesis or not so it does impact on mathematicians it does seem john barrow that we are just from very much from a sort of amateur outsider entering into a world where things have changed i mean what you're talking about all three of is well actually people got on with their jobs and it wasn't it but for instance um uh one of gerdell's contemporaries Herman Viles said the incompleteness theorems were, quote, a constant drain on the enthusiasm and determination

with which I pursued my research work. Put colloquially, for some people seem to have thought that the bottom dropped out of their faith in the power of traditional mathematics. As if you were a formalist like Herman Vial

was, then it would be a rather psychologically inhibiting result. So you would have expected to be able to decide the truth or falsity of any statement that you were given in arithmetic. So if you were involved in that sort of research on the foundations of mathematics, then it had a big impact. It was the most important result ever proved.

But if you were someone building airplanes and using applied mathematics for that purpose or studying oscillations of waves and doing algebra and so forth, non-Euclidean geometry, then it didn't really impact polypacetion. your daily life. And if it ever had, you had a simple remedy. You see what it was saying, if you had a particular number of axioms, you're going to encounter statements that you can't show to be true or false. But all you need to do, perhaps, is then add another axiom to your system. You could create two new systems, one in which the undecided statement is true, another where it's false, and carry on. There will be new undecided statements, creative,

by doing that. But an applied mathematician would sort of work their way around this incompleteness. It's only if you're a logician that you really need to understand it very deeply and you want to identify problems which are undecidable. Philip Welsh. I think another aspect that's important to emphasize about these incompleteness theorems is they don't in any way raise doubt about the consistency of the formal system, piano arithmetic, which we axiomatize

arithmetical notions. They don't raise any doubt also about Zamelo-Frankel, the axiomatic system that really encompasses almost all of mathematics. Indeed, Gerhard Genssen, a German mathematician, showed that piano arithmetic could be consistent by going

to a larger system where one was allowed to do inductions infinitely often, up to some certain number, of times. So it's not that we suddenly had doubts about whether piano arithmetic really was consistent or not. One could go to a simply

stronger theory and prove the consistency of piano arithmetic in that stronger theory. So logicians, I think, were not in any worry that the whole house of mathematics was going to collapse because of the girdle theorems. I think it's also important to point out

that all the theorems that had been proved up to that point were still true. It didn't shatter anything that had been proved up to that point. It just showed that there were things that were maybe beyond being able to be proved within a particular system. And I think it did create a worry in people. I like your quote, a Viles quote actually, because it does mean if you're working on something like the Goldbach conjecture, is every even number the sum of two prime numbers? Well, what if that's actually an undecidable statement and you're dedicating your whole life to trying to prove this thing? And

actually within the system that you're working in, it's not going to be able to be proved. So I think it does create a sneaking worry, and most mathematicians stick their head in the sand and try and ignore it. Did it bring up a debate about the difference between proof and truth in mathematics? John? Yes, I don't know whether it brought up a debate.

I mean, it demonstrated that there was a difference between truth and proof, so that there could be statements that can be proved true in one system, but not proved true in another system. So Gerdley is showing that if you have a certain number of rules and assumptions, there's only an amount of information there really to get at doing certain things. And perhaps you shouldn't be too surprised by that.

Mathematicians previously had encountered impossibilities. They knew that there were things that you couldn't do. That a simple equation that had a fifth order polynomial, we meet quadratics at school, a x square plus bx plus c is nought. And we know there's a handy formula for finding the solution for X. And there is if it's a cubic or a quartic equation, but you could prove that there could be no such formula for a fifth order equation.

So mathematicians had experience of proofs that something could not be done. And this was a reflection of the complexity of the system they were dealing with. The way I interpret Girdle is that what he's saying is that if you have a logical system that's complicated enough, then you have this incompleteness. And the level of critical complexity arrives when you add arithmetic. Because there's no girdle theorem for Euclidean geometry. So that's every statement of geometry can be decided true or false. But it's when you add numbers and arithmetic that the incompleteness kicks in.

And I think the reason is, is because of this prime number factorization, that individual numbers can be identified by this prime factorisation. So they're uniquely specified by their factorisation. And that means that you can have a link between statements about them and numbers unambiguously. Whereas in geometry there are points and lines and they're all identical,

that there isn't a way of identifying a point and therefore having this correspondence between statements about points and points. Thank you very much. Yes, I think Hilbert famously said that in his aximatization of geometry he wasn't concerned what the points and lines were. They could be beer mugs, penguins or tables.

I mean, Hilbert had this kind of perhaps at least this kind of thin vision of mathematics as being this set of, I mean, I think he said at some point that it was just an inventory of provable formulae. Gerdle, on the other hand, had this rather rich kind of platonic conception of mathematics. This is an example of differences in their character. He had this rich platonic conception of an objective world of mathematical objects, perhaps outside of space and time,

but nevertheless, something that one could have some access to through mathematical intuition. Hilbert, on the other hand, as I said, had this rather thin formalist view of the matter. What relevance did Girdle's incompleteness theorems? Does it have to computers, for instance? Well, interestingly, one can derive now Girdle's incompleteness theorems from Turing's work on the unciridability of the halting problem. So this was something that emerged in the same decade in the 30s when Turing went to Princeton to work with Church,

associate of Gerdles there. Turing and Gerdel never actually met. but Turing was trying to provide a foundation for, well, what we would now call computer science, but he invented the whole idea of a machine himself or computing machine, and gave the mathematical theory for it. And what Turing showed was that there was no kind of an equivalent, or something equivalent to Gerdl's theorem, that there was no way that one could decide of a given program

whether it was actually going to halt on a certain input. and we can now view this undecidability of the hoarding problem as a version of this girdle incompleteness theorem. I think it's also a sort of positive spin that mathematicians put on girdle as well, which is in relationship to the computer because a computer can be set to churn out all the theorems of mathematics

within an axiomatic system. You just get it going through all the different possibilities of proofs. And this is, girdle's incompleteness theorem is sort of saying, well, there are things that the computer will not be able to get access through this formal system, but mathematicians, by looking at the system,

looking outside the system, working outside the thing, might be able to get at those truths and show that they're true within another system. And so there was a positive spin to the incompleteness theorem, which is saying somehow, mathematicians are better than computers. Can you, I'm sorry

about this, John, can you briefly give us some idea of the way waves were made in other disciplines because of the incompleteness theorems? Well, philosophers and scientists latched onto it in strange ways that you still read about today. So there was a rather quick reaction from some people that thought that on the one hand, just as it was showing you that computers can never replace human beings, you know, that there were

mathematical truths that the computer could never reach, and only human intuition could get at it. So perhaps because science and physics is based on mathematics, there was some incompleteness about physics and science that we could never know all the mathematical laws of nature. And you sometimes saw this even being cited by theologians, like Yaqui, for example, as being a limit to human understanding of the universe. And then there were others who took a more optimistic view, like Freeman Dyson, who saw it, it was just confirming that discovery could never be You know, we were always going to be exploring and finding new things about the universe. Well, we're a rather pedantic appropriateness.

We have to end this program in completely covering the subject. I'm very sorry for that. But thank you very much, Marcus Sotoi, John Barrow and Philip Welsh. I think this will arouse a lot of interest among our listeners. And next week, hold on, we're going to talk about the 18th and 19th century quest for the spark of life and the signs behind Frankenstein. Thank you for listening. We hope you've enjoyed this Radio 4 podcast. You can find hundreds of other programmes about history, science and philosophy

at BBC.com.ukuk forward slash radio 4.