Gödel's Proof

If Godel proved that no sufficiently complex system, i.e one that is capable of arithmetic, can prove its own consistency or if you assume the system is consistent there will always exist (infinitely many) true statements that cannot be deduced from its axioms, in what system did he prove it in? Is that system consistent? In what sense is the Godel statement true if not by proof? You'll have hundreds of questions popping in your mind every few minutes, and this short book does a very good job of tackling most of them. Godel numbering is a way to map all the expressions generated by the successive application of axioms back onto numbers, which are themselves instantiated as a "model" of the axioms. The hard part of it is to do this by avoiding the "circular hell". Russell in Principia Mathematica tried hard to avoid the kind of paradoxes like "Set of all elements which do not belong to the set". Godel's proof tries hard to avoid more complicated paradoxes like this : Let p = "Is a sum of two primes" be a property some numbers might possess. This property can be stated precisely using axioms, and symbols can be mapped to numbers. ( for e.g open a text file, write down the statement and look at its ASCII representation ). The let n(p) be the number corresponding to p. If n(p) satisfies p, then we say n(p) is Richardian, else not. Being Richardian itself is a meta-mathematical property r = "A number which satisfies the property described by its reverse ASCII representation". Note that it is a proper statement represented by the symbols that make up your axioms. Now, you ask if n(r) is Richardian, and the usual problem emerges : n(r) is Richardian iff it is not Richardian. This apparent conundrum, as the authors say, is a hoax. We wanted to represent arithmetical statements as numbers, but switched over to representing meta-mathematical statements as numbers. Godel's proof avoid cheating like this by carefully mirroring all meta-mathematical statements within the arithmetic, and not just conflating the two. Four parts to it. 1. Construct a meta-mathemtical formula G that represents "The formula G is not demonstratable". ( Like Richardian ) 2. G is demonstrable if and only if ~G is demonstrable ( Like Richardian) 3. Though G is not demonstrable, G is true in the sense that it asserts a certain arithmetical property which can be exactly defined. ( Unlike Richardian ). 4. Finally, Godel showed that the meta-mathematical statement "if `Arithmetic is consistent' then G follows" is demonstrable. Then he showed that "Arithmetic is consistent" is not demonstrable. It took me a while to pour over the details, back and forth between pages. I'm still not at the level where I can explain the proof to anyone clearly, but I intend to get there eventually. Iterating is the key. When I first came across Godel's theorem, I was horrified, dismayed, disillusioned and above all confounded - how can successively applying axioms over and over not fill up the space of all theorems? Now, I'm slowly recuperating. One non-mathematical, intuitive, consoling thought that keeps popping into my mind is : If the axioms to describe arithmetic ( or something of a higher, but finite complexity ) were consistent and complete, then why those axioms? Who ordained them? Why not something else? If it turned out that way, then the question of which is more fundamental : physics or logic would be resolved. I would be shocked if it were possible to decouple the two and rank them - one as more fundamental than the other. I'm very slowly beginning to understand why Godel's discovery was a shock to me. You see, I'm good at rolling with it while I'm working away, but deep down, I don't believe in Mathematical platonism, or logicism, or formalism or any philosophical ideal that tries to universally quantify. Kindle Edition - I would advise against the Kindle edition as reading anything with a decent bit of math content isn't a very linear process. Turning pages, referring to footnotes and figures isn't easy on the Kindle.

I remember my excitement when I read the first edition of this little gem back in 1999 (actually it was its Turkish translation). Being a young student of mathematics, it was impossible to resist reading a popular and clear account of maybe the most important theorem related to the fundamentals of axiomatic systems. After that came Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid which introduced more questions related to symbolic logical reasoning, artificial intelligence, cognitive science, and the consequences of Gödel's work in those ares. With that background and ten years after the second edition, it was truly an exciting second reading, a refresher that was both fun and putting lots of things into perspective. Hofstadter's foreword to this edition is a delight to read and ponder upon. On the other hand, I don't think this is a point strong enough to persuade most of the people who own the first edition anyway. But if you don't have the first edition and want a concise and clear explanation of what Gödel's work is all about then this book is definitely for you.

Bought this to get a little more insight into the philosophy behind Godel's proof, and it's exactly what I wanted. It's helpful to have read a more formal account, and be pretty well versed in the rules of inference in first and second order logic, but only for the purposes of coming to some deep insights on the development of computability theory. Very readable to a layperson who is interested in mathematical history, logic, computation, and philosophy of science. Also, nice sized font, so no squinting (paperback version).

I have been a big fan of the issue of formal mathematics and the theory of computation but I always missed a full grasping of the goedel theorem. The book presents the line along which Goedel moved: mostly formal systems and the most interesting issue of "calculating grammar" by powers of primes: an outstanding example, to me, was how using that instrument one could know whether a sentence was introduced by a "not" or not (in the case simply by checking if the figure expressing the formula was even or odd). In that way the full system of mathematics turned into a sort of a computer program that of course could not calculate every function. For that matter I came to wonder why the demonstration of goedel theorem could not be carried out simply by showing a formal system has the same power as a universal Turing machine and thus transferring to it the (much easier) results obtained on that issue - like for example to problem of the stop or the one of finding any semantic information in a program without actually executing it.

