bill@milford.UUCP (bill) (10/10/85)
In the recently published _The_Beauty_of_Doing_Mathematics_, Serge Lang states (mini-book-review: in general this book is very excellent, especially as a model of a class of the "Math-for-poets"-type) "... 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? I remember arguing some years ago with a distinguished Number Theorist who "proved" that the Riemann Conjecture could never be proven undecidable for the same reason (with almost identically the same words). I tried to distinguish between "Truth" (capital T) and algorithms establishing that Truth, to no avail; I did gain some ground with the idea that undecidability is a higher order predicate which could not be used in such Number Theoretic "proofs", but the Professor continued to insist that undecidability results would somehow "prove" these conjectures. Its well know that in a certain sense the Godelian sentences must be false, but this does not negate that they cannot be proven or disproven within the theory under question. 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"?
lambert@boring.UUCP (10/12/85)
> "... 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
bill@milford.UUCP (bill) (10/15/85)
> > "... 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.
lambert@boring.UUCP (10/18/85)
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