FOM: my non-constructive proof

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

```At 10:40 PM 6/7/00 -0400, Fred Richman wrote:
>martin at eipye.com 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

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

```