Fixed point Lemma
in [Logic]
|
From: Daryl McCullough on 5 May 2010 07:08 apoorv says... >On May 4, 5:20=A0pm, 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. The problem here is that the formula S(x,y,z) (or (x,y,z) in your notation) depends on your coding scheme. For every coding scheme, you have a different S(x,y,z). Since Q is constructed in terms of S, then you similarly have a different Q for each coding scheme. So let's assume we number our coding schemes 1, 2, 3, etc. If A is a formula, let [A]_1 be its code under scheme 1, [A]_2 be its code under scheme 2, etc. We have the corresponding substitution formulas S_1, S_2, S_3, ... We have the corresponding fixed point formulas Q_1, Q_2, Q_3, ... Now, what you are saying is something like this: Start with scheme 1. Get the corresponding fixed point Q_1. Now, let the scheme 1 code of this formula be q. That means that [Q_1]_1 = q. Now, you want to change to scheme 2. Now Q_1 has a different code, q'. So we have [Q_1]_2 = q'. But Q_1 is *not* the fixed point for scheme 2. There is a *different* fixed point, Q_2. -- Daryl McCullough Ithaca, NY
From: apoorv on 5 May 2010 09:54 On May 5, 4:08 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > apoorv says... > > >On May 4, 5:20=A0pm, 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. > > The problem here is that the formula S(x,y,z) (or (x,y,z) in your > notation) depends on your coding scheme. For every coding scheme, > you have a different S(x,y,z). Since Q is constructed in terms of > S, then you similarly have a different Q for each coding scheme. Please note that P is also constructed in terms of S. What you say implies that the choice of code for Q changes P. P must then depend explicitly on the code of Q ; Q in any case depends explicitly on the code for P. Given the nature of godel numbering, code P must be both less than and greater than code of Q. > So let's assume we number our coding schemes 1, 2, 3, etc. > If A is a formula, let [A]_1 be its code under scheme 1, [A]_2 > be its code under scheme 2, etc. > We have the corresponding substitution formulas S_1, S_2, S_3, ... > We have the corresponding fixed point formulas Q_1, Q_2, Q_3, ... > > Now, what you are saying is something like this: Start with scheme 1. > Get the corresponding fixed point Q_1. Now, let the scheme 1 code of this > formula be q. That means that [Q_1]_1 = q. Now, you want to change > to scheme 2. Now Q_1 has a different code, q'. So we have > [Q_1]_2 = q'. But Q_1 is *not* the fixed point for scheme 2. There > is a *different* fixed point, Q_2. The fixed point lemma uses only 2 formulas. Formula P -all z((x,x,z)-->phi(z)). Let us say that the code of this formula is 10. The second formula Q is all z((10,10,z)-->Phi(z)). If P does not depend on the code for Q, then (10,10,z) says that Z is the code of formula obtained replacing x by 10 in the formula whose code is 10 i.e P. So Q is all z (z=code Q-->Phi(z)). The choice of code for P,or for that matter any other formula ,does not constrain the choice of code for Q. On the other hand, if P depends on the choice of code for Q, then P explicitly depends on its own code whereby ,at least for the usual godel numbering, code P>code P. -apoorv
From: Daryl McCullough on 5 May 2010 10:49 apoorv says... >On May 5, 4:08=A0pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: >> The problem here is that the formula S(x,y,z) (or (x,y,z) in your >> notation) depends on your coding scheme. For every coding scheme, >> you have a different S(x,y,z). Since Q is constructed in terms of >> S, then you similarly have a different Q for each coding scheme. > >Please note that P is also constructed in terms of S. What you say >implies that the choice of code for Q changes P. >P must then depend explicitly on the code of Q ; I still do not understand what you are saying. Yes, P depends on your coding scheme. So there is different P for each coding scheme: P_1, P_2, etc. >Q in any case depends explicitly >on the code for P. Given the nature of godel numbering, code P must be >both less than and greater than code of Q. Where are you getting that? >The fixed point lemma uses only 2 formulas. For *each* coding scheme, there are two formulas that are specific to *that* coding scheme. >Formula P -all z((x,x,z)-->phi(z)). The formula (x,x,z) is not a single formula. There is a different one for each coding scheme. >Let us say that the code of this formula is 10. >The second formula Q is all z((10,10,z)-->Phi(z)). Yes, and the code for Q will, in general, be much, much greater than 10. >If P does not depend on the code for Q, then (10,10,z) says that Z is >the code of formula obtained replacing x by 10 in the formula whose >code is 10 i.e P. Right. >So Q is all z (z=code Q-->Phi(z)). No, Q is the formula all z((10,10,z)-->Phi(z)). Q is *provably equivalent* to the formula all z (z=code Q-->Phi(z)), but it's not equal. Two formulas that are provably equivalent don't have the same codes. >The choice of code for P,or for that matter any other formula ,does >not constrain the choice of code for Q. It certainly does! In my notation, P_1 is the formula all z( S_1(x,x,z)-->phi(z) ). I'm using the subscript _1 to mean that this is the S and the P corresponding to the first coding scheme. You want to suppose that this formula has code 10 (according to coding scheme 1). Now, you form the corresponding Q, which I'll call Q_1: all z (S_1(10,10,z)-->Phi(z)) Now, let's suppose that the code for this formula in our coding scheme is 1000. We also have: S_1(10,10,z) <-> z=1000 So, we have Q_1 <-> Phi(1000) The statement Phi(1000) on the right will have a different code, say 5000. It's provably equivalent to Q_1, but it doesn't have the same code. So we have, for this particular coding scheme: 1. Q_1 <-> Phi(1000) 2. the code of Q_1 (in coding scheme 1) = 1000 Now, you want to come up with some other coding scheme that gives Q_1 a different code, say 12. You can do that. Call that scheme 2. Here's a coding scheme that does that: To compute the code of a formula A, do the following: 1. compute the code according to coding scheme 1. 2. If the result is exactly 1000, return 12. 3. Otherwise, if the result is less than 12, return that result. 4. Otherwise, return the result + 1. This is a complicated way of computing a code for a formula, but it is computable. There is a corresponding extremely complicated formula S_2(x,y,z) with the property that S_2(x,y,z) is true if and only if z is the code for the result of replacing the numeral for y for all occurrences of free variables in the formula whose code is x. Then we can form the corresponding formula P_2: P_2 == all z (S_2(x,x,z) --> Phi(z)) Then the code for P_2 will probably be enormous. Let's say it's 1,000,000. There will be a corresponding formula Q_2: Q_2 == all z (S_2(1000000, 1000000,z) --> Phi(z)) The code for Q_2 will be even more enormous. Let's say it's 1,000,000,000. Then we have the following facts: 1. P_1 == all z (S_1(x,x,z) --> Phi(z)) 2. the code for P_1 is 10 3. P_2 == all z (S_2(x,x,z) --> Phi(z)) 4. the code for P_2 is 999,999 in the first scheme, and 1,000,000 in the second scheme. 5. Q_1 == all z (S_1(10,10,z) --> Phi(z)) 6. The code for Q_1 is 1000 in the first scheme, and 12 in the second scheme. 7. Q_1 <-> Phi(1000) 8. Q_2 == all z (S_2(1000000,1000000,z) --> Phi(z)) 9. The code for Q_2 is 999999999 in the first scheme, and 1000000000 in the second scheme. 10 Q_2 <-> Phi(1000000000) -- Daryl McCullough Ithaca, NY
From: apoorv on 6 May 2010 06:59 On May 5, 7:49 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > apoorv says... > > >On May 5, 4:08=A0pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > >> The problem here is that the formula S(x,y,z) (or (x,y,z) in your > >> notation) depends on your coding scheme. For every coding scheme, > >> you have a different S(x,y,z). Since Q is constructed in terms of > >> S, then you similarly have a different Q for each coding scheme. > > >Please note that P is also constructed in terms of S. What you say > >implies that the choice of code for Q changes P. > >P must then depend explicitly on the code of Q ; > > I still do not understand what you are saying. Yes, P depends > on your coding scheme. So there is different P for each coding > scheme: P_1, P_2, etc. > > >Q in any case depends explicitly > >on the code for P. Given the nature of godel numbering, code P must be > >both less than and greater than code of Q. > > Where are you getting that? > > >The fixed point lemma uses only 2 formulas. > > For *each* coding scheme, there are two formulas that are > specific to *that* coding scheme. > > >Formula P -all z((x,x,z)-->phi(z)). > > The formula (x,x,z) is not a single formula. There is a different > one for each coding scheme. > > >Let us say that the code of this formula is 10. > >The second formula Q is all z((10,10,z)-->Phi(z)). > > Yes, and the code for Q will, in general, be much, much > greater than 10. > > >If P does not depend on the code for Q, then (10,10,z) says that Z is > >the code of formula obtained replacing x by 10 in the formula whose > >code is 10 i.e P. > > Right. > > >So Q is all z (z=code Q-->Phi(z)). > > No, Q is the formula all z((10,10,z)-->Phi(z)). > Q is *provably equivalent* to the formula > all z (z=code Q-->Phi(z)), > but it's not equal. > > Two formulas that are provably equivalent don't have the > same codes. > > >The choice of code for P,or for that matter any other formula ,does > >not constrain the choice of code for Q. > > It certainly does! In my notation, P_1 is the formula > all z( S_1(x,x,z)-->phi(z) ). I'm using the subscript _1 > to mean that this is the S and the P corresponding to the > first coding scheme. You want to suppose that this formula > has code 10 (according to coding scheme 1). > > Now, you form the corresponding Q, which I'll call Q_1: > > all z (S_1(10,10,z)-->Phi(z)) > > Now, let's suppose that the code for this formula in our > coding scheme is 1000. > > We also have: > > S_1(10,10,z) <-> z=1000 > > So, we have > > Q_1 <-> Phi(1000) > > The statement Phi(1000) on the right will have a different code, > say 5000. It's provably equivalent to Q_1, but it doesn't have the > same code. > > So we have, for this particular coding scheme: > > 1. Q_1 <-> Phi(1000) > 2. the code of Q_1 (in coding scheme 1) = 1000 > > Now, you want to come up with some other coding scheme that gives > Q_1 a different code, say 12. You can do that. Call that scheme 2. > Here's a coding scheme that does that: > > To compute the code of a formula A, do the following: > 1. compute the code according to coding scheme 1. > 2. If the result is exactly 1000, return 12. > 3. Otherwise, if the result is less than 12, return that result. > 4. Otherwise, return the result + 1. > > This is a complicated way of computing a code for a formula, > but it is computable. There is a corresponding extremely complicated > formula S_2(x,y,z) with the property that S_2(x,y,z) is true if and > only if z is the code for the result of replacing the numeral for y > for all occurrences of free variables in the formula whose code is x. > Then we can form the corresponding formula P_2: > > P_2 == all z (S_2(x,x,z) --> Phi(z)) > > Then the code for P_2 will probably be enormous. Let's say it's > 1,000,000. There will be a corresponding formula Q_2: > > Q_2 == all z (S_2(1000000, 1000000,z) --> Phi(z)) > > The code for Q_2 will be even more enormous. Let's say it's > 1,000,000,000. Then we have the following facts: > > 1. P_1 == all z (S_1(x,x,z) --> Phi(z)) > 2. the code for P_1 is 10 > 3. P_2 == all z (S_2(x,x,z) --> Phi(z)) > 4. the code for P_2 is 999,999 in the first scheme, and > 1,000,000 in the second scheme. > 5. Q_1 == all z (S_1(10,10,z) --> Phi(z)) > 6. The code for Q_1 is 1000 in the first scheme, and 12 > in the second scheme. > 7. Q_1 <-> Phi(1000) > 8. Q_2 == all z (S_2(1000000,1000000,z) --> Phi(z)) > 9. The code for Q_2 is 999999999 in the first scheme, > and 1000000000 in the second scheme. > 10 Q_2 <-> Phi(1000000000) > > -- > Daryl McCullough > Ithaca, NY 1) Is there any explicit presentation of the substitution formula for the usual coding? If it were so, we could easily make out the dependence of S on the particular coding.I suspect an explicit presentation is not known.Do we know the godel number for the godel sentence for P.A? 2) It is very plausible that every coding gives a different substitution formula. But the number of possible codings would be at least equal to the number of 1-1 maps from the set of natural numbers into itself. Thus, the set of all such formulae has the cardinality c, contrary to our asumption that the formulae could be numbered. 3)If S depends on the coding used, it should incorporate in itself the very many arbitrarily assigned codes of the very many formulae .P, should through the formula S, incorporate its own code. 4) At the very least, there are different substitution formulae corresponding to the substitution of different free variables---in which case, the self reference gives way , as demonstrated in the second post. -apoorv 1) Each coding (say C1) results in a different substitution formula S and hence a different P.
From: Aatu Koskensilta on 6 May 2010 07:17
apoorv <sudhir_sh(a)hotmail.com> writes: > 1) Is there any explicit presentation of the substitution formula for > the usual coding? You can answer all these questions for yourself by reading a standard text on the subject. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus |