Torkel Franzen on truth
in [Logic]
|
From: kleptomaniac666_ on 4 Dec 2007 20:32 On Dec 5, 12:59 am, george <gree...(a)cs.unc.edu> wrote: > On Dec 3, 7:00 pm, kleptomaniac6...(a)hotmail.com wrote: > > > I don't think it has been proved that FLT is independent from the > > axioms of PA, if that's what you mean. > > I do. It definitely has. It is actually an old result, like over 40 > years. > [27] Shepherdson, John C., A non-standard model for a free variable > fragment > of number theory, Bulletin de l'Academie Polonaise des Sciences. Serie > des > Sciences Mathematiques, Astronomiques et Physiques, 12, 1964, 79-86. > > > That would be quite some result. > > Do you mean that it has been shown that the proof of FLT as > > given by Wiles cannot be formalised in PA? > > Well, indirectly. > It used to be in vogue to construct nonstandard models of PA. > Back when it was (in the early '60s), Shepherdson constructed > one in which FLT failed for the *first*/simplest case (cubic). > This doesn't have any direct relevance to the TRW proof, but it > does imply independence from PA. I'm almost sure (though my whole > point is, > this hasn't been made *clearly* explicit) it's not independent of ZFC. I thought Harvey Friedman suspects that FLT can be proved in PA? Also, would it not be the case that independence from PA would imply that FLT is true? As FLT can be expressed as a pi-1 sentence.
From: george on 5 Dec 2007 10:44 On Dec 4, 8:32 pm, kleptomaniac6...(a)hotmail.com wrote: > I thought Harvey Friedman suspects that FLT can be proved in PA? OK, I was wrong. I was reading this (too fast) from a paper by Kaye on Tennenbaum's theorem: > As for independence results, Kemeny did produce a model > that addressed some questions of independence in 1958 (MR0098685). > As one in hindsight would expect, Kemeny's model was shown soon > afterwards to fail to satisfy any particularly interesting induction axioms > for arithmetic (Gandy (MR0098686)). To my mind, the highlight of this > period of building recursive models for the purposes of independence results > was the results of the early 1960s by Shepherdson, who, using algebraic > methods, produced beautiful nonstandard models of quantifier-free arithmetic > in which he showed number theoretic results such as the infinitude of primes > and Fermat's Last Theorem (in fact, for exponent 3) are false > (MR0161798) [that was the reference I cited] This was apparentely a nonstandard model of "quantifier-free arithmetic", whatever that is. Presumably, after you put the quantifiers and a full first- order induction axiom back in, this model is not adequate as a model of PA. But I didn't see that the first time. Apparently this model was also recursive, which of course a nonstandard model of PA could not be. > By this time Tennenbaum's theorem was already well known, > and Shepherdson and others were certainly aware of the limitations > of this approach. Limitations apparently preventing any such earth-shaking indepenence results as I had been expecting. > Also, would it not be the case that independence from PA would imply that > FLT is true? > As FLT can be expressed as a pi-1 sentence. I do not see how to do that (express FLT as a Pi-1 sentence in the language of PA), since the language of PA does not include an exponentiation operator.
From: george on 5 Dec 2007 10:49 On Dec 4, 8:21 pm, tc...(a)lsa.umich.edu wrote: > No, Shepherdson isn't studying PA in that paper. It is still open whether > FLT is independent of PA. OK. I was reading too fast. From http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennhistory which includes this paragraph -- > To my mind, the highlight of this period of building recursive models for > the purposes of independence results was the results of the early 1960s > by Shepherdson, who, using algebraic methods, produced beautiful > nonstandard models of quantifier-free arithmetic in which he showed > number theoretic results such as the infinitude of primes and Fermat's > Last Theorem (in fact, for exponent 3) are false (MR0161798). Apparently(in hindsight),this was a recursive model of a weaker(than PA)theory. What was (is) needed is a non-recursive/non- standard model of PA.
From: Alan Smaill on 5 Dec 2007 11:29 george <greeneg(a)cs.unc.edu> writes: > On Dec 4, 8:32 pm, kleptomaniac6...(a)hotmail.com wrote: >> Also, would it not be the case that independence from PA would imply that >> FLT is true? >> As FLT can be expressed as a pi-1 sentence. > > I do not see how to do that (express FLT as a Pi-1 sentence in the > language of PA), since the language of PA does not include an > exponentiation operator. the expressibility of exponentiation in PA was done by Goedel in his proof of incompleteness (and it's serious work). Not sure if this would allow a pi-1 formulation, though. -- Alan Smaill
From: kleptomaniac666_ on 5 Dec 2007 17:27
On Dec 5, 4:29 pm, Alan Smaill <sma...(a)SPAMinf.ed.ac.uk> wrote: > george <gree...(a)cs.unc.edu> writes: > > On Dec 4, 8:32 pm, kleptomaniac6...(a)hotmail.com wrote: > >> Also, would it not be the case that independence from PA would imply that > >> FLT is true? > >> As FLT can be expressed as a pi-1 sentence. > > > I do not see how to do that (express FLT as a Pi-1 sentence in the > > language of PA), since the language of PA does not include an > > exponentiation operator. > > the expressibility of exponentiation in PA > was done by Goedel in his proof of incompleteness (and it's serious work). > Not sure if this would allow a pi-1 formulation, though. > > -- > Alan Smaill I thought (though I could be wrong) that there was a general principle that any statement in the language of first order arithmetic which took the form: every positive integer has the property p, where p is a property that can be algorithmically checked can be expressed as a pi-1 sentence. In the case of FLT, if every positive integer n had the property that it was not the z in a counterexample to FLT, so to speak. To check that a number n is not involved as z in a counterexample to FLT, all that is required is that one check if n is a perfect power where the power is higher than 2, and then check all the pairs of perfect powers which are less than z, of which there will be finitely many. Obviously, propositions like "this diophantine equation has finitely many solutions" would not take this form. It cannot be shown false by counterexample. |