Ron, (or anyone who can answer the simple question) The "essay" that started off this thread .... did you write that Ron ?
I ask because I have been following up "appropriate use of Godel" in philosophical debate, for various reasons, not least because I've just re-read Dennett's Dangerous Idea, and recalled some strong citations of Godel (from Hofstader, Smullyan, Lem, Penrose amongst others). For some reason I thought this post was a cut-and-paste from a piece by Franzen. I now see it cites Franzen, but the piece itself is not (explicitly) attributed. I'd like to cite it in a blog post. Regards Ian On Fri, Aug 22, 2008 at 3:38 PM, Ron Kulp <[EMAIL PROTECTED]> wrote: > > Gödel's Theorem > > > 20 Aug 2007 21:31 > > ________________________________ > > A much-abused result in mathematical logic > <http://cscs.umich.edu/~crshalizi/notebooks/mathematical-logic.html> , > supposed by many authors who don't understand it to support their own favored > brand of rubbish, and even subjected to surprisingly rough handling by some > who really should know better. > > Let me start by trying to make clear just what the theorem states, before > going on to poke at the two most common abuses. Gödel's theorem is a result > about axiomatic systems, which is already a source of some confusion. In > ordinary educated speech, axioms are undubitable truths; for mathematicians, > they are propositions it is convenient or amusing to start from. An axiomatic > system consists of some undefined terms, a bunch of axioms referring to those > terms and partially describing their properties, and a rule or rules for > deriving new propositions from already existing propositions. There are > really two points to setting up an axiomatic system. First, it's a very > compact description of the whole field of propositions derivable from the > axioms, so large bodies of math can be compressed down into a very small > compass. Second, because it's so abstract, the system lets us derive all and > only the results which follow from things having the formal properties > specified by the axioms. One can set up axiomatic systems describing, say, > kinship networks, and then you get results which depend only on having two > parents, one of each sex, and so are applicable to anything with that formal > property; and similarly for axiomatic geometry, algebra, etc., etc. An > axiomatic system is said to be consistent if, given the axioms and the > derivation rules, we can never derive two contradictory propositions; > obviously, we want our axiomatic systems to be consistent. > > One of the first modern axiomatic systems was a formalization of simple > arithmetic (adding and multiplying whole numbers) by the great logician > Giuseppe Peano, called Peano arithmetic. What Kurt Gödel did was to show that > every syntactically correct proposition in Peano arithmetic can be > represented by a unique integer, called its Gödel number. (The trick is to > replace each symbol in the proposition, including numerals, by a different > string of digits. If we represent "1" by 01, "2" by "02", "+" by 10 and "=" > by "11", then the Gödel number of "1+1=2" is 0110011102. Gödel numbers tend > to be huge.) This lets us write down, unambiguously, propositions which are > about propositions. In particular, we can write down self-referential > propositions, ones which include their own Gödel number. (This usually won't > work if numerals are represented by themselves, of course.) From here, Gödel > showed that, either the system is inconsistent (horrors!), or there are true > propositions which can't be reached from the axioms by applying the > derivation rules. The system is thus incomplete, and the truth of those > propositions is undecidable (within that system). Such undecidable > propositions are known as Gödel propositions or Gödel sentences. Nobody knows > what the Gödel sentences for Peano arithmetic are, though people have their > suspicions about Goldbach's conjecture (every even number is the sum of two > prime numbers). [Update, June 2005: Actually, that's wrong. Wolfgang Beirl > <http://yolanda3.dynalias.org/tsm/tsm.html> has pointed out to me that > Goodstein's Theorem <http://en.wikipedia.org/wiki/Goodstein%27s_theorem> is > a result about natural numbers which is undecidable within Peano arithmetic, > but provable within stronger set-theoretic systems. And it's actually a neat > theorem, with no self-referential weirdness!] > > So far we've just been talking about Peano arithemtic, but now comes the > kicker. Results about an axiomatic system apply to any bunch of things which > satisfy the axioms. There are an immense number of other axiomatic systems > which either include Peanese numbers among their basic entities, or where > such things can be put together; they either have numbers, or can construct > them. (These systems are said to provide models of Peano arithmetic.) It > follows that these systems, too, contain undecidable propositions, and are > incomplete. > > There are two very common but fallacious conclusions people make from this, > and an immense number of uncommon but equally fallacious errors I shan't > bother with. The first is that Gödel's theorem imposes some of profound > limitation on knowledge, science, mathematics. Now, as to science, this > ignores in the first place that Gödel's theorem applies to deduction from > axioms, a useful and important sort of reasoning, but one so far from being > our only source of knowledge it's not even funny. It's not even a very common > mode of reasoning in the sciences, though there are axiomatic formulations of > some parts of physics. Even within this comparatively small circle, we have > at most established that there are some propositions about numbers which we > can't prove formally. As Hintikka says, "Gödel's incompleteness result does > not touch directly on the most important sense of completeness and > incompleteness, namely, descriptive completeness and incompleteness," the > sense in which an axiom systems describes a given field. In particular, the > result "casts absolutely no shadow on the notion of truth. All that it says > is that the whole set of arithmetical truths cannot be listed, one by one, by > a Turing machine." Equivalently, there is no algorithm which can decide the > truth of all arithmetical propositions. And that is all. > > This brings us to the other, and possibly even more common fallacy, that > Gödel's theorem says artificial intelligence is impossible, or that machines > cannot think. The argument, so far as there is one, usually runs as follows. > Axiomatic systems are equivalent to abstract computers, to Turing machines, > of which our computers are (approximate) realizations. (True.) Since there > are true propositions which cannot be deduced by interesting axiomatic > systems, there are results which cannot be obtained by computers, either. > (True.) But we can obtain those results, so our thinking cannot be adequately > represented by a computer, or an axiomatic system. Therefore, we are not > computational machines, and none of them could be as intelligent as we are; > quod erat demonstrandum. This would actually be a valid demonstration, were > only the pentultimate sentence true; but no one has ever presented any > evidence that it is true, only vigorous hand-waving and the occasional > heartfelt assertion. > > Gödel's result is of course quite interesting, if you're doing mathematical > logic, and it even has some importance for that odd little specialization of > logic, the theory of computation > <http://cscs.umich.edu/~crshalizi/notebooks/computation.html> . (It is > intimately related to the halting problem, for instance.) It also makes a > fine piece of general mathematical culture; but it doesn't shake the > foundations of the house of intellect, or exalt us above all else that greps. > > (Thanks to Jakub Jasinski for politely pointing out an embarrassing error in > an earlier version.) > > Recommended: > > * Michael Arbib, Brains, Machines and Mathematics [A good sketch of the > proof of the theorem, without vaporizing] > * George S. Boolos and Richard C. Jeffrey, Computability and Logic > [Textbook, with a good discussion of incompleteness results, along with many > other things. Intended more for those interested in the logical than the > computational aspects of the subject - they do more with model theory than > with different notions of computation, for instance - but very strong all > around.] > * Torkel Franzen, Gödel's on the net > <http://www.sm.luth.se/~torkel/eget/godel.html> [Gentle debunking of many of > the more common fallacies and misunderstandings] > * Jaakko Hintikka, The Principles of Mathematics Revisited [Does a nice > job of defusing Gödel's theorem, independently of some interesting ideas > about logical truth and the like, about which I remain agnostic. My > quotations above are from p. 95] > * Dale Myers, Gödel's Incompleteness Theorem > <http://www.math.hawaii.edu/~dale/godel/godel.html> [A very nice web page > that builds slowly to the proof] > * Roger Penrose, The Emperor's New Mind [Does a marvelous job of > explaining what goes into the proof - his presentation could be understood by > a bright high school student, or even an MBA > <http://cscs.umich.edu/~crshalizi/notebooks/management.html> - but then > degenerates into an unusually awful specimen of the standard argument against > artificial intelligence <http://cscs.umich.edu/~crshalizi/notebooks/ai.html> ] > * Willard Van Orman Quine, Mathematical Logic [Proves a result which is > actually somewhat stronger than the usual version of Gödel's theorem in the > last chapter, which however adds no philosophical profundity; review > <http://cscs.umich.edu/~crshalizi/reviews/mathematical-logic/> ] > * Raymond Smullyan, Gödel's Incompleteness Theorems [A mathematical > textbook, not for the faint at heart, though the first chapter isn't so bad; > one of the few to notice the strength of Quine's result] > > To read: > > * John C. Collins, "On the Compatibility Between Physics and > Intelligent Organisms," physics/0102024 > <http://arxiv.org/abs/physics/0102024> [Claims to have a truly elegant > refutation of Penrose] > * Rebecca Goldstein, Incompleteness [Biography of Gödel, which seems to > actually understand the math] > * Ernest Nagel and James R. Newman, Gödel's Proof [Thanks to S. T. > Smith for the recommendation] > * Mario Rabinowitz, "Do the Laws of Nature and Physics Agree About What > is Allowed and Forbidden?" physics/0104001 > <http://arxiv.org/abs/physics/0104001> > > > > Moq_Discuss mailing list > Listinfo, Unsubscribing etc. > http://lists.moqtalk.org/listinfo.cgi/moq_discuss-moqtalk.org > Archives: > http://lists.moqtalk.org/pipermail/moq_discuss-moqtalk.org/ > http://moq.org.uk/pipermail/moq_discuss_archive/ > Moq_Discuss mailing list Listinfo, Unsubscribing etc. http://lists.moqtalk.org/listinfo.cgi/moq_discuss-moqtalk.org Archives: http://lists.moqtalk.org/pipermail/moq_discuss-moqtalk.org/ http://moq.org.uk/pipermail/moq_discuss_archive/
