FOM: my non-constructive proof

Martin Davis martin at
Fri Jun 9 02:07:27 EDT 2000

At 10:40 PM 6/7/00 -0400, Fred Richman wrote:
>martin at wrote:
> > Challenge to committed constructivists: should I have entertained the
> > least doubt about the existence of such a Diopahntine set although I
> > could not furnish an example? The constructive content of my proof if
> > I cared to pay attention, would yield a pair of Diophanitne relations
> > at least one of which does not have a Diopahntine complement. For an
> > actual example, I had to wait twenty years.
>Why don't you believe that your proof furnishes an "actual example"?

Should I have said a specific example? My proof showed that there is a 
Diophantine relation whose negation is not Diophantine. But I was unable to 
furnish an example of such.

>I'd like to clarify this situation by possibly simplifying it a bit.
>Let P be a proposition (like "there is an odd perfect number") and
>let's look for an integer n such that n = 1 if P is true and n = 0 if
>P is false. Are you asking whether anyone should have the least doubt
>about the existence of such an integer?

I don't agree that this is a simplification. I introduced my example into 
the discussion precisely to avoid this kind of artificiality. My example 
came up in my research, and my challenge remains: should I have entertained 
the least doubt about the correctness of my conclusion even though the 
means for obtaining it was (and remained for 20 years, non-constructive?

>Certainly a constructivist would not claim, on general grounds, that
>such an integer existed. An unwillingness to claim existence would
>seem to be evidence of a doubt. On the other hand, the constructivist
>might just like the finer distinctions that can be made when one
>rejects the principle that such an integer exists for every
>proposition. Like the distinction between your proof and the
>construction of an "actual example".

Of course the construction of an example provides additional information; 
one needn't be a constructivist to enjoy constructive proofs. My 
"challenge" has to do with whether a constructivist would really doubt or 
deny the truth of my conclusion.


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

More information about the FOM mailing list