FOM: Goedel: truth and misinterpretations

[Martin Davis]

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




                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com