Gödel's Proof

By Ernest Nagel, James R Newman and Douglas R. Hofstadter

An accessible explanation of Kurt Gödel’s groundbreaking work in mathematical logic: “An excellent nontechnical account.” —Bulletin of the American Mathematical Society
 
In 1931 Kurt Gödel published his fundamental paper, “On Formally Undecidable Propositions of Principia Mathematica and Related Systems.” This revolutionary paper challenged certain basic assumptions underlying much research in mathematics and logic. Gödel received public recognition of his work in 1951 when he received the first Albert Einstein Award for achievement in the natural sciences—perhaps the highest award of its kind in the United States. The award committee described his work in mathematical logic as “one of the greatest contributions to the sciences in recent times.”
 
However, few mathematicians of the time were equipped to understand the young scholar’s complex proof. Ernest Nagel and James Newman provide a readable and accessible explanation to both scholars and non-specialists of the main ideas and broad implications of Gödel's discovery. It offers every educated person with a taste for logic and philosophy the chance to understand a previously difficult and inaccessible subject.
 
New York University Press is proud to publish this special edition of one of its bestselling books. With a new foreword by Douglas R. Hofstadter, Pulitzer Prize-winning author of Gödel, Escher, Bach, who also updated the text, this book will be of interest to students, scholars, and professionals in the fields of mathematics, computer science, logic and philosophy, and science.

• Language: English
• Publisher: Open Road Integrated Media
• Release date: Oct 1, 2001
• ISBN: 9780814758014

Book preview

Thank you for buying this ebook, published by NYU Press.

Sign up for our e-newsletters to receive information about forthcoming books, special discounts, and more!

Sign Up!

About NYU Press

A publisher of original scholarship since its founding in 1916, New York University Press Produces more than 100 new books each year, with a backlist of 3,000 titles in print. Working across the humanities and social sciences, NYU Press has award-winning lists in sociology, law, cultural and American studies, religion, American history, anthropology, politics, criminology, media and communication, literary studies, and psychology.

Gödel’s Proof

In 1931 Kurt Gödel published a revolutionary paper—one that challenged certain basic assumptions underlying much traditional research in mathematics and logic. Today his exploration of terra incognita has been recognized as one of the major contributions to modern scientific thought.

Here is the first book to present a readable explanation to both scholars and non-specialists of the main ideas, the broad implications of Gödel’s proof. It offers any educated person with a taste for logic and philosophy the chance to gain genuine insight into a previously inaccessible subject.

In this new edition, Pulitzer prize–winning author Douglas R. Hofstadter has reviewed and updated the text of this classic work, clarifying ambiguities, making arguments clearer, and making the text more accessible. He has also added a new Foreword, which reveals his own unique personal connection to this seminal work and the impact it has had on his own professional life, explains the essence of Gödel’s proof, and shows how and why Gödel’s proof remains relevant today.

Gödel’s Proof

Revised Edition

by

Ernest Nagel

and

James R. Newman

Edited and with a New Foreword

by Douglas R. Hofstadter

NEW YORK UNIVERSITY PRESS

New York and London

Copyright © 2001 by New York University

All rights reserved

Library of Congress Cataloging-in-Publication Data

Nagel, Ernest, 1901–

Gödel’s proof / by Ernest Nagel and James R. Newman.—Rev. ed. / edited

and with a new foreword by Douglas R. Hofstadter.

p. cm.

Includes bibliographical references and index.

ISBN 0-8147-5816-9 (acid-free paper)

1. Gödel’s theorem. I. Newman, James Roy, 1907–1966. II. Hofstadter,

Douglas R., 1945– III. Title.

QA9.65 .N34 2002

511.3—dc21       2001044481

New York University Press books are printed on acid-free paper,

and their binding materials are chosen for strength and durability.

Manufactured in the United States of America

10 9 8 7 6 5 4 3 2 1

to

Bertrand Russell

Contents

Foreword to the New Edition by Douglas R. Hofstadter

Acknowledgments

I Introduction

II The Problem of Consistency

III Absolute Proofs of Consistency

IV The Systematic Codification of Formal Logic

V An Example of a Successful Absolute Proof of Consistency

VI The Idea of Mapping and Its Use in Mathematics

