Fixed point Lemma
in [Logic]
|
From: apoorv on 6 May 2010 08:10 On May 6, 4:17 pm, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > apoorv <sudhir...(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.koskensi...(a)uta.fi) > > "Wovon man nicht sprechan kann, darüber muss man schweigen" > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus well, what is the godel number for the godel sentence for PA? what number does your standard text give for it-10,100,1000 or some unnameable number? Is there one substitution formula or many or uncountably many? are there different substitution formulae resulting from change of different free variables? -apoorv
From: Aatu Koskensilta on 6 May 2010 08:27 apoorv <sudhir_sh(a)hotmail.com> writes: > well, what is the godel number for the godel sentence for PA? The G�del number of the G�del sentence for PA depends on the details of the numbering chosen, and is of no intrinsic interest. > Is there one substitution formula or many or uncountably many? For any given G�del numbering there are infinitely many formulas (of suitable logical form) defining substitution. There are only countably many G�del numberings, as follows from the requirement that the usual syntactic operations be primitive recursive, there being only countably many primitive recursive functions. Again, you can answer all your 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
From: Daryl McCullough on 6 May 2010 09:06 apoorv says... >1) Is there any explicit presentation of the substitution formula for >the usual coding? That was one of the things that Godel did in developing his original proof of the incompleteness theorem. >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? We can certainly express it as a closed arithmetical term--in one coding, the codes involve +, *, and ^ (exponentiation). The codes are *really* huge though, so if you tried to write such a code out as an explicit numeral, it would be many, many lines long. >2) It is very plausible that every coding gives a different >substitution formula. It's not just plausible; it's certain. >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. No. The codings have to be *computable*. There are only countably many computable codings. Here's the most straight-forward coding to understand: Take a formula Phi, and write it out using ASCII symbols. Replace the symbols by their corresponding base-ten numerals, and concatenate (adding 0s where necessary). For example, for the formula 2+2=4 we would compute the code as follows: 2 --> ASCII code 50 + --> ASCII code 43 2 --> ASCII code 50 = --> ASCII code 61 4 --> ASCII code 52 So 2+2=4 would have ASCII code 5043506152. This is not the coding that Godel used, because it is mathematically cumbersome to deal with, but it is probably the easiest code to understand. >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. Typically, the kinds of codes that are used start off by giving arbitrary assignments of naturals to the symbols occurring in the language of PA and first order logic: 0, +, *, =, E, A, &, or, ->, ~, <->, <, >, and variables. Then more complicated expressions are built up out of these codes using some kind of pairing function or list-formation function. The concatenation operation described above is one way. >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. Yes, if you like, you can make a more complicated substitution formula: S'(x,y,z,w) which says that w is the code of the result of substituting the numeral corresponding to x for variable number y in the formula whose code is z. There is no point in introducing this complication. It doesn't change anything. The fixed point lemma goes through just the same. Pick a variable, say "x", it will have some code, say 57. Then let P be the formula forall w, S'(x,57,x,w) --> Phi(w) This formula will have some code, say 3245. Then let Q be the formula forall w, S'(3245,57,3245,w) --> Phi(w) This formula will itself have a code, say 123456789. Then the following will be the case 1. S'(3245,57,3245,w) <-> w=123456789 2. The code of Q is 123456789. 3. Q <-> Phi(123456789) -- Daryl McCullough Ithaca, NY
From: apoorv on 6 May 2010 13:25 On May 6, 6:06 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > apoorv says... > > >1) Is there any explicit presentation of the substitution formula for > >the usual coding? > > That was one of the things that Godel did in developing his original > proof of the incompleteness theorem. > > >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? > > We can certainly express it as a closed arithmetical term--in one coding, > the codes involve +, *, and ^ (exponentiation). The codes are *really* > huge though, so if you tried to write such a code out as an explicit > numeral, it would be many, many lines long. It is easy even for me to see that S(a,a,y) where a is a given number can be coded. What i am unable to see is that there is a formula S(x,x,y) where x can have any arbitrary value and there are no bounds on the length of the formula that x may represent. > >2) It is very plausible that every coding gives a different > >substitution formula. > > It's not just plausible; it's certain. > > >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. > > No. The codings have to be *computable*. There are only countably > many computable codings. > > Here's the most straight-forward coding to understand: > Take a formula Phi, and write it out using ASCII symbols. > Replace the symbols by their corresponding base-ten numerals, > and concatenate (adding 0s where necessary). > > For example, for the formula 2+2=4 > we would compute the code as follows: > > 2 --> ASCII code 50 > + --> ASCII code 43 > 2 --> ASCII code 50 > = --> ASCII code 61 > 4 --> ASCII code 52 > > So 2+2=4 would have ASCII code 5043506152. This is not the > coding that Godel used, because it is mathematically cumbersome > to deal with, but it is probably the easiest code to understand. > > >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. > > Typically, the kinds of codes that are used start off by giving > arbitrary assignments of naturals to the symbols occurring in > the language of PA and first order logic: > 0, +, *, =, E, A, &, or, ->, ~, <->, <, >, and variables. > Then more complicated expressions are built up out of these > codes using some kind of pairing function or list-formation > function. The concatenation operation described above is one > way. > > >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. > > Yes, if you like, you can make a more complicated substitution formula: > > S'(x,y,z,w) > > which says that w is the code of the result of substituting > the numeral corresponding to x for variable number y in the > formula whose code is z. There is no point in introducing > this complication. It doesn't change anything. The fixed point > lemma goes through just the same. > > Pick a variable, say "x", it will have some code, say 57. > Then let P be the formula > > forall w, S'(x,57,x,w) --> Phi(w) This is not clear. Are we substituting x for the variable whose code is 57 i.e x, in the formula whose code is x? would this not give w=x? -apoorv
From: apoorv on 6 May 2010 13:33
On May 6, 5:23 pm, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > apoorv <sudhir...(a)hotmail.com> writes: > > well, what is the godel number for the godel sentence for PA? > > The Gödel number of the Gödel sentence for PA depends on the details of > the numbering chosen, and is of no intrinsic interest. Sure. maybe i could be given the godel number for the godel sentence for PA for the numbering used by godel. But i suspect we do not have the foggiest idea of what that number is. > > Is there one substitution formula or many or uncountably many? > > For any given Gödel numbering there are infinitely many formulas (of > suitable logical form) defining substitution. There are only countably > many Gödel numberings, as follows from the requirement that the usual > syntactic operations primitive recursive, and there being only countably > many primitive recursive functions. So we have one substitution formula for replacing the free variable v and another for replacing the free variable x in a given formula? -apoorv |