FOM: Goedel: truth and misinterpretations

Martin Davis martin at
Wed Oct 25 14:49:47 EDT 2000

At 07:28 PM 10/25/00 +0200, Kanovei wrote:
>These sentences are obtained as follows.
>There are two sets of sentences, say X \subseteq Y,
>and we know that X is r.e. but Y is not r.e., hence, the
>difference Y - X is infinite, and the "sentences" are just
>those in the difference. There is no one concrete sentence
>there, all we know is that they do exist in plentitude.

This is just not true. For any suitable theory (e.g. any axiomatizable 
consistent extension of Robinson's Q) one can exhibit an explicit 
polynomial P with integer coefficients such that the equation P=0 has no 
solutions in natural numbers, but that fact is not provable in the given 
theory. In fact, one can even manage this so that the only change from one 
theory to another is in the value of a single parameter. Of course, P will 
not be very pretty and some of the numbers will be very large.


                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at
                          (Add 1 and get 0)

More information about the FOM mailing list