VII Gödel’s Proofs

A Gödel numbering

B The arithmetization of meta-mathematics

C The heart of Gödel’s argument

VIII Concluding Reflections

Appendix: Notes

Brief Bibliography

Index

Foreword to the New Edition

by Douglas R. Hofstadter

In August 1959, my family returned to Stanford, California, after a year in Geneva. I was fourteen, newly fluent in French, in love with languages, entranced by writing systems, symbols, and the mystery of meaning, and brimming with curiosity about mathematics and how the mind works.

One evening, my father and I went to a bookstore where I chanced upon a little book with the enigmatic title Gödel’s Proof. Flipping through it, I saw many intriguing figures and formulas, and was particularly struck by a footnote about quotation marks, symbols, and symbols symbolizing other symbols. Intuitively sensing that Gödel’s Proof and I were fated for each other, I knew I had to buy it.

As we walked out, my dad remarked that he had taken a philosophy course at City College of New York from one of its authors, Ernest Nagel, after which they had become good friends. This coincidence added to the book’s mystique, and once home, I voraciously gobbled up its every word. From start to finish, Gödel’s Proof resonated with my passions; suddenly I found myself obsessed with truth and falsity, paradoxes and proofs, mappings and mirrorings, symbol manipulation and symbolic logic, mathematics and metamathematics, the mystery of creative leaps in human thinking, and the mechanization of mentality.

Soon thereafter, my dad informed me that by chance he had run into Ernest Nagel on campus. Professor Nagel, normally at Columbia, happened to be spending a year at Stanford. Within a few days, our families got together, and I was charmed by all four Nagels—Ernest and Edith, and their two sons, Sandy and Bobby, both close to my age. I was thrilled to meet the author of a book I so loved, and I found Ernest and Edith to be enormously welcoming of my adolescent enthusiasms for science, philosophy, music, and art.

All too soon, the Nagels’ sabbatical year had nearly drawn to a close, but before they left, they warmly invited me to spend a week that summer at their cabin in Vermont. During that idyllic stay, Ernest and Edith came to represent for me the acme of civility, generosity, and modesty; thus they remain in my memory, all these years later. The high point for me was a pair of sunny afternoons when Sandy and I sat outdoors in a verdant meadow and I read aloud to him the entirety of Gödel’s Proof. What a twisty delight to read this book to the son of one of its authors!

By mail over the next few years, Sandy and I explored number patterns in a way that had a profound impact upon the rest of my life, and perhaps on his as well. He went on—known as Alex—to become a mathematics professor at the University of Wisconsin. Bobby, too, remained a friend and today he—known as Sidney—is a physics professor at the University of Chicago, and we see each other with great pleasure from time to time.

I wish I could say that I had met James Newman. I was given as a high-school graduation present his magnificent four-volume set, The World of Mathematics, and I always admired his writing style and his love for mathematics, but sad to say, we never crossed paths.

At Stanford I majored in mathematics, and my love for the ideas in Nagel and Newman’s book inspired me to take a couple of courses in logic and meta-mathematics, but I was terribly disappointed by their aridity. Shortly thereafter, I entered graduate school in math and the same disillusionment recurred. I dropped out of math and turned to physics, but after a few years I found myself once again in a quagmire of abstractness and confusion.

One day in 1972, seeking some relief, I was browsing in the university bookstore and ran across A Profile of Mathematical Logic by Howard DeLong—a book that had nearly the same electrifying effect on me as Gödel’s Proof did in 1959. This lucid treatise rekindled in me the long-dormant embers of my love for logic, meta-mathematics, and that wondrous tangle of issues I had connected with Gödel’s theorem and its proof. Having long since lost my original copy of Nagel and Newman’s magical booklet, I bought another one—luckily, it was still in print!—and reread it with renewed fascination.

That summer, taking a break from graduate school and driving across the continent, I camped out and religiously read about Gödel’s work, the nature of reasoning, and the dream of mechanizing thought and consciousness. Without planning it, I wound up in New York City, and the first people I contacted were my old friends Ernest and Edith Nagel, who served as intellectual and emotional mentors for me. Over the next several months, I spent countless evenings in their apartment, and we ardently discussed many topics, including, of course, Gödel’s proof and its ramifications.

The year 1972 marked the beginning of my own intense personal involvement with Gödel’s theorem and the rich sphere of ideas surrounding it. Over the next few years, I developed an idiosyncratic set of explorations on this nexus of ideas, and wound up calling it Gödel, Escher, Bach: an Eternal Golden Braid. There is no doubt that the parents of my sprawling volume were Nagel and Newman’s book, on the one hand, and Howard DeLong’s book, on the other.

What is Gödel’s work about? Kurt Gödel, an Austrian logician born in 1906, was steeped in the mathematical atmosphere of his time, which was characterized by a relentless drive toward formalization. People were convinced that mathematical thinking could be captured by laws of pure symbol manipulation. From a fixed set of axioms and a fixed set of typographical rules, one could shunt symbols around and produce new strings of symbols, called theorems. The pinnacle of this movement was a monumental three-volume work by Bertrand Russell and Alfred North Whitehead called Principia Mathematica, which came out in the years 1910–1913. Russell and Whitehead believed that they had grounded all of mathematics in pure logic, and that their work would form the solid foundation for all of mathematics forevermore.

A couple of decades later, Gödel began to doubt this noble vision, and one day, while studying the extremely austere patterns of symbols in these volumes, he had a flash that those patterns were so much like number patterns that he could in fact replace each symbol by a number and reperceive all of Principia Mathematica not as symbol shunting but as number crunching (to borrow a modern term). This new way of looking at things had an astounding wraparound effect: since the subject matter of Principia Mathematica was numbers, and since Gödel had turned the medium of the volumes also into numbers, this showed that Principia Mathematica was its own subject matter, or in other words, that the patterned formulas of Russell and Whitehead’s system could be seen as saying things about each other, or possibly even about themselves.

This wraparound was a truly unexpected turn of events, for it inevitably brought ancient paradoxes of self-reference to Gödel’s mind—above all, This statement is false. Using this type of paradox as his guide, Gödel realized that, in principle, he could write down a formula of Principia Mathematica that perversely said about itself, "This formula is unprovable by the rules of Principia Mathematica." The very existence of such a twisted formula was a huge threat to the edifice of

Reviews for Gödel's Proof

[antao-3 · Rating: 2 out of 5 stars]

What Gödel's Theorem really says is this: In a sufficiently rich FORMAL SYSTEM, which is strong enough to express/define arithmetic in it, there will always be correctly built sentences which will not be provable from the axioms. That, of course, means their contradictions will not be provable, either. So, in a word, the sentences, even though correctly built, will be INDEPENDENT OF the set of axioms. They are neither false nor true in the system. They are INDEPENDENT (cannot stress this enough). We want axioms to be independent of each other, for instance. That's because if an axiom is dependent on the other axioms, it can then be safely removed from the set and it'll be deduced as a theorem. The theory is THE SAME without it. Now, the continuum hypothesis, for instance, is INDEPENDENT of the Zermelo-Fraenkel axioms of the set theory (this was proved by Cohen). Therefore, it's OK to have two different set theories and they will be on an equal footing: the one with the hypothesis attached and the one with its contradiction. There'll be no contradictions in either of the theories precisely because the hypothesis is INDEPENDENT of the other axioms. Another example of such an unprovable Gödelian sentence is the 5. axiom of geometry about the parallel lines. Because of its INDEPENDENCE of the other axioms, we have 3 types of geometry: hyperbolic, parabolic and Euclidean. And this is the real core of The Gödel Incompleteness Theorem. By the way... What's even more puzzling and interesting is the fact that the physical world is not Euclidean on a large scale, as Einstein demonstrated in his Theory of Relativity. At least partially thanks to the works of Gödel we know that there are other geometries/worlds/mathematics possible and they would be consistent.Without a clear and explicit reference to the concept of a formal system all that is said regarding Gödel's theorems is highly inaccurate, if not altogether wrong. For instance, if we say that Gödel's statement is true, after saying that Gödel's Theorem states that it can't be proved either true or false. Without adding "formally", that doesn't really make much sense. We'd only be only talking about axioms, which are only a part of a formal system, and totally neglecting talking about rules of inference, which are what the theorems really deal with.By independent I mean 'logically independent', that is only a consequence of Gödel's theorem in first order languages, whose logic is complete. In second order arithmetic, the Peano axioms entail all arithmetical truths (they characterize up to isomorphism the naturals), so that no arithmetical sentence is logically independent of such axioms. It occurs, however, that second order logic is incomplete and there is no way to add to the axioms a set of inference rules able to recursively derive from the axioms all of their logical consequences. This is why Gödel's theorems holds in higher order languages too. In fact, this is how the incompleteness of higher order logic follows from Gödel's theorems.What prompt me to re-read this so-called seminal book? I needed something to revive my memory because of Goldstein's book on Gödel lefting me wanting for more...I bet you were expecting Hofstadter’s book, right? Nah...Both Nagel’s & Newman’s along with Hofstadter’s are failed attempts at “modernising” what can’t be modernised from a mathematical point of view. Read at your own peril.

