Torkel Franzen on truth
in [Logic]
|
From: Alan Smaill on 6 Dec 2007 07:56 kleptomaniac666_(a)hotmail.com writes: > 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. I'm not convinced; according to Smullyan, the relation x^y = z is sigma-1 wrt PA. >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. -- Alan Smaill
From: george on 6 Dec 2007 12:29 On Dec 5, 5:27 pm, kleptomaniac6...(a)hotmail.com wrote: > 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. We can concede that. In the case of FLT, though, that will not help. You cannot algorithmically check the property because it has to apply to infinitely many triples. You can algorithmically refute it if it's false but you cannot algorithmically confirm it if it's true. > 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. No, NOT *so* to speak. That is incorrect. The correct way of speaking it, assuming you have an exponentiation operator, is An[n>2-->Axyz[~x^n+y^n=z^n] ]. IT IS *n* that must have or lack the property. You have to check the n. That means you have to check infinitely many x,y,z's. That is not algorithmically doable (yet). If anyone actually finds the algorithm then FLT will get proved from PA rather quickly. > To check that a number n is not involved as z is irrelevant; n doesn't need to be involved as z; n is involved as n.
From: george on 6 Dec 2007 13:04 In his book on GIT, the late TF (to his great credit) challenges > "... the mistaken idea that "Gödel's theorem states that > in any consistent system which is strong enough to > produce simple arithmetic there are formulas which > cannot be proved in the system, but which we can see to be true." > The theorem states no such thing. This forces us to ask, "Does Prof.Peter Smith know Prof.Daniel Isaacson?" Because Isaacson, TEACHING THIS STUFF RIGHT NOW ("Michaelmas term, 2007), flaunts his ignorance of this Torkelian perspective, lecturing, >> "This independence theorem was unprecedented. In the previous >> hundred years the independence of Euclid's fifth postulate had >> been established. Godel's result differs from this earlier one in >> two crucial ways. One was the technique used. The result concerning >> the fifth postulate was established by the construction of models. >> The Godel result is purely syntactic (exploiting Hilbert's insight). >> The other difference is even more fundamental. The fifth postulate >> is neither true nor false, per se. It is true in Euclidean geometry >> and false in non-Euclidean geometries. >>>>> The Godel sentence is demonstrably true, >>>>> though not demonstrable in the system for which it is constructed. Jeezus. This person is a professor. I failed to get my Ph.D. at UNC and have been completely unemployable since. I just got fired from what will probably be my last computer job after less than 5 months. My philosophy degree is a bachelor's. But I know that what this professor has just said is utter bullshit. The Godel sentence, like the parallel postulate, is true in the standard model and false in non-standard ones. For anybody to call G "true" is even more outrageous than usual, because at the relevant cardinality (aleph-0), there is, up to isomorphism, ONLY ONE model in which G is true -- it is false in ALL the others! Saying of any sentence that is "demonstrably" true, in SOME system, without first imposing relevant constraints on the kind of system, is even more idiotic -- obviously every sentence s is "demonstrably true" in the system S whose only axiom is s.
From: Peter_Smith on 6 Dec 2007 17:54 On 6 Dec, 18:04, george <gree...(a)cs.unc.edu> wrote: > In his book on GIT, the late TF (to his great credit) challenges > > > "... the mistaken idea that "Gödel's theorem states that > > in any consistent system which is strong enough to > > produce simple arithmetic there are formulas which > > cannot be proved in the system, but which we can see to be true." > > The theorem states no such thing. > > This forces us to ask, "Does Prof.Peter Smith know Prof.Daniel > Isaacson?" Oh? Why does it force us to ask that?? Actually I do know Dan, and of course we'd both agree with Torkel Franzen's point. (It is one anyone teaching this stuff stresses: sure, we need to assume that the system we are dealing with is indeed consistent if we are get to see that the canonical Gödel sentence is true on the standard interpretation.) > Because Isaacson, TEACHING THIS STUFF RIGHT NOW ("Michaelmas > term, 2007), flaunts his ignorance of this Torkelian perspective, > lecturing, > >>>>> The Godel sentence is demonstrably true, > >>>>> though not demonstrable in the system for which it is constructed. Hold on, hold on. You've rather ripped this out of context from Dan's lecture notes. He two paragraphs earlier introduces the assumption that we are dealing with systems of arithmetic S which are *sound* (and hence consistent). And on *that* assumption, which I take to be still in force when we comments on the proof he sketches, the canonical Gödel sentence will indeed be true on the standard interpretation.
From: Pierre Asselin on 6 Dec 2007 22:38
george <greeneg(a)cs.unc.edu> wrote: > On Dec 5, 5:27 pm, kleptomaniac6...(a)hotmail.com wrote: > > 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. > No, NOT *so* to speak. That is incorrect. > The correct way of speaking it, assuming you have an exponentiation > operator, is > An[n>2-->Axyz[~x^n+y^n=z^n] ]. IT IS *n* that must have or lack the > property. You have to check the n. That means you have to check > infinitely many x,y,z's. That is not algorithmically doable (yet). > If anyone > actually finds the algorithm then FLT will get proved from PA rather > quickly. But you can eliminate the inner quantifiers if you use tuples: every integer has the property that { if you decode a quadruple <x,y,z,n> from it, then n<3 or x^n + y^n != z^n } -- pa at panix dot com |