Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/17/84; site milford.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!ucbvax!decvax!ittatc!milford!bill
From: bill@milford.UUCP (bill)
Newsgroups: net.math
Subject: Re: Undecidability and Proof
Message-ID: <107@milford.UUCP>
Date: Tue, 15-Oct-85 11:20:18 EDT
Article-I.D.: milford.107
Posted: Tue Oct 15 11:20:18 1985
Date-Received: Thu, 17-Oct-85 01:07:01 EDT
References: <106@milford.UUCP> <6650@boring.UUCP>
Organization: Telecomp,Inc. , Milford Ct.
Lines: 54

> > "... if you succeeded in proving that Fermat's problem is unsolvable, 
> > then ipso facto you would have shown that the conjecture is true.
> > Because if there was a counterexample, then with some big computer,
> > some day someone would pull out the counterexample."
> > 
> > How common is this attitude toward undecidability questions?
> > [...]
> > Has anyone else encountered this type of argument? How do people
> > feel about this type of 'proof'? Also, what is the attitude toward
> > such a Platonic notion of ideal "Truth"?
> 
> The argument may be given much more precisely.  A problem is that the
> notion of "(recursive) solvability" or "decidability" is defined only for a
> *class* of problems, not for a specific instance. However, if we let "P"
> stand for some specific problem, then we can consider P' = "P & n=n", and
> ask for an algorithm that, given an input value n0 for n, will output 0 or
> 1 if P'-with-n-replaced-by-n0 is false or true, respectively.  Such an
> algorithm, if it exists, is insensitive to its input.
> 
> There is a Platonic proof that no specific problem P (generalized in the
> above way) is unsolvable. The argument is: either P is false, or it is
> true. If it is false, the algorithm "Output 0" solves the problem;
> otherwise, "Output 1" does. This argumentation is unacceptable to
> intuitionists and constructivists (although they would accept the
> conclusion!).
> 
> For problems like F = "Fernat was right", that can be refuted by a
> counterexample, there is much better argument.  Clearly, if there exists a
> counterexample to F, then F is false. So, in that case, the algorithm
> "Output 0" solves F', so there exists an algorithm for solving F'.  If
> someone succeeds in proving that F' is unsolvable, such an algorithm cannot
> exist, so it follows that no counterexample to F exists. The latter is
> equivalent to "F is true".
> -- 
> 
>      Lambert Meertens
>      ...!{seismo,okstate,garfield,decvax,philabs}!lambert@mcvax.UUCP
>      CWI (Centre for Mathematics and Computer Science), Amsterdam

I think you might have missed my point. Matijasevich showed that
there are Diophantine Equations which are undecidable. Take one of
these as your 'F' predicate instead of Fermat's (Exponential)
Diophantine equation and ask if the equation can be satisfied. Why
cannot you likewise claim that since it is undecidable it must be
true because someone won't find any counter examples? In fact there
would be no counter examples in the ordinary model of the integers;
but in non-standard models ...?

Some classes of Diophantine equations can be shown not to have any
undecidable problems (say those with only one variable, and possibly
those with only two -- its been a while...) but it should still be
a possibility for Fermat's problem to be undecidable.

Cool down, Bill, cool down.