Diagonalisation Theorems and Logical Consequences in Arithmetic

[00:00:00]in this lesson we're gonna put the pieces together of everything that we've done so far to show that logic and theories of arithmetic are undecidable what step that we need to take to do this is to show how that we can convert facts about numbers to facts about formulas and to do this we'll use the idea of a girdle numbering this is something which is due to the logician Kurt gödel gödel numbering is a way of assigning natural numbers to expressions in the language of arithmetic so that these three criteria are satisfied different gödel numbers are assigned to different expressions the girdle number of a given expression can be calculated and it's effectively decidable or recursive to decide whether a girdle number is a godel number of an expression and if so what expression it happens to be the girl on that broth now lots of textbooks goes through defining a particular girdle numbering in detail I don't care about any of those details because basically we've invented a canonical girdle numbering now which is the thing called Unicode which is the way that formula the way that any kind of text of any kind is represented inside computers and computer networks and unicode expression you just type your formula in whatever your favorite word processing text editor thing is and just save it and see the internal representation in the computer of what that expression was that's just a number it's just a string of ones and zeroes which is a binary representation of a number and that representation satisfies all of the criteria of being a girdle numbering so that'll do for defining a godel numbering the important thing for us is that the girdle given any gödel numbering the godel number for a formula is a number and so in the language of arithmetic we've got a name for that number the numeral for that number so that means for any formula in our language call one eye there is a number in the language which kind of represents eye it's the code for I so will represent that not by writing out a big long number but just by writing the a with these funny-looking corner quotes there like a different kind of quotation mark which has become standard for the internal representation in the language of arithmetic for the formula I now you might think what a language has already got a representation of the formula i it's the formula a itself that's something that's in the language but that is something that is in the language as formula as a sentence as the kind of thing which is true or false whereas quotes i the internal representation the name of a is not itself a formula it's a name it's a particular numeral because i is a formula it makes sense to say if a then B that's another formula but if code say then B makes no more sense than if five then B those things aren't even sentences they don't make sense what we can say using gödel numbers is quotes I equals quotes B that's to say that a and B are the same sentence or we could even say something like quotes a is even because quotes a remember names a number and whether that number is even or odd is something we can ask so remember quotes a is a numerical term all it is is a zero followed by a large number of primes exactly how many depends on the formula a itself now remember we've used the technique of diagonalization twice once when we were looking at Cantor's theorem showing that bitstreams can't be enumerated and next when we were looking at the halting problem and we showed that the halting function cannot be encoded by any register machine in each of these cases we did something where we applied a number in two different ways we looked at the number for example of a bitstream in an enumeration and then we looked at the value of the bitstream that number of positions are long that was what makes a diagonal we did the same thing for a register machine in the halting problem we looked at the code of the register machine and then we saw we asked the question whether that register machine holds on that very input and we're gonna do exactly the same thing here except now we're going to look at a formula and we're going to see the formula the connection between that formula and it's good ol number now formulas don't have holes to plug things in unless they do unless they've got free variables so here given a formula with a free variable eggs so we pick out a particular free variable we'll use X the diagonalization of that formula is going to be this particular formula here there is an x such that x equals quod say and i now when i has the variable x free in it this is like the formula i holds all quotes i in fact it's a very easy deduction in logic to go from this formula to the diagonalization formula and back because if i holds of quote say that which our problem could say is just some number then there is something which is identical to that number such that i hold of it and on the other hand if there is something which is identical to that number there and i holds a bit then it must hold of course i because that's the only thing that is identical to quite say so that's just elementary logic to go in both directions there so you can get this kind of diagonalization picture where you think of the formulas listed one by one and you can think of that being applied to various things and the diagonal in this picture is applying this formula to its own girdle number so that might give you a hint of why this is called diagonalization let's have a look at how it works in concrete practice given a particular little formula what I've got here is the formula X plus zero equals zero and it's diagonalization is there is an X such that X equals N and X plus zero equals zero where n is whatever the girdle number is of X plus zero equals zero so it's just some longer formula and you can say that that is going to be logically equivalent to saying that n plus zero is zero now there's a bunch of new concepts here and some of them refer to things in the language and some of them refer to the things the language talks about namely numbers and it's important to get these straight in your head so here's a diagram that might help remember we've got the numerals the things in our language like zero with an underline and 0 with Prime's behind them and things like that which refer to particular numbers then there are the formulas in the language things like 2 plus 2 is 4 and all of the other kinds of formulas like we can make with our quantifiers and connectives and everything these are the kinds of things which are true or false in our models which follow from the axioms or don't follow from the axioms and those sorts of things these things are represented in our language or encoded by girdle numbers which are numbers and since these are numbers there are going to be numerals in the language which stand forth of them finally we use the connection between a and quad say to define the notion of the diagonalization of a formula now since the diagonalization is itself a formula it has a girdle number two and this relationship of diagonalization on the language side is paired up with a relationship on the numbers side for any number if that's the girdle number of a formula we can find another number which is the girdle number of the diagonal of that formula and that's a function from numbers to numbers at least four numbers which are girdle numbers our formulas we could define the girdle number of the diagonal of that formula and calculate that in terms of this original number that relationship is what we call the diagonal function given any number n die again is the girdle number of the diagonalization of the formula with godel number n if there is such a number and for the things which aren't our girdle numbers of formulas we just say the diag of those numbers is zero that's a function from numbers to numbers it's very easy to define so if n is the girdle number of X plus 0 equals 0 for example then diag of n is the godel number of this this formula there is an X such that x equals n and x plus 0 equals 0 diag turns out to be very easy to calculate here's how you do it you check if n is the godel number of a formula if it isn't return 0 and if it is you just add code dump the numbers in code for there is an X such that x equals a in and in the front of the block and then add the code for a right bracket at the back this is a recursive function and since it's a recursive function it can be represented in cubed by some formula so if we've returned to this diagram which shows what's on the language side of things and what's on the numbers side of things the I AG function which is represented here by this bright green arrow which takes us from a number to a number there's got to be an analogue of it over here on the language side so what we've got here is quite a complicated big jug with the language on the left in red and numbers on the right in green now actually on the right we've got two things we've got numbers in dark green and then we've got functions over there in bright green and then over there on the left hand side of the diagram in the language half in red up in the top we've got terms these are the kinds of things that named numbers while in the bottom we have formulas these are the kinds of things which had true or false now the things on the left are different kinds of things and the things on the right they're both you know abstract things but sentences and terms in our language are different things than numbers and functions on numbers the last thing to note is that there's different sorts of links between these two worlds the simplest is the reference or standing for relation where a name like 0 or 5 stands for the number 0 or 5 or the name 2 times 5 plus for that complex numerical term names 14 that's one relation between terms and numbers another relation is the relation between sentences and numbers and that's the girdle number of or the encoding relation you know the girdle number of the formula 2 plus 2 is 4 whatever big long number that is that encodes the sentence that 2 plus 2 is 4 and encodes other sentences it says mostly a relationship between numbers and sentences that's what we're interested in although there's another encoding relation between numbers and terms 2 because you know there's a girdle number for each of these other terms as well then there is the this representation relation between a sentence and our function that it represents and we could also have the defining relation between formulas and sets of numbers that are defined by those formulas we haven't put that in the diagram that's not so much room for that the other thing that's in this diagram is the diagonalization relation the diagonalization function which takes us from a sentence to another sentence so it's important to keep the differences here in mind so that you can see what different kinds of things are being defined so in particular let's go on with this formula that represents the diag function because we can do a lot with that in particular we can prove this following fact it's called a lemma the diagonalization lemma goes like this if I've got a theory like robinson's arithmetic or piano arithmetic in which the diag function is represented then for any formula B with a free variable Y there is some sentence G such that the theory proves that G and B of quotes G are equivalent to each other now this is a an incredibly powerful fact that we're going to do a lot with but before we do things with it let's explain why it's actually true we'll start off with this formula that represents the diag function in the theory take what this means is if diag of the number n is the number k then t can prove this for every Y I have and Y if and only if y equals K so this formula here with two free variables the first variable represents the input of the diag function in here and the second variable Y represents the output so we're going to be working with this formula B which has got the variable Y free in it and we're going to use that to define what this formula G is going to be we start off with this particular formula which we're going to call F it's the formula there's a Y such that I of x and Y and B Y I'll pause from them and think about what this formula f says it says there is some Y which is the diagonalization of X and B holds of it so this has got the variable Y free and it basically says be holds of the diagonalization of X so let n be the girdle number of that formula and then let G indeed be the diagonalization of this formula f so in other words G is this formula there is an X such that X equals N and F holds where n is the girdle number of F the first thing to note is that logic proves that G is equivalent there is a y such that I of N and Y and B Y is why G is this formula there is an X such that X equals N and F and that's equivalent to just plugging in and for X here so I'd get this formula there is a Y such that I XY and B Y and I just plug in the end for the X there it's there is a Y such that I am Y and B Y so logic tells us that now T proves that for every Y a NY if 95 cos K that's what it is for this formula - for the formula I to represent the diag function where K is a girdle number of the formula G so that's exactly what we need if K is a girl number of G we've got this so I and Y is going to be equivalent to y equals K so I can plug y equals K in here and get the T proves that Jesus equivalent to there is a while which is identical to K and B Y but that reduces to G is equivalent to B of K now what is K it is that girdle number of G it's the girdle number of G so T indeed proves that G is equivalent to B of check so that's the diagonalization them approved now we're going to step back and think about it for a bit because frankly that's incredible it's amazing it's a very very powerful result it tells us that any predicate in the theory like be without invariable free in it is has a kind of fixed point that is there's a sentence which is true if and only if that predicate holds of its girdle number you might have heard when people talk about things like the liar paradox strange sentences which say things like this very sentence is false now this is probably a paradoxical sentence because if it's true it's false if it's false it's true now this doesn't really have a lot to do with arithmetic as it stands because arithmetic doesn't have a predicate false we don't have a way in the language of arithmetic to describe the sentence as true or to describe the sentences false but more importantly arithmetic doesn't have a pronoun like this there's no way of getting a sentence to describe itself every sentence has got a girdle number and we've got a term for that girdle number but that term for the girdle number of a sentence is always going to be longer than the sentence itself so the sentence can't contain its own good or number but diagonalization allows us to get very close to this so don't think of the predicate is true or is false just imagine we have some property that a sentence might have like B with the variable Y indicating what it's describing so B of 1 means that the object 1 is got property B and B of 5 since the object 5 does it cetera well the diagonalization lemma says that there is some sentence J which according to the theory of arithmetic that we're using G is equivalent to B of quotes J that means that what the sentence G says is true if and only if the sentence G has got property Bey that means you can think of the sentence as making the claim that that very sentence has property Bey and that is something that we can do so we're going to start rolling out the consequences of the diagonalization memo from define ability to what we can define in our languages to the fact that these theories are going to be undecidable now remember we said that a set of numbers is definable by a formula B in the theory T if and only if the theory proves be avenged just when for number n is in the set and it proves not B then if and only if the numbers not inside so here's our first consequence I've got a theory and it's consistent can't be inconsistent and it's at least as strong as Q then the set of things that the theory can prove the theorem subt a I mean that girdle numbers of those theorems is not definable in the theory T itself is what suppose we did have some formula which defines the set of girdle numbers of theorems of that theory well the diagonalization lemma tells us that there is a formula G which is equivalent to not say of J so here we're applying diagonalization on the predicate not say and that's exactly the same kind of thing we do with diagonalization before when we were flipping the bits in bitstreams we were changing 1 to 0 0 to 1 we're doing exactly the same thing here we are inserting this negation which is doing all the work we can ask ourselves the question for this formula J does the theory prove it or not well if the theory proves it then according to this equivalence T's gotta prove not C of J and then since C defines the theorems of T that means T can't prove G because C of G is meant to represent the idea that Jesus indeed a theorem so T can't prove G because this is a consistent theory if tea doesn't prove J then tea doesn't prove not C of G because the theory is consistent and since C defines all the theorems of tea tea indeed proves G now this is of course a contradiction we've proved that if tea proves G it doesn't and if tea doesn't prove G it does so we've got an inconsistency here which means that there is no such predicate C which defines the set of all theorems the set of all theorems of this theory cannot be defined inside the theory itself but remember the recursive functions are the things which are representable in the theory and the recursive sets are the things which are definable so in this theory the set of all theorems isn't definable so it immediately follows from that that if I've got a consistent theory at least as strong as Q the set of theorems of that theory is not recursive that is being a theorem of T is not decidable we've shown that Robinson's arithmetic and any stronger consistent theory like piano arithmetic is undecidable there is no algorithm for determining whether or not something is a theorem of the theory we thought that was probably gonna be the case because arithmetic is kinda complicated but now we know our inability to find an algorithm for proving exactly the theorems of arithmetic and refuting exactly the non theorems we now know that we're never gonna find such an algorithm any function which does that is not recursive so this is a really powerful imitative result it's our first undecidability result concerning a logical theory an immediate consequence of this is that any consistent deductively defined extension of Robinson's arithmetic has to be incomplete to here's why if I had a consistent deductively defined extension of Robinson's arithmetic call it a since it's an extension of Q it doesn't represent its own set serums so but since it's an extension of cue it does represent all the cursive seds so the set of serums of tea is not recursive we know that but if T were complete since its deductively defined it would be decidable because its theorems would be a recursive set because remember complete deductively defined theories we put that algorithm since its theorems are recursively enumerable if it's consistent and complete we could just check the theorem says they get generated white for whether i or its negation is generated and that would give us an algorithm to decide membership of the theory so since this theory is undecidable its theorems is not it's set of theorems is not recursive that means it's also incomplete any axiomatic deductively defined extension of Q has got to have gaps in it so this is our first hint or our first proof that piano rithmetic is also incomplete because it is deductively defined it's just the little finite set of seven Robinson's arithmetic axioms plus all of the axioms of induction but that's it's recursively decidable whether or not a formula is an instance of induction and so this is a deductively defined extension of Q to some piano Resnick's gotta have gaps in it as well we haven't filled in all the incompleteness by adding those induction axioms so there we've shown that q and a bunch of extensions of it are incomplete and undecidable now we're gonna not go up from Q we're gonna go down to logic itself the set of serums of predicate logic is also undecidable suppose we had a way to decide if a formula is valid as a tautology in the language of predicate logic then if we knew how to do that we'd also be able to decide whether or not something was a theorem of Robinson's arithmetic because you just check if this sentence I if you want to check if this sentence I use the theorem of Robinson's arithmetic you just check if logic alone proves this formula Q 1 and Q 2 and Q 3 and Q 4 q5 and q6 mq7 implies I that is a theorem of logic its tautology if and only if I follows from the axioms of Robinson's arithmetic but there's no way to decide recursively if something is a theorem of Q so there's no way to decide if a formula is a tautology in the language of predicate logic so if logic itself is undecidable as well so we've got that Robinsons arithmetic and piano arithmetic and other a consistent extensions which are deductively defined are all undecidable and incomplete we've got that logic is undecidable it's also incomplete but that was obvious you know P and not P logic doesn't decide between those what about going up even further that what about true arithmetic that is a theory it's consistent and it's complain it's the set of all formulas that are true in the standard model operation attack what can we learn about that what since it's determined by a single model it's complete since true arithmetic is complete it can't be deductively defined that's just modus tollens for the modus ponens that we've done before now since true arithmetic is an extension of Q it's not decidable it doesn't represent its own theorems and it does represent all recursive sets this is what's called task ease in define ability theorem this is the result which says there the truths of arithmetic cannot be defined by recursive function so let's sum up what we've proved so far any consistent extension of Q cannot define the set of its own theorems that was the first thing that we proved using diagonalization now we also know that only consistent extension of Q can define all of the recursive said so I'm going to put these two together which says that any set of theorems of any consistent extension of Q cannot be recursive so any complete and consistent deductively defined theory does have a recursive set of theorems that's that algorithm I was telling you just since its recursively enumerable if it's consistent and complete that makes it recursive so any consistent deductively defined extension of Q's got to be incomplete putting 3 & 4 together now if the set of theorems of predicate logic is recursive so is Q that's just a fact that Q is finitely at CIMMYT honest so any problem about whether or not something's in the theory of Q can be reduced to a problem of whether or not a particular formula is logically valid it follows from that the predicate logic is undecidable that's 3 & 6 together now true arithmetic the set of senses true in the standard model since it's a consistent extension of Q is not deductively defined that is a consequence of 5 then it follows from that that truth in the standard model of arithmetic is not recursive and in fact it's not even recursively enumerable so that's a massive load of consequences that we've all churned out these are an amazing family of limited results we're going to extend this in our last lesson next week where we're going to look at answering the specific questions we know that Q and P a and these theories of arithmetic are incomplete we know they've got to be incomplete but just like when we were looking at recursive functions it's one thing to know that there are non recursive functions it's another thing to know some examples of them well we already know why Q is incomplete we've already seen that for example for every X for every Y X plus y equals y plus X can't be proved and neither can its negation but piano rithmetic isn't like that piano arithmetic can prove that addition is commutative and if that piano is that it can prove a huge number of true arithmetic claims it's an import issue where is it that piano ResNet ik is incomplete in fact is there a why and we'll say next week that there is a why of for any theory like this pinpointing what it is that it can't prove and this will give us a greater insight into the kinds of limits of logical theories but that's our topic for next week