Early in the second decade of the twentieth century, Bertrand Russell and Alfred Whitehead published their monumental work "Principia Mathematica". In it, they claimed to have laid out the mathematical foundations on top of which the demonstration of all true propositions could be constructed. However, Kurt Gödel's milestone publication of 1931 exposed fundamental limitations of any axiomatic system of the kind presented in "Principia Mathematica". In essence, he proved that if any such axiomatic system is consistent (i.e., does not contain a contradiction) then there will necessarily exist undecidable propositions (i.e., propositions that can not be demonstrated) that are nevertheless true. The original presentation of Gödel's result is so abstract that it is accessible to only a few specialists within the field of number theory. However, the implications of this result are so far reaching that it has become necessary over the years to make Gödel's ideas accessible to the wider scientific community. In this book, Nagel and Newman provide an excellent presentation of Gödel's proof. By stripping away some of the rigor of the original paper, they are able to walk the reader through all of Gödel's chain of thought in an easily understandable way. The book starts by paving the way with a few preparatory chapters that introduce the concept of consistency of an axiomatic system, establish the difference between mathematical and meta-mathematical statements, and show how to map every symbol, statement and proof in the axiomatic system on to a subset of the natural numbers. By the time you reach the crucial chapter that contains Gödel's proof itself all ideas are so clear that you'll be able to follow every argument swiftly. The foreword by Douglas Hofstadter puts the text of this book into the context of twenty-first century thinking and points out some important philosophical consequences of Gödel's proof.

I believe this book taught me something.... however it was not what I was expecting. I have read mathematics book in the past like "Prime Obsession," "Unknown Quantity," and "The Code Book" all being extremely interesting and making me die to continue reading. I was hoping this book would be like those. I found the authors, both mathematicians, to be extremely fact-oriented, often taking 4 sentences to explain something where a single sentence would have sufficed. The footnotes, taking 1/3 of the bottom of every other page, exacerbate the situation. I wanted a book that would capture my imagination; this book merely reinforced all the facts I can learn on Youtube with the exception of one (below). The mention of Godel's proof is merely 3 or 4 pages that vaguely review the summary Godel arrived at. This vague summary was not satisfying to me. The reason I gave this 3 stars is because I learned about meta-mathematics. I also learned about systems where axioms are defined and how theorems in the system naturally follow from the axioms. Systems are everywhere, from playing chess to playing soccer and to driving. Fundamental rules are what keep these systems in flow. I liked how the authors dived into this a bit and because it is a short book I don't believe I wasted much time. The boring tone of this book reminded me of "GEB;" I suffered around 30 hours through GEB getting 70% done when I stopped reading, put the book away, and around 4 months later I gave it to a friend. I never heard from my friend or his thoughts on the book, I suppose he must have tossed it in the trash (which is fine with me).

I recommend this book for readers who want a clear and concise introduction to Godel's proof. The book will be especially useful for readers whose interests lie primarily in mathematics or logic, but who do not have very much prior knowledge of this important proof. Readers with broader interests, who would like to explore the larger implications of the proof for science or philosophy, may be disappointed that the book ends where it does. Godel's Incompleteness Theorem is cited by many scholars who question some of the fundamental assumptions of science. Just to give one example, it figures prominently in Robert Rosen's argument that a computing machine is an inadequate model for an organism. It is relevant to the question of whether everything that nature does can be understood as a computation, as Wolfram and many others have maintained. This book would have been more exciting if it had delved into a few of these discussions. Instead the authors wrap it up quickly with a brief "concluding reflections" chapter, as if they had a deadline to meet or a severe space limitation to conform to. That may leave some readers understanding the logic of the proof, but saying "so what?"

I redid my review (now July 2006) after your 50:50 votes on helpfulness. I think you needed more content to the review and less ebullience. So here it is... In the interim, I have read other treatments of Gödel's proof (including the Dover book of Gödel's article itself also with an introduction, Beyond Numeracy, The Advent of the Algorithm [ref below], and several others). What stands out in THIS book, though, is the extreme thoroughness of explaining to you the context in which Gödel was working at the time. This book is unique in its dedication to getting you to a concrete understanding of -- and appreciation for -- the background and context. In fact making sure you get the context appreciation takes up about 2/3rd's of the book! Of course the book is thorough on the Proof itself too. Is that part easy? No, it's still not. But you won't be left at all vague on what the proof is like. The only other book that is as good on the CONTEXT of Gödel's proof is The Advent of the Algorithm. The Advent of the Algorithm is also excellent on how others took, and "ran-with", Gödel's results. As for which edition of this book (Gödel's Proof) to get, the new addition has Hofstaddter's introduction. That intro adds value for sentimentality (if you should so find his story about his reading the book and his subsequent friendship with Nagel) and Hofstadter's own ebullience, but the book is virtually identical otherwise with its 1959 edition. It would be perfectly good -- you'll miss nothing -- if you bought a cheap 1959 edition. For a good complimentary book, get also The Advent of the Algorithm by David Berlinski (2000) ISBN 0 15 100338 6 or ISBN 0 15 601391 6 (pbk). You can read my review on that book too if you like.