Fixed point Lemma
in [Logic]
|
From: apoorv on 21 Apr 2010 07:11 The Fixed point lemma is: if p is the godel number of the formula P -- Ay((x,x,y)-->B(y)) and q is the godel number of sentence Q---Ay((p,p,y)-->B(y)), then Q <--> B(q). One could use other numbering for the formulae (or use other variable symbols while using the same numbering). If p' is the (new)number for P, the corresponding Q' would be Ay((p',p',y)-->B(y)) and the fixed point lemma would say, Q'<-->B(q') with q' as the new number for Q'. Presumably, one could think of a numbering which is the same as the usual numbering except for the sentence Q , where instead of being q, it is q'. P is still Ay((x,x,y)-->B(y)) with the (new) number p Q is still Ay((p,p,y)-->B(y)) ,but with the new number q'. However, in the new numbering, (p,p,y) is true iff y=q'[in words: y is the number of the sentence obtained by replacing, in the formula whose number is p i.e P, the free variable by p.That is, the y is the number of Q. In the new numbering this is true iff y =q' ] . So, in the new numbering Q<-->B(q'). So, we have Q <-->B(q)<--> B(q'), where q' is arbitrary. I am not able to resolve this issue. will appreciate help in clarifying this . -apoorv
From: apoorv on 24 Apr 2010 05:12 On Apr 21, 4:11 pm, apoorv <sudhir...(a)hotmail.com> wrote: > The Fixed point lemma is: > if p is the godel number of the formula P -- Ay((x,x,y)-->B(y)) > and q is the godel number of sentence Q---Ay((p,p,y)-->B(y)), > then Q <--> B(q). > One could use other numbering for the formulae (or use other > variable symbols while using the same numbering). > If p' is the (new)number for P, the corresponding Q' would be > Ay((p',p',y)-->B(y)) and > the fixed point lemma would say, Q'<-->B(q') with q' as the new number > for Q'. > Presumably, one could think of a numbering which is the same as the > usual numbering > except for the sentence Q , where instead of being q, it is q'. > P is still Ay((x,x,y)-->B(y)) with the (new) number p > Q is still Ay((p,p,y)-->B(y)) ,but with the new number q'. However, in > the new numbering, > (p,p,y) is true iff y=q'[in words: y is the number of the sentence > obtained by replacing, in the formula whose number is p i.e P, the > free variable by p.That is, the y is the number of Q. In the new > numbering this is true iff y =q' ] . > So, in the new numbering Q<-->B(q'). > > So, we have Q <-->B(q)<--> B(q'), where q' is arbitrary. > > I am not able to resolve this issue. will appreciate help in > clarifying this . > > -apoorv Apropos above post, a plausible? but completely heretical view: We note that in the first formula P, a variable v is being replaced by x. In the second sentence Q, x (now treated as a variable) is being replaced by p. To make this more explicit, consider the notation (v:x,x,y) <--> y is the godel number of the formula obtained by replacing the free variable v by x in the formula whose godel number is x. Then P is Ay((v:x,x,y)-->B(y)) with Godel number p.P has the free variable x. (let) Q' be Ay((v:p,p,y)-->B(y)) with godel number q'. Q' is obtained from P by replacing the free variable x in P by p (the godel number of P) Since v is not free in the formula with number p i.e P, the substitution contemplated by (v:p,p,y)is vacuous and (v:p,p,y)<-->y=p (let) Q be Ay((x:p,p,y)-->B(y)) with godel number q.[Q is Not obtained from P by replacing the free variable x in P by p. That replacement yields Q' as noted above.] Now (x:p,p,y)<--> y is the godel number of the formula obtained by replacing the free variable x by p in the formula with godel number p i.e P.That is y is the godel number of Q' or y=q'. So we have P with godel number p ----Ay((v:x,x,y)--> B(y)). Q' with godel number q' --- Ay((y is the godel number of P-->B(y)) Q with godel number q----Ay((y is the godel number of Q'-->B(y)) So, Q'<-->B(p) and Q<-->B(q').The self reference in Q mellts away. -apoorv
From: apoorv on 3 May 2010 03:03 On Apr 24, 2:12 pm, apoorv <sudhir...(a)hotmail.com> wrote: > On Apr 21, 4:11 pm, apoorv <sudhir...(a)hotmail.com> wrote: > > > > > > > The Fixed point lemma is: > > if p is the godel number of the formula P -- Ay((x,x,y)-->B(y)) > > and q is the godel number of sentence Q---Ay((p,p,y)-->B(y)), > > then Q <--> B(q). > > One could use other numbering for the formulae (or use other > > variable symbols while using the same numbering). > > If p' is the (new)number for P, the corresponding Q' would be > > Ay((p',p',y)-->B(y)) and > > the fixed point lemma would say, Q'<-->B(q') with q' as the new number > > for Q'. > > Presumably, one could think of a numbering which is the same as the > > usual numbering > > except for the sentence Q , where instead of being q, it is q'. > > P is still Ay((x,x,y)-->B(y)) with the (new) number p > > Q is still Ay((p,p,y)-->B(y)) ,but with the new number q'. However, in > > the new numbering, > > (p,p,y) is true iff y=q'[in words: y is the number of the sentence > > obtained by replacing, in the formula whose number is p i.e P, the > > free variable by p.That is, the y is the number of Q. In the new > > numbering this is true iff y =q' ] . > > So, in the new numbering Q<-->B(q'). > > > So, we have Q <-->B(q)<--> B(q'), where q' is arbitrary. > > > I am not able to resolve this issue. will appreciate help in > > clarifying this . > > > -apoorv > > Apropos above post, a plausible? but completely heretical view: > We note that in the first formula P, a variable v is being replaced by > x. > In the second sentence Q, x (now treated as a variable) is being > replaced by p. > To make this more explicit, consider the notation > (v:x,x,y) <--> y is the godel number of the formula obtained by > replacing the free > variable v by x in the formula whose godel number > is x. > Then P is Ay((v:x,x,y)-->B(y)) with Godel number p.P has the free > variable x. > (let) Q' be Ay((v:p,p,y)-->B(y)) with godel number q'. > Q' is obtained from P by replacing the free variable x in P by p (the > godel number of P) > Since v is not free in the formula with number p i.e P, the > substitution contemplated by (v:p,p,y)is vacuous and > (v:p,p,y)<-->y=p > (let) Q be Ay((x:p,p,y)-->B(y)) with godel number q.[Q is Not obtained > from P by replacing the free variable x in P by p. That replacement > yields Q' as noted above.] > Now (x:p,p,y)<--> y is the godel number of the formula obtained by > replacing the free variable x by p in the formula with godel number p > i.e P.That is y is the godel number of Q' or y=q'. > > So we have P with godel number p ----Ay((v:x,x,y)--> B(y)). > Q' with godel number q' --- Ay((y is the godel number of P-->B(y)) > Q with godel number q----Ay((y is the godel number of Q'-->B(y)) > So, Q'<-->B(p) and Q<-->B(q').The self reference in Q mellts away. > -apoorv- Hide quoted text - > > - Show quoted text - Am still trying to figure out 1) What is the Godel no. of (x,x,y) with the usual numbering? 2)One can visualise an effective computation methodology for (x,x,y) for any particular value of x (say 2^3.3^5.5^3).however a computation methodolgy for (x,x,y) as a function of x is not at all clear. 3)If (a,a,y) is computed by a turing machine,would the machine be dependent on a? Is there a known T.M that computes (a,a,y) for all a? 4) Finally, what is the godel number of the godel sentence for P.A? -apoorv
From: Daryl McCullough on 4 May 2010 08:20 I'm having trouble understanding what, exactly, is your question about the fixed point lemma. The conclusion of the theorem is this: for any formula Phi(x) with one free variable, x, there is another formula Q with Godel code q such that it is provable that Q <-> Phi(N_q) where N_q is the numeral corresponding to the natural number q. The way to prove this is to define the substitution predicate S(x,y,z) with the following property: 1. Let A be any formula. 2. Let n be the Godel code of A. 3. Let m be any natural number. 4. Let A' be the result of replacing the free variables in A by N_m. 5. Let k be the Godel code of A'. Then the following formula is provable: 6. forall z, S(N_n, N_m, z) <-> z = N_k Given such a formula S(x,y,z), and given Phi(x), we can find our formula Q as follows: 1. Let P be the formula: forall z, S(x,x,z) -> Phi(z) 2. Let p be the Godel code of P. 3. Let Q be the result of replacing the free variables in P by N_p. 4. Then Q is the formula: forall z, S(N_p, N_p, z) -> Phi(z) 5. Let q be the Godel code of Q. Then, by properties of the substitution predicate, we have: 6. forall z, S(N_p, N_p, z) <-> z = N_q A consequence of 6 is the following: 7. (forall z, S(N_p, N_p, z) -> Phi(z)) <-> (forall z, z = N_q -> Phi(z)) The right side of the <-> in 7 can be simplified to just Phi(N_q). So we have: 8. (forall z, S(N_p, N_p, z) -> Phi(z)) <-> Phi(N_q) The left side of <-> is just Q. So we have: 9. Q <-> Phi(N_q) -- Daryl McCullough Ithaca, NY
From: apoorv on 5 May 2010 06:35 On May 4, 5:20 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > I'm having trouble understanding what, exactly, is your question > about the fixed point lemma. Thanks for responding.Firstly, just to clarify notation, i had used (x,x,y) for your S(x,x,y) and dropped the distinction between the natural numbers and the numerals representing them. The clarification that i sought in the opening post was: let Q be the formula Q<-->Phi(codeQ). Q itself does not contain code Q explicitly although it depends on the codes of other formulae. If the code representing Q is changed from q to q' without changing the code of other formulae, then Q does not change.Then we get Q<-->Phi(q) and Q<-->Phi(q').q' being arbitrary, we either have Allx Phi(x) or Allx ~Phi(x) for any formula Phi. There were some more clarifications that i requested in the subsequent post, but essentially i wanted to know if the godel sentence for P.A has been written out explicitly in the language of arithmetic and what is its godel number? > The conclusion of the theorem is this: for any formula Phi(x) > with one free variable, x, there is another formula Q with Godel > code q such that it is provable that > > Q <-> Phi(N_q) > > where N_q is the numeral corresponding to the natural number q. > > The way to prove this is to define the substitution predicate > S(x,y,z) with the following property: > > 1. Let A be any formula. > 2. Let n be the Godel code of A. > 3. Let m be any natural number. > 4. Let A' be the result of replacing the free variables in A by N_m. Do we need to state clearly ,which of the free variables -if any- is to be replaced by N_m?A' will depend on this specification: If we consider the formula x=0, the result of replacing x by 1 is the sentence 1=0;the result of replacing y by1 is just x=0 ,as y does not occur (free) in x=0. Perhaps, we have a predicate S for replacing ( in a formula)the variable v if free and another S' for replacing x ( in that formula) if free. -apoorv > 5. Let k be the Godel code of A'. > > Then the following formula is provable: > > 6. forall z, S(N_n, N_m, z) <-> z = N_k > Given such a formula S(x,y,z), and given Phi(x), > we can find our formula Q as follows: > > 1. Let P be the formula: forall z, S(x,x,z) -> Phi(z) > 2. Let p be the Godel code of P. > 3. Let Q be the result of replacing the free variables in P by N_p. > 4. Then Q is the formula: forall z, S(N_p, N_p, z) -> Phi(z) > 5. Let q be the Godel code of Q. > > Then, by properties of the substitution predicate, we have: > > 6. forall z, S(N_p, N_p, z) <-> z = N_q > > A consequence of 6 is the following: > > 7. (forall z, S(N_p, N_p, z) -> Phi(z)) <-> (forall z, z = N_q -> Phi(z)) > > The right side of the <-> in 7 can be simplified to just Phi(N_q). So > we have: > > 8. (forall z, S(N_p, N_p, z) -> Phi(z)) <-> Phi(N_q) > > The left side of <-> is just Q. So we have: > > 9. Q <-> Phi(N_q) > > -- > Daryl McCullough > Ithaca, NY
|
Next
|
Last
Pages: 1 2 3 4 5 6 7 Prev: sci.lang is not meant for advertisement Next: The Electron’s puzzles. |