Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 (MC840302); site boring.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!decvax!ucbvax!ucdavis!lll-crg!seismo!mcvax!boring!lambert
From: lambert@boring.UUCP
Newsgroups: net.math
Subject: Re: Undecidability and Proof
Message-ID: <6656@boring.UUCP>
Date: Thu, 17-Oct-85 21:27:33 EDT
Article-I.D.: boring.6656
Posted: Thu Oct 17 21:27:33 1985
Date-Received: Sun, 20-Oct-85 06:19:35 EDT
References: <106@milford.UUCP> <6650@boring.UUCP> <107@milford.UUCP>
Reply-To: lambert@boring.UUCP (Lambert Meertens)
Organization: CWI, Amsterdam
Lines: 99
Apparently-To: rnews@mcvax.LOCAL

bill@milford.UUCP, initially quoting Lang:
>>> "... 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"?

Me, following up:
>> There is a Platonic proof that no specific problem P (generalized in the
>> above way) is unsolvable. [...]
>> 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".

Bill again, gradually warming up:
>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 ...?

I may have missed the point, in which case I may still be missing it.  In
general, I find ``Platonic'' arguments unacceptable.  But in the case
cited, my assumption was that this was not the Platonic argument, but the
good one, phrased somewhat less felicitous.  Here I may have been mistaken.
So there are two issues: (i) is my argument correct; and (ii) is Lang's
argument correct?  The latter argument leaves out too many steps, so I
cannot be really sure what it was (but see also the end of this article).

As to Matijasevich's theorem, that concerns a *class* problem: Find an
algorithm that will decide, given *arbitrary* input representing an
polynomial in several variables, whether the polynomial assumes the value 0
for integer values of its variables (one of Hilbert's problems).
Matijasevich showed that no such algorithm exists.  In no way can it be
concluded that there exist *individual* undecidable Diophantine problems,
first because his proof suggests nothing of the kind, and secondly because
the supposition that there exist individual undecidable problems leads to a
contradiction, as I thought I had demonstrated convincingly.

One more try.  Let P be a predicate, defined (without loss of generality)
on the natural numbers.  We call P undecidable if there exists no total
recursive predicate A (decidable by an algorithm) such that, for all n,
P(n) iff A(n).  In other words, if P is undecidable, then for *all* total
recursive predicates A:

    it is *not* the case that for all n, P(n) iff A(n).

Now let P be an undecidable constant predicate, i.e, such that P(n) iff
Q, where Q has the form ``for all m, not R(m)''.  (Q is refutable by
counterexample.  Both F and individual Diophantine problems can
be expressed in this form.)  Let m stand for an arbitrary natural number,
and assume R(m) to hold.  So m gives a counterexample to Q, which thereby
is false.  Let FALSE be the constant predicate that is false for all
natural numbers.  So, for all n, P(n) = Q = false = FALSE(n).  This is a
contradiction, so the assumption, R(m), is false.  Since m was not
constrained, we have now:

    For all m, not R(m).

This proves that the truth of such problems is a consequence of their
undecidability (and so the assumption that they are undecidable is
contradictory).

The reference to non-standard models is, I think, a red herring (unless
non-standard notions of truth and falsehood are used:-).  Decidability is
not the same as *provability* in some formal logic.  It is conceivable that
F is proved independent of PA; this proof would be a proof of the truth of
F (by similar argumentation).  There is no contradiction here, since the
independence proof must have used reasoning not expressible in PA.  It is
also conceivable that F is proved non-provable in PA; then we would still
know nothing about the provability *per se* of F.

On rereading Lang's argument, I noticed it contains an application of
``Markov's Principle'' (MP).  Let Q be as above, and let the predicate R be
total and recursive.  Then MP states:

    If R(m) is not false for all m, then there exists an m
    such that R(m) is true.

The principle MP is usually not accepted by intuitionists.  Personally, I
find this the least offensive of classical principles rejected by
intuitionists.
-- 

     Lambert Meertens
     ...!{seismo,okstate,garfield,decvax,philabs}!lambert@mcvax.UUCP
     CWI (Centre for Mathematics and Computer Science), Amsterdam