Diagonalisation Lemma & Representability in Q | Logic Lecture 28

[00:00:01]in the last lecture we used the property of of the diagonalization of a formula to achieve some kind of sort of self-reference right and we use that to derive taskies theorem on the undefinability of truth that said that there was no formula which was true of precisely those numbers which were girdle numbers of true statements in arithmetic so there was no shortcut or royal road to finding out what the truths of arithmetic are solving the riemann hypothesis doing whatever right simply by plugging in the code of that formula and seeing to some other super formula and seeing if that was true so what girl did was do a as it were a syntactic probability version of this so tarsky is all about you know semantics it's about what's true in arithmetic what girdle was after was about what's provable from a set of axioms so we he wants to use the same kind of self-reference trick that went on in the tarsky argument but not about talking about what comes out to be true in n but actually what's provable in q or in axiom systems that are like cured extended in some kind of algorithmic way so we're going to go back and look at this very simple system queue here which is in section 6.2 and we're just going to point out some of the features and we're not going to do everything that's here in this section so let's look at 6 2 then and see what it's got so 6 2 is so the axiom system q revisited so again this is a little bit about you know what's provable in the theory q and if we had more time we'd actually do some proofs in this system q but as it is we'll just look and see what's what's there rather than actually concentrating on that the actual proofs themselves so q you recall was a just one collection of finite number of axioms and what can we prove from those axioms well to see what example 6 16 says okay from the axioms of q we can prove that one is different from two so this is my way of bold facing the letters there right so recall here this is just a successor of zero and two of course is the double successor of zero so actually what this is saying perhaps more formally is not this here now the axioms of q say certain things they don't explicitly say that the successor of one thing is different here the successor of something else so we can actually prove this here in queue and if you look there at the actual proof itself again as i said i don't particularly want to go through this is here's actually how you would do it you would take certain two axioms from q and we do some predicate calculus proof on those axioms and we'd end up here right in the end getting some proof from q of zero doesn't equal one and then the reference to another lemma then says this means that q proves that one is not two okay so if i've got two objects that are different and i apply the successor function to them i get two different objects but anyway how this comes about is not particularly of interest to us but the result actually is that q is a strong enough set of axioms to prove that one is different from two but also it can prove our standard arithmetical facts q can prove that two plus two equals four right so this of course is the the answer to all those kind of annoying people at parties is ask you know how do we really know that two plus two equals four well this the eight lines there on page 96 that tells them right so two plus two equals four so again what we'd be doing here is this is really saying this so in general and we can prove simple statements like this in queue of the kind that we think are kind of obvious so in section 621 6.21 sorry this is called arithmetical results in q there's a kind again it's a library of results here is built up right and it's interesting to see actually what you can't prove in q we can actually prove from q rather we cannot prove from q that every number is different from its successor now this might look very strange at first right well we can prove the natural numbers are different from their successes but this string turns out not to be provable from q and how one establishes it is by finding a structure in which q is true and in which this is false and then appealing to the completeness theorem so we'd know we couldn't couldn't prove this this from q of course the structure in which q together with a negative together with this sorry together with this here it would have to have something in it who's some object in it which was its own successor so you take something to look like national numbers and you throw in some kind of infinity or something like this but again we're not going to bother about this it's done there in the text an example of a structure extending the natural numbers but we shan't we shall need this using some structure and i think it's called n double star in the notes right um sorry n star with an extra point or an extra number if you like let's call it infinity with infinity prime equals infinity and we can find n star all the other axioms of q are true but also the negation of this we have that q is true but anyway this is by the way this is not going to affect us later on but it's to say that the axiom system is um it's strong enough what we want to do but it's a rather weak system because it can't prove certain things that we we think of as obvious about the natural numbers 619 again gives us some things that aren't theorems but let's skip that let's just look at what we can do so we can do enough in q if m equals n and q will prove that the term here zero followed by m primes is the same as the term zero followed by n primes but if m is different from m then q will prove these terms are different so it's kind of a little bit adequate like this if i plus j equals k then q can prove i plus j equals k i mean what does it mean to prove this it means that we've got this plus function here and we've got these terms with these primes in them so ku can prove that from these two terms we can shift the primes around and get a term with zero with k primes on it if i plus j equals k so this works eh if this is not the case then q can prove it's not the case here and 623 is about multiplication it says the same thing for multiplication so if i j equals k then q can prove that i times j equals k so basic arithmetical facts kind of almost like atomic arithmetical facts about the natural numbers and their numerals q can prove so again you don't need to know and i've you can see i've skipped over justifying these things here but i do want you to be aware of the fact that you can prove these basic facts here like this so you might think that q is kind of useless because there are certain things that it can't prove but actually the contrary is true uh because q is a weak theory and we can still prove quite a lot in q that makes it useful for for girdle's theorem and what you can do in q is show that all sorts of functions not just addition and multiplication work out well in queue but actually all recursive functions work out well in queue so we'll formulate a way of expressing that and that's the beginning of section 6 2.2 representation of functions in q okay so we've just we've just seen you know that plus and times let me just say they work out well in those lemmas 6 21 and 23.

