Limits of Logic: Gödel's Legacy and Incompleteness Explained

[00:00:05]Crysta asked me when he invited me to speak about girdle and I thought that maybe I was going to speak not only about girdle but about other things that are unknowable but then I decided that for my presentation this morning I would talk just about girdles incompleteness theorem and and try to give an overview of it I'm not going to try to talk very much about philosophical consequences we can talk about that in discussion but just to give an overview of of what girdle did and ah so as Marcus said in his presentation girdle was inspired by paradoxical statements like this sentence is false and um he took that a kind of structure or construction and imported it into into mathematics in a way that nobody could have ever expected I have broken my lecture up into so-called chapters I don't know what that means but it's just for the humor of calling things ah chapters so um mathematics you know about four or five hundred years ago was there was no symbols practically at all it was all done in sentences there were not even such a thing as an equation or letters of the alphabet used for variable names or constants those things were invented Descartes I think it was invented the idea of using letters of the alphabet to represent numbers letters the beginning of the alphabet to represent things that were constant letters toward the end of the alphabet to represent things that were variable and there was a Scottish mathematician whose name I've forgotten his first name oh I think was Robert but I don't remember his last name who invented the equals sign four or five hundred years ago it's kind of hard to imagine mathematics without any symbols at all but that tells us that we've come a long way in in the 17th 18th 19th centuries mathematics became extremely formal but people didn't they still didn't a lot of it was done in language as it is today but they didn't know exactly what was rigorous and what wasn't huh lots of things that seemed paradoxical were discovered by people like Euler and many other people ah and these paradoxes gave rise to a lot of concern about the reliability of mathematical reasoning even though it was felt very rigorous and very precise the the idea was they wanted to try to pin it down in sort of a formal way so that for once and for all they would know what was mathematical truth now since this is a short lecture I'm not going to try to summarize any of that there were lots of people who contributed I could name people like a bull George Boole Augustus de Morgan goat Loeb Vega and David Hilbert and many many others epic piano there were many people but the people that I want to talk about in particular this is Alfred North Whitehead and hisses Bertrand Russell a rather humorous photograph of Bertrand Russell and their great opus principia mathematica which came out in three volumes in years 1910 to 1913 was an attempt to to formalize all of what mathematics was and to unite it with logic and artifact to ground mathematical reasoning in logic and the theory of sets and this was a noble attempt and one of the things that lay at the core of their work was the idea of trying to get rid of paradox as I mentioned earlier that was troubling to many people and and to Russell it felt as if the root of all paradoxes was self-reference or sentences that could talk about themselves like this sentence is false or sets that could contain themselves and so he developed what he called the theory of types which was I'm not going to go into it but it was a way of trying to eliminate self reference from coming into a system and it was a very elaborate and and careful Bastion created to prevent self reference from ever coming up from ever arising in such a system and that was something that was very important and for many years ah it was this this is just a page that I took out of it to show the I don't know what you would call it the prick leanness of their notation but for many years uh this their work was taken as being the realization of this dream that of grounding all of mathematics in logic and of formalizing it and of having it be a precise system for once and for all all mathematics was going to come out of this work principia mathematica but in Vienna girdle was caught girdle was in some sense dubious of the of what was of this goal and he felt that there was something wrong about this attempt I'm going to talk about what he did but I wanna I have to first talk a little bit about the nature of mathematical reasoning and how it worked in not only principia mathematica but in any formal system the idea of a formal system is that one has a set of axioms which are written down in a formal notation and uh which are then manipulated in certain formal ways by things called rules of inference I'm certainly not going to detail any of that I hear are some axioms that can be taken for number theory and they're not all of the axioms of number theory but they illustrate things and I'll try to decode this notation for you it's it really doesn't matter very much but the upside-down capital a means for all and so this says for all a this twiddle means not it's a negation the capital S means successor of so this says for all a it is not the case that the successor of a equals zero what this effectively says is I can translate that I can say there is no number whose successor zero successor being the thing you do when you add one every time so basically this is saying there are there is no such thing as negative one there's no negative numbers this one is sort of defining the property of the number zero it says for all a the sum of a and zero is a zero is an additive identity this one says something about the nature of addition it says for a all a and B if you add a and the successor of B it's the same thing as taking the successor of the sum of a and B and that's a rather trivial statement it would seem but it's enough to allow addition to get off the ground then this is the statement that multiplying by zero of course gives you zero and this is a statement that is sort of getting defines the essence of multiplication that is if you multiply a times the successor of B it's the same thing as taking a times B in an adding a on and those statements allow you to do a lot I mean there's there other axioms are needed but I don't I don't want to try to go into it in any detail what what I want to stress though is that when I say formal what I mean is I mean today in the era of computers people are familiar with the idea that symbols can be manipulated by machines back in 1910 1913 and the years in Principia Mathematica came out and in the preceding decades and in the following decades there weren't any computers around even though uh what's his name why am i blocking on names these days uh lady Lovelace's Babbage Charles Babbage yeah Babbage had invented the concept of of computers and it sort of developed them in a theoretical way in a marvelous way so the concept of computers was sort of around not electronic of course mechanical but still but but back then the idea of symbols being manipulated formally was was a was new and uh different and and so uh it it's very important to realize that the idea of these systems was that you didn't pay any attention to the meaning of the symbols I said that this means up this upside down a means for all and that this means not but in a certain sense you're not supposed to know the meanings of these symbols when you when you perform the operations that that I said rules of inference allow you to deduce theorems from axioms those operations are not supposed to be to take into account any meaning they're supposed to ignore the meanings of the symbols the you look only at the symbols themselves and you say okay this this sequence of symbols has a certain form that allows me to proceed from from it to another sequence of symbols I don't know what they mean okay so that's the the idea of formal systems and that was the the notion that that was being pushed in mathematica so I'm going to show two proofs I'm not going to explain the rules of inference being used but I just want to show you that what a proof looks like this is a very short proof this is a proof of this statement that says one plus one equals two that is the successor of zero added to the successor of zero equals the successor of the successor of zero and so here is here's the proof it begins with it makes use of two axioms and then it uses some rules of inference up which I'm not going to describe but formal processes allow me to pass from this axiom to this specification of it to this to this to this to this the only thing that I want you to notice I put a red line on the right margin and I want you to notice that the line sort of goes back and forth it's these this is a long a couple of long things then they get very short and then they get a little bit it gets a little bit longer toward the end that's only a hint of things to come I just want to I just want you to notice that now the other proof that I'm going to exhibit is that one times one equals one it's a longer proof it's more complex but this is about as short as it could get from the set of axioms that I just showed you and this and the rules of inference that I was allowing in this system and I I'm not going to go through it at all it's not important for this purpose I just again want you to look at that at this wavy shape and to see that in order to prove a this is a string of symbols that's very short I had to go through a pathway that involved some pretty long strings what's the longest one it's that one there a lot longer than the result that I was expecting and that's a very crucial fact in thinking about the nature of proofs that is that in some sense we don't know how long a proof how long the strings are going to be that we're going to have to manipulate in order to get in the end a very short string as our result nor do we know how many steps were going to have to use we can't predict that in advance so Bertrand Russell of course was very happy when he was devising he and his colleague Alfred North Whitehead were creating this theory because it was clear that when you wrote down statements about integers I mean even complicated statements like a statement that might express the pheremones Last Theorem that a to the N plus B to the N can never equal C to the N with a B and C being positive integers and n being greater than two that kind of a statement can be written down in this kind of a notation and it clearly doesn't have anything to do with the idea of paradoxical statements like saying this statement is false that as far as you can possibly get from such a thing it's talking about integers and that's all it's talking about and or a statement of the Goldbach conjecture which says any even number greater than four is the sum greater than or equal to four is the sum of two prime numbers which is still unproven but everybody believes it to be true such a statement again has only to do with prime numbers and uh and sums and such things and and how could self referential statements possibly come up in a system that is only talking about integers and their properties so that was on a very something that I'm sure made Bertrand Russell very happy that his system was clearly unable to have self-referential statements now I want to distinguish I've already talked a little bit about theorems I want to talk about something called well-formed formulas because they form a contrast to theorems a well-formed formula is really just a you could say a grammatical sentence something that expresses a statement it could be a true statement or it could be a false statement but it's just a it's just a statement so let's take a look at them here's one that says one plus one equals two that one happens to be true here what is one that says zero equals one that happens to be false but it's they're both equally good well-formed formulas they express thoughts that are either true or false and that's a that's all we need to think about here's one that expresses the commutativity of addition and this one says there is no number a whose square is two and and so forth if I took away the tilde at the beginning it would say there is a number a whose square is two they're both equally good well-formed formulas now what I wanted to tell you about well-formed formulas is that it's very easy to tell if a formula is a formula meaning a string of a string of symbols it's very easy to tell if a formula is well-formed or not I mean for example there's there are some rules basically you just look at its parts and break it up into smaller parts I mean for example here I look at this and I see it begins with the right parenthesis well that tells me I better have a balancing left sorry eyes it begins with the left parenthesis I better have a balancing right parenthesis and it doesn't have to be at the end but it has to be somewhere there has to be a balance of parenthesis and indeed there that balances this balances that doesn't guarantee yet but it's well-formed but it certainly is a part of the test as to whether it's well-formed here is a this thing here stands for if then or implies and if I read this out loud it would say if 1 if 0 equals 1 then 2 plus 2 equals 4 it's not a very interesting statement kind of a silly sounding statement that's not the point but we can read it and make sense of it and this is well-formed in itself 0 equals 1 is well-formed and this is well-formed this is 2 plus 2 equals 4 and then I've combined a 1 statement on another statement with an if-then and that is also an operation that allowed that create that takes two well-formed formulas and makes another well-formed formula from them and on when I build up formulas into well-formed formulas all I do is I take smaller chunks and I build them into larger ones that's all I do so if I and and so if I want to know if a string of symbols is a well-formed formula all I need to do is look at its parts I break it down into smaller parts and I break them down into smaller parts and I keep on going and it's very predictable test of well formative well for madness I'm contrasting that with theorems it's not so easy to know if something is a theorem and that that's what that red line on the right margin was trying to tell you that on the the definition of theorem is something that has a demonstration something that has a proof and in order to in order to know that you have to make a search among possible proofs but you don't know how long that search is going to take and you don't know how long the formulas are that are going to be involved in in that search so there's a kind of a degree of unpredictability to it whereas again the contrast that I'm drawing is there is no unpredictability to the question of how long is it going to take me to figure out whether this formula is well-formed that's a really trivial question okay that contrast is very very crucial I guess I've already said this but so I don't need to go through it it just says test for well for madness by a recursive break down into simpler parts you break for a formula a possibly well formed possibly not well formed string down into parts and you keep on breaking them into their parts until you finally either arrive at you know the it is well-formed or that it isn't it's a very straightforward thing oh so here's here's a string this actually is an expression of the Goldbach conjecture in these formal notation i can sort of tell you what it says here it says for all a there exists a B and a C with the following properties um basically there it's saying this here is it multiplying 2 times a plus 2 so an a can be as low as 0 so a plus 2 is 2 3 4 5 6 and so forth so this is any even number from 4 onwards and it's saying for any a for any this is a this is basically an arbitrary even number and it's saying there exists a B and a C such that a is the sum of these two things and then over here it's saying that B and C are prime numbers I'm not going to decode it for you but basically this is an expression of the Goldbach conjecture as I said still today not known whether it is true or false although everyone believes it's true um so uh is it a well-formed formula just look at it you know I mean it'd take you a few seconds to realize that this is a well-formed formula it's nothing hard about it is it a theorem well try to prove it and hundreds of years of mathematicians working on it have not yielded that ok so you can see that although both properties being well-formed and being a theorem are formal properties that involve the properties of symbols one property is a very simple property that can be detected in a predictable amount of time the other property is one that is is much subtler and more elusive so to sum it up here on the left side it says well form formulas are built up recursively by putting smaller pieces together this idea of this picture is that you are you take small things and you put them together and you've got a big thing the build up grows you can reverse it trivially breaking well well phone formulas in two parts whereas for theorems they are arrived at by you only know something as a theorem if there exists a proof a demonstration of it that is starting with the axioms and following rules of inference combining axioms and combining previously proven theorems into new theorems and that can be a process that involves getting longer and longer strings shorter strings longer shorter you never quite know where you're going and it can take any amount of time and you're not sure so that's a very big contrast between two kinds of structures okay now we come to two types of numbers and this is an analogy that I'm going to use to try to get you to understand I mean many of you already do but those of you who aren't familiar with girdles work to understand the the idea behind his his his construction Fibonacci numbers well you know what they are but all all I'll just mention them the Fibonacci numbers are the numbers that you get when you take sums of previous the previous two numbers 1 plus 2 is 3 2 plus 3 is 5 etc 13 plus 21 is 34 everybody these days is pretty familiar with the Fibonacci numbers now if I were to ask you about if I were to give you a number and say 672 is that a Fibonacci number or not you wouldn't say oh my god I have no idea how to figure that out what you would do is you would you you would generate the Fibonacci numbers up to that size what did I say 672 up to that size or close to it and you would say well it looks like it's not because the next one is going to be above its going to be about nine hundred and something nine hundred eighty seven and that's all I've already gone and I'm never going to get smaller the Fibonacci numbers always get bigger and if I passed 692 well or 670 whatever it was that I said then I guess it's not but if I had said instead three hundred and seventy seven and you hit it you'd say yes it is so it's very easy to know if number is or is not a Fibonacci number it's a very simple test similarly you could say that for primes do i you know is 691 prime or not you divide it by a series of numbers and eventually when you hit the square root of 691 and you haven't found a divisor you know you're done and you know it's it's a prime or if you found a divisor in that period then it's it's it's not a prime and so there are lots of properties of numbers that can be tested very quickly and very predictably in contrast I'm going to talk about I'm not even going to show that you get the idea I'm going to talk about a famous conjecture made by Co lots lotta Co lots in the 1930s he was a mathematician who was specialty with differential equations but he probably is going to be known more for his conjecture than for anything else that he did although he was a good mathematician so I'm going to phrase it in a way that is a little bit different from the way he phrased it but it's equivalent it's the same thing it's just sort of looking at it from the backwards perspective start with N equals one we always start with one and then we have two things we can do we can always jump from n 2 to n we can always double anything we have we can double and if the number has the form 3 K plus 1 such as for example 7 or 22 then we are allowed to jump from this big number let's say 22 down to 7 because 22 is of the four 3k plus 1 is 3 times 7 plus 1 so I can jump from 22 downwards because it's of the form 3k plus 1 I can't do that with 23 because it's not of that form I can't do it with 24 because it's not of that form but with 25 I can do it I can jump from 25 down to 8 because it's of that form all right now so I have these two rules that allow me to do things to the numbers that I have I can go 1 double it get to double it get 4 double it get 8 double it get 16 now 16 is of the form 3k plus 1 so I can go down now I can go to it under 5 if I wish to I could also just double it but I decided that I would use the other rule and I would go down to 5 then I can go to 10 then I can go to 20 and then I can go to 40 oh look 40 is of the form 3n plus or 3k plus 1 so I can go down now I can go down to 13 and I can go up to 26 and so forth I can take pathways in the set of numbers where what what destinations can I reach here is actually the the shortest pathway to 7 it's very very kind of funny pathway I I get bigger then I get smaller then I get bigger then I get smaller then I got bigger and I get smaller then I get bigger than I got smaller then I get bigger then finally I wind up at 7 it's in a kind of a chaotic pathway and it's the shortest pathway to reach 7 now you can see that if I say a is a given number does I'll call these call-outs numbers is a given number a call that's number is not so trivial as as is determining whether it's a Fibonacci number because I don't know how long the pathway is going to be to get there can you get to 3 so here is checking it out and in fact I can get to 3 but I have to you know if I take all the possible routes starting with one I I start going all sorts of different ways it turns out this is the promising route but we didn't know in advance that this was the route to take all right what about 27 this is a famous case that is the shortest route to get to 27 and it goes all the way up I put it I put this number in green and made it large it goes all the way up to 9,000 232 it had you can only go that's the shortest route to get to 27 you have to go all the way up to 9,000 in order to come back down to get to 27 that is really quite astonishing so here's a sort of a picture of it I don't know why it's not it's cut off a little bit at the bottom but I guess that's okay can you see the graph or what I wear those think can you see the graph that's that idea is that it goes kind of chaotic jumps then it goes way up to that then it comes down then it goes way up then it comes down it jumps and finally we get to 27 that's that's an interesting picture and um so I said all of this it's not a test into by recursive break down to the simpler smaller cases and it's not guaranteed to succeed we do we don't know if I say what about getting to 542 using this rule well we don't know how long it's going to take or even if we can get there in advance so now Google although he wasn't familiar with Cole outs numbers because they were only invented after his work was done but he understood yeah yeah the conjecture states that every possible intent positive integer can be reached in this fashion every positive integer can be reached by following this process and it's been tested of all the way out to many billions and it's always been it's always been found but every number works but it's not it's never been proven so um I want to come back to a girdle now gödel had a deep insight I mean in the in the preceding centuries people use numbers to stand for all sorts of things on and I mean everybody knew for example that you could model the physical world I don't mean everybody but people in science knew that you could model the physical world by using equations that that the coordinates of the say the center of gravity of planets could be thought of as numbers and that there were equations that governed their evolution in time and so it was understood that numbers could it could simulate the world but what goodwill saw was that numbers could also integers in fact not real numbers could very easily simulate some things that people had never thought of as being mathematical objects it seemed may be clear after Kepler and Newton that planets moving in orbits were sort of mathematical object and that they could be simulated by real numbers following differential equations but the idea that that formal systems of of the sort that Russell and Whitehead had invented was itself a mathematical system was not something that anybody had thought about they they didn't think of the process of creating a proof as being a mathematical process it was somehow not thought of in terms of in terms of numbers what Google realized was that essentially the manipulation of symbols was a mathematical operation and therefore could be modeled using integers so well here is a picture of a piece of music of piece by Bach and you can imagine encoding this piece into one very large integer the method by which you encode it into a very large integer is not relevant to this discussion but you can imagine that you could encode this in a very large integer and then you could ask questions about that integer which would amount to asking questions about the piece of music even though it seemed to be asking questions about the about the integer it would be asking questions about the piece of music also at the same time so for example question is how many notes are in the piece that's a mathematical question which you could answer by looking at this big integer that stood for it what is the key signature of the piece is it by Bach or not that's a little bit harder to imagine a mathematical operation that will take a big integer and tell you whether or not the piece that it stands for was written by BA but you can imagine maybe maybe it's a mathematical question what nationality was the composer that gets a little bit tricky uh so I I just wanted to raise some of the kinds of issues that you could imagine asking such questions some of them seem trivial how many notes are in the piece and some of them seem a little bit harder ah so if you did the same thing to us strings of symbols like the Goldbach conjecture is a string of symbols I don't know how many it contained it the way I wrote it out I guess it probably contained about 30 symbols and you could imagine now that you could encode it in some fashion as a large integer and I'll explain how good did that how he encoded him as integers but imagine that you have a big integer that in some sense stands for this string then you could ask how many symbols are in this string and that should be something you could be able to figure out is this a fact from the times table that is is it a mere multiplication like two times two equals four or nine times eight equals 72 is that what this string is expressing or is it expressing something else how about whether it's true or false is this a true statement or a false statement can you apply a mathematical operation to the large integer and and know whether it's a true or false statement does it follow directly from another statement is it a theorem of principia mathematica or not and so forth and so forth so on um alright so let's see how did he do oh I have a picture of gödel with an unidentified peasant I think so so good all mapped strings into large integers by taking advantage of the fact that you can on the fact that all all any any integer can be factored in a unique way so here 6 is 2 to the 1 times 3 to the 125 is 5 squared 37 is a prime so it's already factored into its own thing now ah here is a large integer fairly large 1700 we factor it into 2 squared times 5 squared times 17 that is its prime factorization and on the exponents here of the primes that are involved well up to the biggest prime the biggest prime involved is 17 the intermediate primes are 2 3 5 7 11 13 and 17 those are all the primes up to 17 each of them in this factorization has an exponent most of them here are zeros but uh 2 squared 3 2 0 5 squared 7 0 11 etc and so I have a sequence of integers being coded by this large integer sequence of small integers being coded by this large integer this is what goodwill saw he said a large integer can stand for a sequence of small integers an arbitrarily long sequence of small integers and so he then recast all of what was being done by Whitehead and Russell in principia mathematica as a sequence of operations on large integers instead of seeing it as an operations on strings it was operations on large integers so let's take an example that let's look at just one string so see how girdle could encode it as a large integer the string I've taken is that axiom that was the first axiom for all a it is not the case that the successor of a equals 0 which basically is saying there are no negative numbers ok that's the sequence of how many symbols 1 2 3 4 5 6 7 8 symbols so we'll take the first 8 prime numbers and we'll put them to various powers what I have written here is I've actually put 2 to the upside-down capital a but I'm that that may not look like it's an integer but if you think of upside-down capital a as being a digit in in Martian this is just Martian notation and upside-down capital a might be 7 in Martian notation and lowercase a might be 9 and each of these symbols is really just an integer in Martian notation so so when I do do this I I'm just creating a large integer that's all I'm doing and if I want to know what formula I was I was doing it for all I need to do is take that large energy factor it and then look at the sequence of exponents and I can spell out the exact string that I was encoding in the large integer so goodwill had this way of encoding strings into large integers now um it does creates a kind of an ambiguity is this large integer is it a number well yes is it a formula well in a sense yes it's a formula that is a formula to in compute mathematically yes it is it's it's a formula in the sense that it stands for this formula and if we are dealing with it in the context of these formal operations that allow us to pass from one string to another or from one number to another according to certain rules then it can be thought of as a formula it's just a formula written in a funny notation this actually is on the integer that stands for one of the axioms in principia mathematica it's a big integer because the axiom is a complicated statement and and it requires a lot of symbols and using there are many ways of doing what is called girdle numbering this is using a girdles actual system I mean there are many other ways of doing it which would make it simpler but I just thought it's amusing to see that this one large integer is standing for one of the axioms of principia mathematica and you could figure out that it was by just factoring it it might take you a while to factor it but you once you've factored it you could you could you could exactly map out symbol by symbol exactly what this axiom says however it's another thing to figure out if it's a theorem well if you recognize that it's an axiom you're done you know but anyway does a given integer not that one in particular but just to give an integer stand for a well-formed formula that's easy question very easy question because you just you know you can just look at the exponents and then you look at that that's formula and you know how to break it down you can do this with it but you can bypass the translation into this into the the notational system of principia mathematica you can just operate on the integer itself you can have rules that will tell you how to break that integer down into smaller pieces and to this yet smaller pieces and they will tell you whether that integer stands for a well-formed formula or not it's just as mechanical and isomorphic to the process of breaking down a string and asking whether it is a well formed string so it's it's it's a the same question just asked in a different notation does the an integer stand a given integer stand for a theorem well there's no obvious way to know that because proofs are like zigzagging Collatz pathways and this is sort of one of the crucial slides of this lecture I did was I took the proof that this is a proof of a beginning with the axioms let's see yeah this is a proof of the commutativity of addition it says at the end for all D and C C plus D equals D plus C so that's the commutativity of addition and it begins with axioms and uses rules of inference it's a fairly long proof I mean it's actually very short but for our purposes it seems fairly long in it and it requires getting some fairly long statements and and there as well and it's a bumpy root in order to derive the commutativity of addition but in the end we do derive it but notice that we don't know how long this proof is going to be in advance and we don't know how long those strings involved the intermediate stages are going to be there are two completely unknown things and and notice how similar this feels to the Collatz numbers and if we think of these things not as strings now but as integers because remember we can encode as integers were basically doing the very same thing we're taking some smallish integers mathematically manipulating them in various ways getting some very big integers the analog of 9000 232 then we keep you lations we get some other big integers and finally at the end we wind up with the thing that we were hoping for so this is what goodwill saw that the question about whether something is a theorem is a potentially a very complex question unlike whether it's a well-formed formula which is not a very complex question ok so well formed formula numbers the numbers that stand through gödel numbering before well-formed formulas they're like Fibonacci numbers you can test very easily theorem numbers numbers that stand for theorems in the pen Capilla Mathematica are not so simple they're more like call-outs numbers so a way of putting it is well-formed formulas there comes the numbers that correspond to them to make such numbers you just increase the pathway just it goes from smaller integers to larger ones and that's all there is it's just a monotonically increasing pathway this kind of thing theorem numbers is not a monotonically increasing pathway it jumps back and forth in chaotic ways alright um well formed formula numbers are isomorphic to well-formed formulas through girdle's mapping and the pathways that get you to well formed formula numbers are monotonic and thus monotonous nothing very interesting theorem numbers are isomorphic to theorems ah but again since theorem the pathways that get you to theorems are not predictable the same holds for theorem numbers so that's just reiterating what I told you earlier um theorem number of pathways follow unpredictable zigzags ok and so girdle was able to show that the notion of a theorem number was as mathematically precise as the notion of let's say prime number in other words a prime number is a is clearly a mathematical notion right it just involves asking you know when I factored this number do I get anything in between 1 and itself as a factor and that's a very mathematical notion what gödel showed was that being a theorem number is also a perfectly mathematical notion that is you begin with that you begin with by stating that a certain set of numbers are theorem numbers which ones are those the ones that stand for the axioms the axioms are all by definition theorem numbers that the axiom numbers are all theorem numbers and so you're just given those out right here's you're told these five or these ten whatever however many axioms there are these numbers are all theorem numbers and then you're given some formal rules that allow you to manipulate these numbers and from those numbers you can create new numbers that are big sometimes bigger and sometimes smaller but you will get new numbers those are called the theorem numbers and those numbers are just as mathematical as the ko lots numbers just as mathematical as the prime numbers just as mathematical as the Fibonacci numbers so what girdle was doing was bringing a discussion of proved ability into the domain of discourse that principia mathematica dealt with what is principia mathematica dealing with its dealing with statements about integers does this is this integer prime or not is this integer eco lots number or not is this integer a Fibonacci number is this integer a well-formed formula number all of these are mathematical questions is this integer a theorem number another mathematical question and yet in code it is saying is this particular theorem is this particular string a theorem or not if you ask if is this a theorem number you're saying effectively is this string a theorem of print capilla Mathematica or not and so despite the fact that Russell and Whitehead were under the illusion that self reference was not possible in their system girdle had snuck it in by the Trojan horse of gödel numbering because once you have numbers that are acting isomorphic Li to the structures in principia mathematica then you're able to talk about all the structures that bring capilla Mathematica numerically and so he was I'm not going to explain how he did this exactly but he was not only able to import the notion of theorem number into rinkeby mathematic into the system itself but also he was able to write down a very special string that expressed this following statement it was a particular particular integer G it said the integer G is not the number of a theorem is not the number is not a theorem number where a theorem number remember is just a mathematical notion be like saying the integer 641 is not prime which incidentally is false it is prime but that's not irrelevant it's just a mathematical statement the integer G is not the number of a theorem is not a theorem number however it turned out that the integer G was actually the exact number that correspond 'add to this string that expressed this statement so the G this is girdle's formula says this thing in the notation of principia mathematica it says G this lower case number this lower case letter G is not a theorem number so it says this number has a certain number theoretical property and it also says that by doing that it it says that the formula that it stands for is not a theorem but it happens that this formula is actually that exact statement so he actually created a statement that said about itself that it was not a theorem and that's what Marcus put up he said this theory this statement is not it's not provable so um I guess I just added this little thing these are the same assertion just understood in two different ways a certain number has a certain number theoretical property or a certain formula is not a theorem of principia mathematica identical statements I guess all I I see I've already done in effect well I didn't really because this is my last slide well let me just conclude then by mentioning the consequences are not the but some of the consequences of this construction because the construction creates a statement that speaks of itself which is the the thing that inspired such terror in Bertrand Russell's mind self reference to his mind was the source of all paradox and he had striven so hard to make sure that it was not a part of pink hippy Mathematica and girdle had actually brought it inside principia mathematica by this Trojan horse of gödel numbering now the statement that girdle created said of itself that it was not provable well it if it was uh let's let's think about that supposing that it was provable then it would be a false statement because it states that it is not provable but if it were provable then a false statement would be provable oh that seems horrible we don't want there to be any false statements provable that would be that would be the destruction of principle Mathematica nobody believed that or where any false statements will be provable so we have to go back and read Shakhtar assumption which was that it was provable so it's not a provable thing but that's what it says that's exactly what it says it says that it's not provable so it turns out that what it says is true and B precisely for that reason it is not provable it's like here's a pair of real paradox it's the exact reason that it is not provable is that it is true that's the exact opposite of what mathematicians like they think that they want prove ability and truth to be synonymous the exact reason that this string is not provable is that it is true very very strange and this construction that showed that there was a statement that was true but not provable in principia mathematica didn't apply only to principia mathematica it applied to any system of this structure it didn't depend on any of the details of principia mathematica zwey of the particular axioms that he used or the particular rules of inference that it used all it depended on was the idea that there was some axioms and some rules of inference and um and it showed that in any system that was rich enough to get the truths of number theory in it there were statements that were true and not provable and this would in you could then throw this in as a new axiom but that wouldn't hurt that wouldn't help anything because that's a new system that has a new set of axioms and you just apply the the godel prop procedure to that system which is a little larger and you've got another string which is which is not provable but true and you can keep on going forever and so there are an infinite number of holes and they can't be systematically all filled I guess the last thing I want to say is that it has been shown in the last few decades that although these number theoretical statements I mean girdle's statement says certain number has certain kind of property but it it seems like a very artificial kind of a property that is its it's constructed using this mapping that Goodall created and and and so forth and it might seem like it's such a very very esoteric kind of formula that even though that such things exist that they are very remote from anything in a mathematician would ever actually talk about but it's been shown that that's not the case at all and in fact John Conway and colleagues were able to show that there are if you consider the Co Lots problem as one of a family of problems that are all of that sort that basically involve multiplying or dividing integers and just going up and down in that way I'm not going to try to define the exact family but you can imagine it I mean the Cole that's the problem is often called the three n plus one problem and you can imagine a five n plus one problem or a five n plus two problem or something like that if you just consider all of those problems together it's been shown that there are problems of that sort that are undecidable for good alien reasons that is that the the girdle the girdle construction includes it you can you can prove that the girdle construction is equivalent to a Collatz problem of of some sort and so in fact that's a very very normal number theoretical kind of question it's not it's not something that seems obscure or strange or non mathematical or artificial it's a very natural mathematical kind of question it's also been shown that the Daiya fantine equations are there exist unsolvable Daiya undecidable diet die of fantine equations and those are equations of the basically the form some integers to some powers equal a set of sum of integers two powers equals another set of integers to sum of integers to powers it's it's a very very simple basic algebraic kind of equation and those two there exist ones that are undecidable so it turns out that as a result of as a consequence of girdles work that there are questions a very standard mathematical form that have been shown to be undecidable and so the undecidability doesn't just apply to very very weird remote regions but to very standard kinds of constructions and that's a really an astounding somewhat scary thought and with that I think I'll conclude