Hofstadter Douglas R. - Gödels proof

Gdels Proof

In 1931 Kurt Gdel published a revolutionary paperone 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 Gdels 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 prizewinning 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 Gdels proof, and shows how and why Gdels proof remains relevant today.

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
Gdels 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. Gdels theorem. I. Newman, James Roy, 19071966. II. Hofstadter,
Douglas R., 1945 III. Title.
QA9.65 .N34 2002
511.3dc21 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

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 Gdels 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 Gdels 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 books mystique, and once home, I voraciously gobbled up its every word. From start to finish, Gdels 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 NagelsErnest 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 Gdels 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 onknown as Alexto become a mathematics professor at the University of Wisconsin. Bobby, too, remained a friend and today heknown as Sidneyis 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 Newmans 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 DeLonga book that had nearly the same electrifying effect on me as Gdels 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 Gdels theorem and its proof. Having long since lost my original copy of Nagel and Newmans magical booklet, I bought another oneluckily, 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 Gdels 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, Gdels proof and its ramifications.

The year 1972 marked the beginning of my own intense personal involvement with Gdels 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 Gdel, Escher, Bach: an Eternal Golden Braid. There is no doubt that the parents of my sprawling volume were Nagel and Newmans book, on the one hand, and Howard DeLongs book, on the other.

What is Gdels work about? Kurt Gdel, 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