New essay on Goedel's Incompleteness Theorem
in [Logic]
|
Prev: Solutions manual to Mechanical Behavior of Materials, 3E Norman E Dowling
Next: Editor of Physical Review A, Dr Gordon W.F. Drake does WRONG subtraction of 8th Class mathematics.
From: Aatu Koskensilta on 1 Oct 2009 10:28 Marshall <marshall.spight(a)gmail.com> writes: > Or is the oft-recommended Franzen one at all accessible? Very accessible. Franz�n writes with extraordinary clarity. I don't recall what there's on the diagonal lemma in _G�del's Theorem_ but the presentation of the incompleteness theorems in _Inexhaustibility_ is one of the best in print, and certainly includes a discussion of the diagonal lemma. I'm not sure how familiar you're with the recursion theorem, but reflecting on that result may shed some light on the diagonal lemma... -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon mann nicht sprechen kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Daryl McCullough on 1 Oct 2009 11:12 Marshall says... > >On Sep 30, 1:26=A0pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) >wrote: >> >> Look, to refresh your memory, here are the facts about G: > >I have some questions about the below. > > >> 2. Every formula of arithmetic has an associated Godel code, >> which is a natural number. If Phi is a formula, then let #Phi >> be its Godel code. > >This associated code is arbitrary, is it not? Presumably >there are many such encodings. If I understand correctly, >all that is necessary is that we have a way, given Phi, >to calculate #Phi, and given #Phi, a way to calculate Phi, >yes? Yes, the only requirement is that it be possible to compute #Phi given Phi (and that #Phi can be uniquely decoded to give Phi). >> 3. There is a provability predicate Pr for Peano Arithmetic with the >> property that for any formula Phi, >> If Phi is provable from the axioms of Peano Arithmetic >> then >> Pr(#Phi) is true >> Conversely, if Phi is not provable from the axioms of >> Peano Arithmetic, then >> ~Pr(#Phi) is true. > >Is this supposed to be: > > If Phi is provable from the axioms of Peano Arithmetic > then > Pr(Phi) is true > Conversely, if Phi is not provable from the axioms of > Peano Arithmetic, then > ~Pr(Phi) is true. > >Otherwise I don't see how the provability relation could >be applied to a natural number. A natural number in the >language of PA would be a term, not a formula, right? The provability relation is a formula of arithmetic. It applies to natural numbers. Pr(x) is interpreted to mean "x is the Godel code of a provable statement of Peano Arithmetic". >> 4. For every formula Phi of arithmetic, there is a corresponding >> formula G with the property that PA proves >> >> G <-> Phi[#G] > >Other than the fact that for every Phi there is a G, where >does G come from? How do we figure out what G is >given Phi? Let's define an operation on formulas called "diagonalization". It's defined as follows: If Phi is any formula, then the diagonalization of Phi is the formula Phi' resulting from replacing all the free variables of Phi by the numeral for the Godel code of Phi. For example, if Phi is the formula x+0 = x And the Godel code of Phi is 42, then the diagonalization of Phi is the formula 42 + 0 = 42 Now, let D(x,y) be the formalization in arithmetic of the relation "x is the Godel number of some formula Phi, and y is the Godel number of the diagonalization of Phi". Next, if Phi(x) is any formula of arithmetic with one free variable, x, then let G0 be the formula forall x, D(y,x) -> Phi(x) Let #G0 be the Godel code of G0. Finally, let G be the diagonalization of G0. This means that G is constructed from G0 by replacing its free variables (only y is free in G0) by the numeral of the Godel code of G0. So G is the formula forall x, D(#G0, x) -> Phi(x) Now, from the way that D was defined, D(#G0,x) is true if and only if x is the Godel number of the diagonalization of G0. But G is the diagonalization of G0. So D(#G0,x) is true if and only if x = the Godel code of G, which we denote by #G. So forall x, D(#G0,x) -> Phi(x) <-> forall x, (x = #G) -> Phi(x) <-> Phi(#G) -- Daryl McCullough Ithaca, NY
From: Scott H on 1 Oct 2009 17:44 On Oct 1, 10:19 am, Marshall <marshall.spi...(a)gmail.com> wrote: > The symptoms you describe are much too serious to leave > untreated, or ineffectively treated. Get help immediately, > and as often as necessary. Find a new doctor today; nothing > else you were planning is as important. I appreciate your encouragement -- not just yours, but Aatu's and David's as well. However, no medication ever seems to help me, even over extended periods of time, and I have a personal preference against medication regimens due to the ethical problem of genetic inheritance. Modern psychotropics are somewhat dangerous, too, as they work against the 'pleasure chemical' in the brain and can cause both movement disorders and loss of gray matter. Some of these auditory hallucinations are repetitions of insults made at me in childhood. I think what I need is more positive reinforcement for the right actions. When I get home, I'll update my essay to indicate the possibility that G, G', G'', ... are identical statements. I'll also use equivalence classes to clarify the notion of endless reference. Either way, we will only need G, G', and G'' to ask whether G is Platonically true, and I've devoted the section 'On the Possible Existence of Supernatural Numbers' to the examination of this question.
From: Tim Little on 1 Oct 2009 23:56 On 2009-10-01, Scott H <zinites_page(a)yahoo.com> wrote: > I've deliberately left it an open question whether G, G', G'', > ... are the same statement. So what? I (and other posters) have showed that it is *not* an open question. The interpretation of G' as a statement *is* G, by definition. The numerical referent of G' *is* therefore G', by construction. You can call it G'', G''', or "the Goedel number formerly known as Prince" for all it matters. It is the same number as G'. - Tim
From: Aatu Koskensilta on 2 Oct 2009 04:07
Nam Nguyen <namducnguyen(a)shaw.ca> writes: > You seem to have a tendency to interpret things _out of context_, > for the worse! We all need a hobby. > Scott seemed so _desperate_ to the point he would "attack" people > pointlessly. I just tried to console him that should it be the case > only he and nobody else would see the (correct) truth, others don't > have to see it and so he wouldn't need to be frustrated/desperate. I think being frustrated or desperate would be a perfectly natural and appropriate reaction in such a situation, and it seems unlikely merely contemplating the impersonal nature of mathematical truth would be of much consolation. In my comment I had in mind in addition to your reassuring consolation of Scott also various more or less romantic but historically inaccurate utterances by you about G�del, Brouwer, Einstein etc. over the years. Those who feel their discoveries have been unjustly ignored, their cogent arguments met with incredulous stares and silence, and so on, often find comfort in the idea that various famous thinkers have in the past had to battle stagnant orthodoxy and mindless regurgitation of received wisdom, all alone, armed with nothing but their unwavering conviction and superb intellect, understood and appreciated only by later generations -- alas, the historical facts do not usually support anything of the sort. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus |