paulv@mcvax.UUCP (Paul Vitanyi) (02/08/84)
***** QUOTE net.ai 365 ***** From: Charlie Crummer <crummer@AEROSPACE> Fortunately (or unfortunately) puzzles like Fermat's Last Theorem, Goldbach's conjecture, the 4-color theorem, and others are not in the same class as the geometric trisection of an angle or the squaring of a circle. The former class may be undecidable propositions (a la Goedel) and the latter are merely impossible. Since one of the annoying things about undecidable propositions is that it cannot be decided whether or not they are decidable, (Where are you, Doug Hofstader, now that we need you?) people seriously interested in these candidates for undecidablilty should not dismiss so-called theorem provers like A. Arnold without looking at their work. Is the 4-color theorem undecidable or not? --Charlie ***** UNQUOTE ***** Fermat's Last Theorem, Goldbach's conjecture, the Four Color Theorem (or Conjecture) and others of that type which can be disproved by a single counterexample can not be undecidable propositions in mathematics. Suppose Fermat's Last Theorem were undecidable. Then there cannot be a counterexample (four positive integers x,y,z > 0 and n > 2) such that x**n + y**n = z**n. Consequently Fermat's Last Theorem is true. Thus the assumption of undecidability of this individual statement implies that the statement is true. The assumption that Fermat's Last Theorem is undecidable and false is a contradiction. The assumption that Fermat's Last Theorem is decidable does not contradict either the falsehood or the truth of the Theorem. Paul Vitanyi
mcmillan@eosp1.UUCP (John McMillan) (02/13/84)
Paul Vitanyi has committed (it seems to me), a simple error of logic. To Paraphrase him: Suppose Fermat's last theorem were undecideable; then there can be no counter examples; in which case the theorem is true. If it is true, it is not undecideable. (End paraphrase) Please note that TRUE and PROVED are two entirely different things. First, how can we tell whether there are no counterexamples? If we can PROVE there are no counterexamples, we have proved the theorem. If we merely fail to find counter examples, we DON'T KNOW THERE ARE NO COUNTEREXAMPLES. Since we are dealing with an infinite set (integers), there is no way to exhaustively search the set, looking for counterexamples, without rogorously proving the theorem. Now in addition, we must take into account what Goedel's theorem proved for the set of integers and all sets embedding them -- it is possible for a theorem to be true, and yet for the rigorous logical system containing the theorm to be unable to formally prove the theorem. One might think, in such cases, that an axiom could be added to the system so that all such true threorems can be proved, but Goedel showed that an inifinite number of axioms would be required. - Toby Robison allegra!eosp1!robison decvax!ittvax!eosp1!robison princeton!eosp1!robison (NOTE! NOT McMillan; Robison.)
ka@hou3c.UUCP (Kenneth Almquist) (02/15/84)
Paul writes, "Suppose Fermat's Last Theorem were undecidable. Then...". That should really be "Suppose it has been proved that Fermat's last theorem is undecidable," because you have to assume that the theorem is *known* to be undecidable before you can base further arguments on its undecidability. In other words, isn't it posssible that no counter- examples to Fermat's last theorem exists, but that it is impossible to prove that none exist using the current axioms of number theory? Kenneth Almquist
minas@foxvax1.UUCP (P.C. Minasian ) (02/16/84)
Could someone please help out an ignorant soul by posting a brief (if that is, indeed, possible!) explanation of what Fermat's last theorem states as well as what the four-color theorem is all about. I'm not looking for an explanation of the proofs, but, simply, a statement of the propositions. Thanks! -phil minasian decvax!genrad!wjh12!foxvax1!minas
MJackson.Wbst@PARC-MAXC.ARPA (03/01/84)
Fermat's Last Theorem:
is the assertion that
A^N + B^N = C^N
has no solution in integers for N > 2. (For N = 2, of course, all the
well-known right triangles like [3,4,5] are solutions.)
The Four-Color Theorem:
states that any planar map can be colored so that no two adjacent
regions are the same color using no more than four different colors.
(Regions must be connected; "adjacent" means having a common boundary of
finite length, i.e. not just touching at a point.
The latter was shown to be true by two mathematicians at the University
of Illinois, using a combination of traditional mathematical reasoning
and computer-assisted analysis of a large set of graphs. An article
describing the proof can be found in a back issue of /Scientific
American/.
The former appears in a manuscript by Fermat, with a marginal notation
to the effect that he had found a slick proof, but didn't have enough
space to write it down. This was discovered after his death, of course.
Most mathematicians believe the theorem to be true, and most do not
think Fermat is likely to have found a valid proof, but neither
proposition has been proved beyond question.
Mark