[00:13:40]and what we'll assert now is in fact all recursive functions work out well in queue and one way of getting a handle on that is definition 6 24.

[00:14:28]yes so let's see what this is suppose i've just got a function which takes cages fulls of naturals to naturals right then i'm going to say f is representable in q if there's some formula which sort of like defines it and it's got variables v k up to v k plus one okay with three variables just here but precisely its free variables shown so that if i've got numbers p1 up to pk and some j here these are all in n and if no this is the concrete function this is my arithmetical function if f of the p's end up being j then q can prove this fact about to p1 up to pk and j so the formula is sort of like giving you a piece of the graph of the function this is giving us some positive information here recall what we saw with addition right if i plus j equals k q can prove i plus j equals k so this is the formula about these three things that q can prove it's the same kind of idea behind this there's a formula that tells me something about the graph of f and the other thing we'll have is or we'll want that q thinks that phi defines a function right it better be that if this turns out to have j we better not have anything else also making phi come out true so for all vk plus one if phi holes of p1 up to pk vk plus one then it better be that v k plus 1 is j so it's functional phi is defining a function we can't have two different things in here making phi come out true it has to be j something makes phi come out to be true it's j if f p vector j over here so this is the idea this is how we kind of capture that a theory like q or something that perhaps extends q represents certain functions so example here we look at the projection function this was one of the basis functions for the recursive functions actually and the idea is that from an eye tuple of things it picks up to the jth one so where uij of n1 up to ni this will pick out the jth one here okay so this is a very simple concrete function um one of the basis functions of recursive functions so what's the formula five that's going to represent it in this way well this is a simple formula well it just says all of these the v ones so this is just something that's clearly true about the different things we substitute in for v1 v2 vt up to v and vi here and also the the next thing here v i plus 1 is v j this works because we can show in queue friendly um what we got k1 here up to ki we've got an i vector of things here we can show in the queue proves and these are all supposed to have circles around them here and if vi plus one equals kj here if and only if vi plus one equals kj so all of this here and in fact one doesn't really need the theory q here this just follows from predicate calculus using the rules for equality here so this formula here will do for showing that this project this very simple projection function here can be representable in the theory here so again there's some details here we'd have to show that indeed this this held and you know i'm i'm skipping that because we haven't really done much about proofs so we can share this and actually the the next theorem again this proof will omit uh says in fact every recursive function is so representable in q by some formula or rather this is perhaps a little bit remarkable and it's saying every computable function can be represented or defined inside this theory q but q looked like a rather weak theory but nevertheless that's the case one can show this so that's the statement of 627 so the functions representable in queue are precisely the recursive functions so actually q is good enough right to prove for certain formally rather any recursive the group facts about the graph of any recursive function and actually that's exactly what it can do so we omit the proof there's a reference there to one of the texts but we will use this this theorem here i mean you might think you can add more axioms to q and represent more functions but actually remarkably that's not the case well in the following sense but actually so if i got some q prime some theory that extends q and i obtained it by adding finitely many more axioms that are true in n so q prime minus q is finite and everything in this new collection is true in n one can show that you haven't got any more representable functions so there are no new or no further representable functions okay so this is just a fact again you don't need to know this this is just an interesting comment and here but because the functions representable and q are precisely the recursive functions the diagonal function is recursive so diag is representable in queue so again let's remind ourselves what that is diag of n equals m if and only f m is the girdle number of the diagonalization other formula with girdle number and again this is just because to take a formula and build up its diagonalization is an easy matter right i mean if we wanted to look at psi here its diagonalization is what what is it it exists x such as x is the girdle number of psi here and beside and so if here if the girdle number psi is n here this is supposed to be diagonal n have the girdle number of this whole thing is diagon so we take the girdle number of n and we just embedded in a code for the rest of the string here and it's fixed what the string is going to be the only thing that's variable is well there's n and the psi so we have lemma 6 29 here for any formula phi of x in l and for any natural number q proves there is something which is this term zero within dash is after it and if i holds x being a free variable of phi then i can then say this here this is true this i can prove in q if there is something that's like this if and only if i holds when i substitute in for the free variable x and actually this isn't really about q it's just about predicate calculus and in fact it's something that was there in the chapter about deductive systems it's just lemma 371 here so also from this here we'll get what looks like a diagonalization again so this is just corollary 6 30.

