[FOM] Bound in Gödel 1931

[Alasdair Urquhart]

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
> 
>