[FOM] Bound in Gödel 1931

Richard Heck richard_heck at brown.edu
Mon Feb 27 15:39:54 EST 2017

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170227/fcf2a115/attachment.html>

More information about the FOM mailing list