[palaverofbirds · Rating: 2 out of 5 stars]

For a book that was supposed to simplify Godel's Proof it was exceptionally complex. No real thesis either; basically, the first 75% of the book is just setting up preliminaries and doesn't even deal directly with Godel's work. Reading this book gave me no further insights on Godel's challenging concepts. I recommend instead Godel, Escher, Bach, which is longer and only devotes a chapter's worth of study on the Proof, but does so in far simpler terms (the author of G.E.B. does the intro to this book.)

[encephalical · Rating: 3 out of 5 stars]

Left me wondering about more foundational items that were mentioned in passing such as 'primitive recursive truths' and the 'Correspondence Lemma'. The exposition seemed rushed at the end.

[emresevinc · Rating: 5 out of 5 stars]

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.

[nolongeratease_1 · Rating: 4 out of 5 stars]

Nagel and Newman provide a nice, quick, and generally well written exposition of Godel's famous proof. This book can easily be read in an afternoon by anyone with the requisite background in logic. They do a particularly nice job in their brief dissemination of the historical concerns that led up to the crisis in foundations in the late 19th and early 20th century. What's nice about this is that it puts Godel into context in a salient way. Godel without Hilbert is like Kant without Leibniz (and Wolff, I suppose). Given the narrow scope and short page count, Hilbert is covered well. However, there are a couple of real problems with this book.First, I do not beleive that this book would really be that helpful for "the educated layman". Insofar as their target audience is concerned, the book is, perhaps, a failure. Why do I say this? Given its breivty, the authors are forced to introduce important bits of information without adequate exposition. For example, the notion of universal quantification makes its first appearance in the last twenty odd pages of the book and is explained in a sentence or to. This is fine for anyone that's had an intro logic course (and can recall what was covered) but is probably inadequate for the logical/mathematical novice. Furthermore, this example is just one case of something that occurs quite often throughout the book. My second worry is that the actual mechanics of the proof are not presented lucidly. This is not altogether unexpected, but the fifteen pages or so that comprise the actual exposition of the proof seem to go by too quickly and sacrifice depth and clarity for readability and brevity. This may not be the authors' fault. I have doubts about whether or not one can successfully offer the sort of exegesis the authors are striving for. That is, I'm just not sure that anyone will ever pull off a lucid "Godel for Dummies". Final thought: I think this book would best serve the needs of a first year graduate student or advanced undergraduate in philosophy. For the student that has some background in logic (perhaps they've done a completeness proof for FOL or at least some proofs with quantifiers) but has yet to take a meta-logic course this book can provide a nicely structured overview of what the the typical meta-logic course aims for.

[nealjking_1 · Rating: 5 out of 5 stars]

This little book offers real insight into one of the weirdest aspects of modern mathematics.

[billmcn_1 · Rating: 5 out of 5 stars]

This is a non-formal, though still rigorous, presentation of the argument of Gödel's famous demonstration that will be accessible to anyone familiar with the basics of mathematical proof, logic, and number theory. By the end of the book, I acutally had the outline of Gödel's tricky self-referential argument all in my head at once, and though it faded quickly, I feel confident I could resurrect it with another reading. Nagel's description of the significance of the proof, as opposed to its mechanics, is less thorough, but that's a quibble. This slim book is a truly impressive feat of exposition.