Gödel Numbers Explained: Arithmetization & Substitution

[00:00:01]welcome back to cares.org today we're welcome back to cares.org today we're welcome back to cares.org today we're going to be continuing with our series going to be continuing with our series going to be continuing with our series you can't handle the truth in this video you can't handle the truth in this video you can't handle the truth in this video we are also continuing with Alfred we are also continuing with Alfred we are also continuing with Alfred tarski's theory of Truth our minseries tarski's theory of Truth our minseries tarski's theory of Truth our minseries within the series on that but unlike we within the series on that but unlike we within the series on that but unlike we said in the last video where we said we said in the last video where we said we said in the last video where we said we were going to be talking about the were going to be talking about the were going to be talking about the indefinability of Truth next we are indefinability of Truth next we are indefinability of Truth next we are going to take a little step in between going to take a little step in between going to take a little step in between to look at a dumb founding definition to look at a dumb founding definition to look at a dumb founding definition dising distinction and diabolical dising distinction and diabolical dising distinction and diabolical Doctrine being what is a a girdle number Doctrine being what is a a girdle number Doctrine being what is a a girdle number so girdle used a numbering system to so girdle used a numbering system to so girdle used a numbering system to translate particular propositions into translate particular propositions into translate particular propositions into numbers for his proof of the numbers for his proof of the numbers for his proof of the incompleteness theorems tarski uses the incompleteness theorems tarski uses the incompleteness theorems tarski uses the same system or a similar system to prove same system or a similar system to prove same system or a similar system to prove the indefinability of Truth so we're the indefinability of Truth so we're the indefinability of Truth so we're going to take a brief look at that here going to take a brief look at that here going to take a brief look at that here so in order to get to tarski's proof of so in order to get to tarski's proof of so in order to get to tarski's proof of indefinability there are a few tools we indefinability there are a few tools we indefinability there are a few tools we will need girdle numbers free variables will need girdle numbers free variables will need girdle numbers free variables arithmetization arithmetization arithmetization substitutions and a process that Douglas substitutions and a process that Douglas substitutions and a process that Douglas hoffstad the author of gerbach calls hoffstad the author of gerbach calls hoffstad the author of gerbach calls arithm coining after Quin with these arithm coining after Quin with these arithm coining after Quin with these tools we will be able to show that truth tools we will be able to show that truth tools we will be able to show that truth cannot be defined within any particular cannot be defined within any particular cannot be defined within any particular language it can be defined from an language it can be defined from an language it can be defined from an outside meta language but within a outside meta language but within a outside meta language but within a language we cannot offer a definition of language we cannot offer a definition of language we cannot offer a definition of truth because we're going to violate truth because we're going to violate truth because we're going to violate convention t now in the proof of girdle's now in the proof of girdle's now in the proof of girdle's incompleteness theorem girdle creates a incompleteness theorem girdle creates a incompleteness theorem girdle creates a numbering scheme which translates the numbering scheme which translates the numbering scheme which translates the strings of a particular language into strings of a particular language into strings of a particular language into unique numbers each of the elements of unique numbers each of the elements of unique numbers each of the elements of the alphabet are assigned a particular the alphabet are assigned a particular the alphabet are assigned a particular number then the numbers representing the number then the numbers representing the number then the numbers representing the symbols in the string are placed end to symbols in the string are placed end to symbols in the string are placed end to end to create one larger number this end to create one larger number this end to create one larger number this makes it so that every formula has a makes it so that every formula has a makes it so that every formula has a unique girdle number and every unique unique girdle number and every unique unique girdle number and every unique girdle number if translated correctly is girdle number if translated correctly is girdle number if translated correctly is going to have a formula it can be going to have a formula it can be going to have a formula it can be translated into and you can have a translated into and you can have a translated into and you can have a function or just a relation that function or just a relation that function or just a relation that translates back and forth between them translates back and forth between them translates back and forth between them it's also interesting something we won't it's also interesting something we won't it's also interesting something we won't get to here is that are then get to here is that are then get to here is that are then typographical rules of proofs so that typographical rules of proofs so that typographical rules of proofs so that you can prove this line from this line you can prove this line from this line you can prove this line from this line or this line from this line can actually or this line from this line can actually or this line from this line can actually be then translated into arithmetic rules be then translated into arithmetic rules be then translated into arithmetic rules which say you can multiply by 100 and which say you can multiply by 100 and which say you can multiply by 100 and add 123 to a particular string okay so add 123 to a particular string okay so add 123 to a particular string okay so we're not going to get into those we're not going to get into those we're not going to get into those translations here yet but we are going translations here yet but we are going translations here yet but we are going to cover the basics of girdle numbers so to cover the basics of girdle numbers so to cover the basics of girdle numbers so if we take the definitions for the side if we take the definitions for the side if we take the definitions for the side we can translate some basic strings into we can translate some basic strings into we can translate some basic strings into girdle numbers for example TP the girdle numbers for example TP the girdle numbers for example TP the predicate t t being prefaced over the predicate t t being prefaced over the predicate t t being prefaced over the proposition P could be translated as 777 proposition P could be translated as 777 proposition P could be translated as 777 2 32999 2 32999 2 32999 323 because the 777 represents the T as 323 because the 777 represents the T as 323 because the 777 represents the T as you see on the side we have 777 equals T you see on the side we have 777 equals T you see on the side we have 777 equals T the 232 is the open parentheses the 999 the 232 is the open parentheses the 999 the 232 is the open parentheses the 999 is the p and the 323 is the closed is the p and the 323 is the closed is the p and the 323 is the closed parentheses we put the commas in between parentheses we put the commas in between parentheses we put the commas in between not only because it's the standard not only because it's the standard not only because it's the standard Convention of writing really large Convention of writing really large Convention of writing really large numbers you put a comma every three numbers you put a comma every three numbers you put a comma every three digits but also because by doing that we digits but also because by doing that we digits but also because by doing that we can very clearly see which set of can very clearly see which set of can very clearly see which set of numbers represents which numbers represents which numbers represents which letter we could also translate this letter we could also translate this letter we could also translate this little bit more complicated statement little bit more complicated statement little bit more complicated statement for all p and all q p or q and not Q for all p and all q p or q and not Q for all p and all q p or q and not Q implies P basically a statement of implies P basically a statement of implies P basically a statement of the rule of destructive syllogism we can the rule of destructive syllogism we can the rule of destructive syllogism we can translate that as this really long translate that as this really long translate that as this really long number I encourage you to go through the number I encourage you to go through the number I encourage you to go through the number see if I made any mistakes in number see if I made any mistakes in number see if I made any mistakes in there but I'm pretty sure it's basically there but I'm pretty sure it's basically there but I'm pretty sure it's basically correct we have 2 32 representing the correct we have 2 32 representing the correct we have 2 32 representing the Open Bracket 111 representing the Open Bracket 111 representing the Open Bracket 111 representing the universal quantifier 999 being p and so universal quantifier 999 being p and so universal quantifier 999 being p and so on and so forth okay hopefully that on and so forth okay hopefully that on and so forth okay hopefully that makes sense for a basic understanding of makes sense for a basic understanding of makes sense for a basic understanding of what we mean by translating girdle what we mean by translating girdle what we mean by translating girdle numbers into propositions and numbers into propositions and numbers into propositions and propositions back into girdle propositions back into girdle propositions back into girdle numbers at some point we're going to numbers at some point we're going to numbers at some point we're going to learn about a method for representing learn about a method for representing learn about a method for representing numbers in logic known as successorship numbers in logic known as successorship numbers in logic known as successorship but for now we're going to take each of but for now we're going to take each of but for now we're going to take each of the 10 digits as separate symbols just the 10 digits as separate symbols just the 10 digits as separate symbols just to keep things to keep things to keep things simple now there's a great deal that can simple now there's a great deal that can simple now there's a great deal that can be done with girdle numbers from this be done with girdle numbers from this be done with girdle numbers from this point we can as I said translate all of point we can as I said translate all of point we can as I said translate all of our rules of propositional calculus into our rules of propositional calculus into our rules of propositional calculus into rules about arithmetic and even go on to rules about arithmetic and even go on to rules about arithmetic and even go on to prove girdle's theorem in a future video prove girdle's theorem in a future video prove girdle's theorem in a future video we may look at these ramifications but we may look at these ramifications but we may look at these ramifications but for now we're just going to use them to for now we're just going to use them to for now we're just going to use them to understand these other relations and understand these other relations and understand these other relations and these other tools that we have I have these other tools that we have I have these other tools that we have I have done a video on girdle's incompleteness done a video on girdle's incompleteness done a video on girdle's incompleteness theorem which is a Basics video at some theorem which is a Basics video at some theorem which is a Basics video at some point hopefully we will do a full series point hopefully we will do a full series point hopefully we will do a full series really delving into and digging into how really delving into and digging into how really delving into and digging into how girdle proves those theorems using some girdle proves those theorems using some girdle proves those theorems using some of these really interesting of these really interesting of these really interesting methods now the next tool we're going to methods now the next tool we're going to methods now the next tool we're going to use is known as a free variable free use is known as a free variable free use is known as a free variable free variables are something we've covered variables are something we've covered variables are something we've covered before but just as a review they're before but just as a review they're before but just as a review they're variables p q n m Etc in formulas which variables p q n m Etc in formulas which variables p q n m Etc in formulas which are not under a quantifier that means are not under a quantifier that means are not under a quantifier that means that they don't have a quantifier next that they don't have a quantifier next that they don't have a quantifier next to them the beginning or at any point in to them the beginning or at any point in to them the beginning or at any point in the statement so variables are under a the statement so variables are under a the statement so variables are under a quantifier then they're called bound quantifier then they're called bound quantifier then they're called bound variables variables can represent both variables variables can represent both variables variables can represent both propositions and numbers now that we're propositions and numbers now that we're propositions and numbers now that we're introducing kind of numbers very introducing kind of numbers very introducing kind of numbers very basically into our propositional basically into our propositional basically into our propositional calculus we'll use variables like n and calculus we'll use variables like n and calculus we'll use variables like n and M to represent numbers and in this case M to represent numbers and in this case M to represent numbers and in this case they're going to just be girdle numbers they're going to just be girdle numbers they're going to just be girdle numbers we'll use variables like P and Q to we'll use variables like P and Q to we'll use variables like P and Q to represent propositions for example in represent propositions for example in represent propositions for example in the following formula p and N are bound the following formula p and N are bound the following formula p and N are bound variables while q and M are free variables while q and M are free variables while q and M are free variables so look at this carefully at variables so look at this carefully at variables so look at this carefully at the beginning of the statement we have the beginning of the statement we have the beginning of the statement we have for all P there exists some for all P there exists some for all P there exists some n such that and we continue on P and Q n such that and we continue on P and Q n such that and we continue on P and Q you note that P was bound at the you note that P was bound at the you note that P was bound at the beginning by a universal quantifier but beginning by a universal quantifier but beginning by a universal quantifier but Q was not we didn't have a for all Q or Q was not we didn't have a for all Q or Q was not we didn't have a for all Q or there exists a q at the beginning so Q there exists a q at the beginning so Q there exists a q at the beginning so Q is free while p is bound is free while p is bound is free while p is bound or a n implies a or a n implies a or a n implies a m so on and so forth so it should be m so on and so forth so it should be m so on and so forth so it should be clear that that n is Quantified by the clear that that n is Quantified by the clear that that n is Quantified by the existential quantifier at the beginning existential quantifier at the beginning existential quantifier at the beginning so n is bound M doesn't have any so n is bound M doesn't have any so n is bound M doesn't have any quantifiers so m is quantifiers so m is quantifiers so m is free hopefully you understand that we free hopefully you understand that we free hopefully you understand that we talk a little bit about free variables talk a little bit about free variables talk a little bit about free variables in the final 10 days of the first one in the final 10 days of the first one in the final 10 days of the first one 100 days of logic check those videos out 100 days of logic check those videos out 100 days of logic check those videos out if you're a little confused but if you're a little confused but if you're a little confused but hopefully this is pretty intuitive if hopefully this is pretty intuitive if hopefully this is pretty intuitive if you have a basic understanding of you have a basic understanding of you have a basic understanding of propositional propositional propositional calculus now next up we have calculus now next up we have calculus now next up we have arithmetization the third tool we'll arithmetization the third tool we'll arithmetization the third tool we'll need to learn about is arithmetization need to learn about is arithmetization need to learn about is arithmetization this is a relation between a number and this is a relation between a number and this is a relation between a number and a proposition remember relations are two a proposition remember relations are two a proposition remember relations are two part predicates or predicates that take part predicates or predicates that take part predicates or predicates that take two two two things as their constituent part so things as their constituent part so things as their constituent part so we'll rep represent it with a open we'll rep represent it with a open we'll rep represent it with a open parentheses n comma P close parenes it's parentheses n comma P close parenes it's parentheses n comma P close parenes it's always going to be a number first and a always going to be a number first and a always going to be a number first and a proposition second and we'll translate proposition second and we'll translate proposition second and we'll translate it as p is the translation of the girdle it as p is the translation of the girdle it as p is the translation of the girdle number n for example number n for example number n for example a 155 55555 comma m equals m is true since 55555 comma m equals m is true since 55555 comma m equals m is true since under the definitions we've offered 155 under the definitions we've offered 155 under the definitions we've offered 155 5551 155 translates to m equals m okay 5551 155 translates to m equals m okay 5551 155 translates to m equals m okay so if you were to plug in some number so if you were to plug in some number so if you were to plug in some number that was not a girdle number or was not that was not a girdle number or was not that was not a girdle number or was not the correct girdle number for a the correct girdle number for a the correct girdle number for a proposition that would just make this proposition that would just make this proposition that would just make this whole predicate false it would say that whole predicate false it would say that whole predicate false it would say that this relation does not apply between this relation does not apply between this relation does not apply between this predicate and this proposition the this predicate and this proposition the this predicate and this proposition the important thing to note here is this important thing to note here is this important thing to note here is this isn't some action or new type of thing isn't some action or new type of thing isn't some action or new type of thing for our predicate calculus it's just a for our predicate calculus it's just a for our predicate calculus it's just a relation the same way that you could say relation the same way that you could say relation the same way that you could say that something is to the left of that something is to the left of that something is to the left of something else we're not moving something else we're not moving something else we're not moving something to the left of it we're not something to the left of it we're not something to the left of it we're not actually doing the action of translating actually doing the action of translating actually doing the action of translating something into something else we're something into something else we're something into something else we're simply stating that these two things simply stating that these two things simply stating that these two things bear that relation to each bear that relation to each bear that relation to each other hopefully that makes sense but if other hopefully that makes sense but if other hopefully that makes sense but if it doesn't let's look at some examples it doesn't let's look at some examples it doesn't let's look at some examples so here's a very clear example of how we so here's a very clear example of how we so here's a very clear example of how we could arithmetization does is Express that a arithmetization does is Express that a arithmetization does is Express that a particular particular particular number and the correct translation of number and the correct translation of number and the correct translation of that particular number bear that particular number bear that particular number bear a relation to each other namely the a relation to each other namely the a relation to each other namely the arithmetization arithmetization arithmetization relation okay so the fourth tool that we relation okay so the fourth tool that we relation okay so the fourth tool that we will need is another relation called will need is another relation called will need is another relation called substitution and this is probably the substitution and this is probably the substitution and this is probably the most complicated of the tools arithm most complicated of the tools arithm most complicated of the tools arithm coining gets a little more complicated coining gets a little more complicated coining gets a little more complicated but only because it involves but only because it involves but only because it involves substitution this is going to hold substitution this is going to hold substitution this is going to hold between ordered sets of three girdled between ordered sets of three girdled between ordered sets of three girdled numbers basically it claims that if you numbers basically it claims that if you numbers basically it claims that if you take the first girdle number take the first girdle number take the first girdle number arithmetization equation then arithmetization Ln M where l n and M are arithmetization Ln M where l n and M are arithmetization Ln M where l n and M are all numbers okay this might be a little all numbers okay this might be a little all numbers okay this might be a little confusing but to clarify let's take a confusing but to clarify let's take a confusing but to clarify let's take a look at an example so to be clear some look at an example so to be clear some look at an example so to be clear some three numbers Ln M bear the substitution three numbers Ln M bear the substitution three numbers Ln M bear the substitution relation to each other if and only if relation to each other if and only if relation to each other if and only if the arithmetization of m is identical to the arithmetization of m is identical to the arithmetization of m is identical to the arithmetization of L but with all of the arithmetization of L but with all of the arithmetization of L but with all of the free variables in L having been the free variables in L having been the free variables in L having been replaced by n not the arithmetization of replaced by n not the arithmetization of replaced by n not the arithmetization of n but n n but n n but n itself okay hopefully that makes sense itself okay hopefully that makes sense itself okay hopefully that makes sense but if not here's an example it's a but if not here's an example it's a but if not here's an example it's a little complicated and there's a lot of little complicated and there's a lot of little complicated and there's a lot of numbers but trust me it's going to make numbers but trust me it's going to make numbers but trust me it's going to make sense so we have S and we have three sense so we have S and we have three sense so we have S and we have three numbers Each of which is on a separate numbers Each of which is on a separate numbers Each of which is on a separate line and I've put spaces and commas in line and I've put spaces and commas in line and I've put spaces and commas in between to distinguish between just the between to distinguish between just the between to distinguish between just the normal commas between the numbers so we normal commas between the numbers so we normal commas between the numbers so we have this first long string comma this have this first long string comma this have this first long string comma this second really kind of short string and second really kind of short string and second really kind of short string and this third really long string that goes this third really long string that goes this third really long string that goes onto two lines and this would be true onto two lines and this would be true onto two lines and this would be true why because the first number translates why because the first number translates why because the first number translates into if you translate each of those into if you translate each of those into if you translate each of those things in that first line where the S is things in that first line where the S is things in that first line where the S is into there exists some P such that n is into there exists some P such that n is into there exists some P such that n is the arithmetization of the arithmetization of the arithmetization of P the second number translates to Q or P the second number translates to Q or P the second number translates to Q or not q and the third translates to there not q and the third translates to there not q and the third translates to there exists some P such that that's the exists some P such that that's the exists some P such that that's the arithmetization of that second number is arithmetization of that second number is arithmetization of that second number is p hopefully you can see the reason we p hopefully you can see the reason we p hopefully you can see the reason we have all of those eights in that third have all of those eights in that third have all of those eights in that third numbers because we're actually numbers because we're actually numbers because we're actually representing each of those numbers in representing each of those numbers in representing each of those numbers in that that that statement as you can see what what we statement as you can see what what we statement as you can see what what we did was we substituted the second number did was we substituted the second number did was we substituted the second number in for the free variable in the first in for the free variable in the first in for the free variable in the first Formula which was n to get the third one Formula which was n to get the third one Formula which was n to get the third one the third number and the third number the third number and the third number the third number and the third number was just the arithmetization was just the arithmetization was just the arithmetization of that of that of that proposition it's important to note that proposition it's important to note that proposition it's important to note that this doesn't have to be true so this this doesn't have to be true so this this doesn't have to be true so this does seem to happen to be a true does seem to happen to be a true does seem to happen to be a true statement there exists some such that statement there exists some such that statement there exists some such that this it's a proposition I that 66691 this it's a proposition I that 66691 this it's a proposition I that 66691 9100 9100 9100 666 can be translated into namely Q or 666 can be translated into namely Q or 666 can be translated into namely Q or not q but that third number or that not q but that third number or that not q but that third number or that third arithmetization doesn't need to be third arithmetization doesn't need to be third arithmetization doesn't need to be true for the substitution relation to true for the substitution relation to true for the substitution relation to hold what needs to be the case is that hold what needs to be the case is that hold what needs to be the case is that if you plug in the second number into if you plug in the second number into if you plug in the second number into all of the free variable slots in the all of the free variable slots in the all of the free variable slots in the first number you will get the third first number you will get the third first number you will get the third number that's what needs to be true it number that's what needs to be true it number that's what needs to be true it doesn't need to be the case that the doesn't need to be the case that the doesn't need to be the case that the third number represents a proposition third number represents a proposition third number represents a proposition that is actually that is actually that is actually true hopefully that makes true hopefully that makes true hopefully that makes sense all right the final tool we're sense all right the final tool we're sense all right the final tool we're going to learn about will combine all of going to learn about will combine all of going to learn about will combine all of the tools we've learned so far arithma the tools we've learned so far arithma the tools we've learned so far arithma quiz is a relation between two girdle quiz is a relation between two girdle quiz is a relation between two girdle numbers it claims if we take the first numbers it claims if we take the first numbers it claims if we take the first girdle number in the relation turn it girdle number in the relation turn it girdle number in the relation turn it into an equation a formula a string and into an equation a formula a string and into an equation a formula a string and then plug that that first girdle number then plug that that first girdle number then plug that that first girdle number the same girdle number we just turned the same girdle number we just turned the same girdle number we just turned into a formula in for all of the into a formula in for all of the into a formula in for all of the instances of a free variable in that instances of a free variable in that instances of a free variable in that equation then the girdle number of that equation then the girdle number of that equation then the girdle number of that equation or formula is the second girdle equation or formula is the second girdle equation or formula is the second girdle number so if the second girdle number in number so if the second girdle number in number so if the second girdle number in the relation is this new girdle number the relation is this new girdle number the relation is this new girdle number the relation is true if not it is false the relation is true if not it is false the relation is true if not it is false we're going to represent this relation we're going to represent this relation we're going to represent this relation with with with qn m qn m qn m okay now if you're paying attention and okay now if you're paying attention and okay now if you're paying attention and you have a good understanding of you have a good understanding of you have a good understanding of substitution you should be able to see substitution you should be able to see substitution you should be able to see that arithm coining is just substitution that arithm coining is just substitution that arithm coining is just substitution where the first two numbers are the same where the first two numbers are the same where the first two numbers are the same or in other words we could Define q&m as or in other words we could Define q&m as or in other words we could Define q&m as snnm so if you're having trouble with snnm so if you're having trouble with snnm so if you're having trouble with arithma whining go back to arithma whining go back to arithma whining go back to substitution practice it understand it substitution practice it understand it substitution practice it understand it and then just use the first number twice and then just use the first number twice and then just use the first number twice to get to get to get what arithm whining is what that what arithm whining is what that what arithm whining is what that relation relation relation is all of these methods will be what is all of these methods will be what is all of these methods will be what tarski uses to prove that is impossible tarski uses to prove that is impossible tarski uses to prove that is impossible to Define Truth for a language within to Define Truth for a language within to Define Truth for a language within that language and rigorously prove that that language and rigorously prove that that language and rigorously prove that the Liar's Paradox makes Truth the Liar's Paradox makes Truth the Liar's Paradox makes Truth indefinable at least within a indefinable at least within a indefinable at least within a language that was what is a girdle language that was what is a girdle language that was what is a girdle number next time we will actually be number next time we will actually be number next time we will actually be doing the indefinability of Truth watch doing the indefinability of Truth watch doing the indefinability of Truth watch this video and more here at cares.org this video and more here at cares.org this video and more here at cares.org and stay skeptical everybody