Gödel's Incompleteness Theorem: Formal Systems & Gödel Numbering

[00:00:00]this is the first part in a five-part series on gardels incompleteness theorem before we even really get discussing what the theorem is why it's interesting why it's important and all of that kind of thing we're going to have to introduce you to what are called formal systems rather than defining it or anything like that I've got an example right here it's directly taken from Douglas Hofstadter's book gorillas sure Bach and it does the job quite nicely for our purposes the name of that system is the mi u system systems are made out of what are called strings see here we've got a few strings of characters some of them are strengthened the mi u system some of them as you can see are not the only definition to limit what is a string of the mi u system is that it contains nothing but the characters M I and you si M is not a my 3 is not because they contain other characters I understand that we're starting out probably a little too simple but believe me understanding this is going to come in very handy later the next thing you'll notice is that some of them are called well formed strings some of them are not well formed in order to be a well formed string you need to start with the letter M and then after that the only characters you're allowed to use are you and I so M begins every well formed string and does not appear anywhere else we've got some not well formed strings here this one doesn't start with them this one does but it also has an M later on so that's no good and this one also does not start an M even though all three of these contain the right characters they are not well formed strings we won't be able to do anything with them so all we are really interested in are the well formed strings now what we're going to be doing is taking well formed strings and applying rules to them we'll get to this axiom in just a moment things you're allowed to do when a will form string ends in the character I that a blank space that means there's nothing that comes after it you can take that blank space and insert a you there so anytime something ends and I you can make it end in I you the next rule is that no matter what you have as long as this is a well formed string it will start with a little letter M and it'll contain something after it whatever the thing is that comes after the M you can double it I'll give some examples of that in a little bit if that may might be a little bit unclear third rule is that wherever you have three eyes in a row you can switch them out for you and finally when you have to use in a row you can remove them entirely now there's a certain set of well formed strings that are called theorems a theorem is any well formed string that begins with the axiom uses nothing but the rules on them and if you can get a well formed string as a result of nothing but the axiom and the rules then it is a theorem let's look at a nice little example of that alright here are some theorems there are infinitely many but you know whatever not everything's a theorem some things are only well formed strings but not theorems so star from the axiom which we've already been given and let's keep the rules handy just in case first thing we'll do is apply rule number two rule number two says that whatever comes after the M you can double it so we had M I we have M I I after using Rule two then let's use Rule two again we had M I I we double the I I and there's four of them and this is just an illustration to show that there are certainly infinitely many theorems since you can just keep doubling it as many times as you want and see we had four now we have eight and now that we've expanded it probably as much as we'll want to for our simple little purposes here let's start making it smaller again and if you look rule three takes three characters and turns them into one so that makes things shorter let's do that one since we have a whole bunch of eyes let's take three of them in charm into you doesn't matter which ones I chose these three right here so we used rule three and now we have em I you then four eyes hey why not let's do the same thing again we've got the M you have that first eye that we haven't done anything with and then we've got the u we had before those three eyes turn into another one and then there's one that we still haven't done anything with and then let's shorten it even further we have to use in a row since rule for us as we can just leave them off we just got the M the first eye and the other one that we haven't done anything with if you've been paying ten you will probably notice that we have ended up pretty close to back where we started that happens all the time in these kinds of things it's fine there's nothing wrong with it there's a whole bunch of ways to make every theorem and to finish this off let's just use the only rule we haven't which is actually rule number one anything that ends in an eye you can add a you to the end so we got something that ends in our eye let's add a u and where I think things start to get interesting is with the question is mu a theorem we certainly haven't proved it yet but they are infinite different things we can do for theorems you can try and find it out if you'd like I'll go ahead and tell you that you're probably not going to find it but frustratingly you might not be able to figure out a way to prove that it is not a theorem the fact that you're not really sure whether or not trying more and more uses of the rule is going to get you any closer or not it might just take 10,000 steps you're there's no way to know that for sure or it might be impossible and that kind of question is incredibly important to mathematicians they certainly want to know whether or not continuing to work on a problem is guaranteed to give them results or if they might not ever get results we're gonna be looking at one more system in this video but don't get too scared if that one was a little much for your brain to cut process all at once you might have noticed that we call the last system a type of graphical system and this one is not the difference is that now we'll be using our nothing but numbers instead of rules that we just gonna use mechanical processes on will do nothing but arithmetic though the system is gonna also use three symbols 3 1 & 0 the advantages of using these three symbols is that they're numbers so we can operate on them as we do any other number we'll want to know how we define well formed strings which they'll start with the number 3 and follow with only ones and zeros you're probably noticing a similarity between this one in the last system and yes you're right these two systems are going to function exactly the same as each other our axiom will be 31 and we'll have four rules as well and you'll notice that all we're doing is substituting Ms for 3s eyes four ones and use four zeros the rules however are going to be a little bit more complicated since all we're doing is arithmetic on them that really limits the amount of things we can do and a nice simple rule that we had in the mi u system where you add you to anything that ends in an I turns out looking like that numbers ending in one can be multiplied by ten okay that's not so bad however numbers ending in one searching for numbers ending in one is another type of graphical operation so unfortunately we'll need to get a little more specific here we have update rulz they look quite a bit more complicated but really they're pretty manageable once you get used to them you'll see that they all start with if we have followed by a kind of long and maybe confusing string of numbers and letters we can make and then a different good potentially confusing string of numbers and letters it's not too important that we understand exactly exactly what's going on but the point is that you can use the same rules instead of this sheet we're going with this one and set it m so we have threes and so on and what you'll get is exactly the same things we've already gone over this and if instead of the typographical system you want to use arithmetic here's the same exact thing just to get a better sense we're going to use one example we'll use going from the three one one one one two the three with eight ones and at the end of it I know it's simpler just to remember that anything after the three you double but in order to keep it purely mathematical here's what you got to do so the rules say that if we have three times ten to the M plus n we can make 10 to the M times 3 times 10 to the n plus n plus n what what on earth does that mean well if we look at the bottom we know that M and K are any old natural number we get to pick them and N is a natural number and you can use any of them as long as not greater than 10 to the M oh how on earth are we supposed to be able to tell if it fits into that form we know that since we're using rule number two it's going to apply to any well formed string since it did on the old system so if we're doing things right it should do the same thing on the new one and the trick for figuring out m and n for n all we do is take all of the numbers that aren't the three at the beginning and for em what we do is take how many digits it takes to get to the three at the beginning in this case M is going to be four n is going to be the four ones first let's make sure we're doing things right three times ten M plus n 3 times 10 what do we have for M 10 to the 4 plus n which is those 4 ones all right let's see 3 times 10 to the 4 is just 3 with 4 zeros after it plus 1 1 1 1 and then we get 3 1 1 1 1 that what we started with it sure is so that checks out and now what can we make we can make 10 M times 3 times 10 to the M plus n plus n so we got 10 to the 4 and since we know that in the parentheses all it is what we started with we'll just substitute the 3 1 1 1 in there plus n which we've already figured out so 10 to the 4 times that gives us that Plus that and there we go let's see if that did what we wanted it to we were going from here to here 3 with 4 ones 2 3 with 8 ones and that's exactly what we did now why are third we do all that turns out that no matter what your typographical system is you can do the same thing by substituting all of the characters or whatever with numbers any of these sets of rules you will be able to figure out one of these sets of rules and for any axiom you've got you'll be able to figure out a new axiom and that's all you need to make theorems that might not seem very important but trust me in a couple videos you'll see how that actually will kind of very much about math so I will hope to see you soon with the next part of this video thank you very much for watching