[00:31:22]take a formula in the arithmetical language and the free variable of the formula is that x and will let psi be the diagonalization fire then what do we have we're having q psi holds if and only if five holds of its own girdle number on the numeral for its own a lot here but this actually is just coming from this level here if n is the girdle number of phi then what is psi right psi is the diagonalization of phi so it says there is x so x is the girdle number of phi here and five holes so this is what size and this is the diagonalization of fine here so and then what is well n here is the girdle number of phi right so this is n in here so there is x so the x equals n and five holes then within in place of x the phi we're then in place of x it's free variable and then this is just in other words it's just this right because n being the girdle number of phi here so another way of writing this is again just to say that this here just is the girdle number this is the girdle number and this numeral here is this new rule sorry gone off the page so let's back up a little bit um if n is the girdle number of phi right then psi is this diagonalization here right so there's this x x is here the girdle number of phi and five holes so this just is psi this is the formula beside so phi with n replaced uh sorry x replaced by n this is just phi with well the girdle number of phi put in the numeral for it because if n is a good number of phi this numeral is this numeral here so i've got precisely this the psi is equivalent to this phi applied to it's the numeral of its girdle number i suppose it will be clearer to say why the sorry perhaps i haven't said enough why the punch line holds the punch line is coming from the the lemma up there after all here this is psi and this is phi of girdle numbers of five okay thus okay so from lemma 629 i've got that q this is proving that is equivalent to phi of here this in place of x but this is psi and this is phi with code number for phi in place of x which is what the um what the lemma is saying right or what the crawler is 630 is saying so maybe i'll write down here chrome is 6 30.

[00:36:56]okay 631 we don't really need so let's just now look then at the diagonal number six three so this is the kind of the crux of the mata here so the diagonal right so let t be set of sentences set of axioms so a theory any language l prime which extends the language of q and in which diagonal is representable so q itself is an example of a t here so e g q so then given any formula psi of y with the three variables of psi being that's why that's there so then [Music] there is a sentence chi in the language with the theory that we're interested in proves the chi is equivalent to psi of chi so you should compare this to what we were doing before when we were talking about tarsky still on the undefinability of truth we were doing diagonalization we were talking about equivalences like this being true in in but here we're talking about being something provable in the theory t right so this is much more concrete if you like so what we've got is that chi is equivalent to the formula where we insert the girdle number for chi in for the only free variable in the formula now i give two proofs for this and we only have to you only have to worry about the informal first version if you're interested you are welcome to read the formal second version but all we want to take away from this is this informal version here and it's similar to the things that we've been doing and i've been warming up to this this point here so we in three steps first step we define 5x to be there is a y it says the y is the diagonal of x and psi holds of sorry technique corners here cycles of y so it's a little bit like exercise 6.3 we're going to talk about the diagonalization of this formula phi which already talks about diagonalization so 2 to find chi to be the diagonalization of five so what does that mean what is chi chi is to be as usual the diagonalization of phi is to be this i suggest the definition of diagonalization but coronary 630 right it then then said that q we prove that chi is then equivalent to phi with its own girdle number inserted in place of x sure so now we'll just plug in right what the definition of phi is down here q proves chi is equivalent to well we look and see what fires here so now we just plug in here the definition of phi so here's phi at the top definition of phi here yields okay so chi is equivalent to and now phi here so it exists y and kind of what i'd like to just say is y is the diagonalization of phi here and psi y holds right to make it look like what's up here so this should be in the end phi of girdle number five here right actually what i really should use perhaps is this is the function the diagonalization function that's outside what i should use is the formula here that defines the diag function here so there is a y such that y is a girdle number of the diagonalization of the formula who's of the formula phi that's here but now the point is that chi actually is the diagonalization of phi here so the y that we're talking about down here right it's just that this is just the number of kai the total number of kai so but kai is the diagonalization of fire so what we're going to say is then that ok q proves this y is this chi down here so what do we have we have that q proves that chi is equivalent to saying there is a y says that why is the diag of phi and psi holes of this y but this but this y there's only one unique solution to this why it's the code of chi so q is proving these two things so we're then going to have chi is equivalent to now psi of this guy here because this is the only candidate for y here is this code of chi that's here but this of course is this is just what we're after so we're done so this is a slightly sort of informal version where i haven't done all of the moves of the proof down if you want to be fastidious and look at the formal version which is in the second half before the qed please do so but this is going to be quite sufficient right for our purposes here so you can just get by with looking at the informal version only