[FOM] Bound in Gödel 1931
Joe Shipman
joeshipman at aol.com
Wed Mar 1 18:00:40 EST 2017
I have always wondered why Godel didn't first prove his theorems for PA with Exponentiation, or even for Exponential Function Arithmetic, and then show that Exponentiation was representable.
-- JS
> On Feb 28, 2017, at 7:55 PM, Alasdair Urquhart <urquhart at cs.toronto.edu> wrote:
>
> I think that Goedel's bound is correct. I argue as follows.
>
> Let a_1, a_2, ..., a_k be a sequence of positive numbers. Then
> the Goedel number gn(a_1, ..., a_k) of the sequence is
>
> g = 2^{a_1} . 3^{a_2} . ... . p_k^{a_k},
>
> where p_k is the kth prime number. By induction on k
> we can prove the bound
>
> g <= (p_k)^{a_1 + ... + a_k}.
>
> Let a_1, ..., a_k and b_1, ..., b_l be two finite sequences
> of positive numbers, x and y their gn's. Then the gn x*y
> of their concatenation is bounded by
>
> (p_{k+l})^{a_1 + ... + a_k + b_1 + ... +b_l}.
>
> However,
>
> a_1 + ... + a_k <= 2^{a_1} + 3^{a_2} + ... + (p_k)^{a_k}
> <= 2^{a_1} . 3^{a_2} . ... . (p_k)^{a_k}
> = x,
>
> since all the terms in the second sum are >= 2. Hence,
>
> gn(a_1, ..., a_k, b_1, ..., b_l) <= (p_{k+l})^{x+y},
>
> which is Goedel's bound.
>
>
>> On Mon, 27 Feb 2017, Richard Heck wrote:
>>
>> I'm teaching Gödel's classic paper on the incompleteness theorems and have been wondering about the bound he gives in
>> definition (8) of the star function. He doesn't explain where he got the bound (as he does for the one in (23)), and I
>> don't see any simple way to explain why it works. If I parrot the sort of thing Gödel says in footnote 35, it'd be
>> something like this.
>> Each of the prime factors in x * y is <= Pr(l(x) + l(y)). The exponent on each of these is <= max(x,y) or, if you
>> prefer, x+y. And there are l(x) + l(y) factors. So
>> x*y <= Pr(l(x) + l(y)) ^ { (x+y)(l(x) + l(y) }.
>> Or, since l(x) + l(y) <= x + y, we could do:
>> x*y <= Pr(l(x) + l(y)) ^ ((x+y)^2)
>> Whereas Gödel has
>> x*y <= Pr(l(x) + l(y)) ^ (x+y).
>> It's not that I think this bound doesn't work. It probably does. (In general, Gödel's bounds are pretty loose.) But it's
>> surprising he doesn't say anything about it, since this is not exactly obvious. Might there by a typo or thinko here?
>> Any thoughts?
>> Richard Heck
>> --
>> -----------------------
>> Richard G Heck Jr
>> Professor of Philosophy
>> Brown University
>> Website: http://rgheck.frege.org/
>> Blog: http://rgheck.blogspot.com/
>> Amazon: http://amazon.com/author/richardgheckjr
>> Google+: https://plus.google.com/108873188908195388170
>> Google Scholar: https://scholar.google.com/citations?user=QUKBG6EAAAAJ
>> ORCID: http://orcid.org/0000-0002-2961-2663
>> Research Gate: https://www.researchgate.net/profile/Richard_Heck
>> Academia.edu: https://brown.academia.edu/RichardHeck
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list