FOM: my non-constructive proof

[Martin Davis]

At 01:57 PM 6/14/00 -0400, Fred Richman wrote:
>You said the constructive content of your proof would yield a pair of
>Diophantine relations. I assumed that meant you could have produced
>two specific relations if you wanted to. Would your story have had the
>same point if the constructive content of your proof would have
>yielded a single Diophantine relation, but it was too tedious to
>unwrap that content?

No.


> >> [F.R. again] 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?
>
>It seems simpler to me: I don't have to know anything about
>Diophantine relations, just perfect numbers. But whether or not it is
>simpler, and whether or not it is unnatural, it would be interesting
>to me to know your take on this example. Then I might understand what
>the nature of your challenge is. There are lots of reasons why
>mathematicians are sure that certain conclusions are correct, and most
>of these reasons have nothing to do with constructivity.

OK. If pressed I will say that yes, that is a definite integer, but we 
don't know whether its value is 0 or 1. But it seems silly. 1 just stands 
for "true" and 0 for "false".


>Your result showed that it was impossible for the negation of every
>Diophantine relation to be Diophantine. So nobody was going to be able
>to disprove your conclusion. Are you asking constructivists whether
>that is enough to establish your conclusion in their eyes? They would
>say no. Are you asking whether they would doubt the conclusion? That
>question is not so clear cut given the subjective nature of what makes
>us sure things are true. Certainly they can't form an opinion as to
>whether *you* should have doubted it.

So our disagreement comes down to terminology. I would say that I had 
proved the existence of a Diophantine relation with a non-Diophantine 
negation where a constructivist would say I had only proved the 
impossibility of every Diophantine relation having a Diophantine negation. 
Now remember the mathematical context: I wanted to know whether every r.e. 
relation is Diophantine. My belief that his might be true was strengthened 
by seeing that the two classes (Diophantine and r.e. relations) had the 
same closure properties:
the were closed under "and,or, exists" but not under "not". If I had been 
converted to constructivism, would the evidence for my conjecture have been 
as compelling?

Martin





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