Contents

Prologue

Acknowledgement

Part I: The Gödelian Symphony

Chapter 1: Foundations and Paradoxes

1 “This sentence is false”

2 The Liar and Gödel

3 Language and metalanguage

4 The axiomatic method, or how to get the non-obvious out of the obvious

5 Peano’s axioms …

6 … and the unsatisfied logicists, Frege and Russell

7 Bits of set theory

8 The Abstraction Principle

9 Bytes of set theory

10 Properties, relations, functions, that is, sets again

11 Calculating, computing, enumerating, that is, the notion of algorithm

12 Taking numbers as sets of sets

13 It’s raining paradoxes

14 Cantor’s diagonal argument

15 Self-reference and paradoxes

Chapter 2: Hilbert

1 Strings of symbols

2 “… in mathematics there is no ignorabimus”

3 Gödel on stage

4 Our first encounter with the Incompleteness Theorem …

5 … and some provisos

Chapter 3: Gödelization, or Say It with Numbers!

1 TNT

2 The arithmetical axioms of TNT and the “standard model” N

3 The Fundamental Property of formal systems

4 The Gödel numbering …

5 … and the arithmetization of syntax

Chapter 4: Bits of Recursive Arithmetic …

1 Making algorithms precise

2 Bits of recursion theory3

3 Church’s Thesis

4 The recursiveness of predicates, sets, properties, and relations

Chapter 5: … And How It Is Represented in Typographical Number Theory

1 Introspection and representation

2 The representability of properties, relations, and functions …

3 … and the Gödelian loop

Chapter 6: “I Am Not Provable”

1 Proof pairs

2 The property of being a theorem of TNT (is not recursive!)

3 Arithmetizing substitution

4 How can a TNT sentence refer to itself?

5 γ

6 Fixed point

7 Consistency and omega-consistency

8 Proving G1

9 Rosser’s proof

Chapter 7: The Unprovability of Consistency and the “Immediate Consequences” of G1 and G2

1 G2

2 Technical interlude

3 “Immediate consequences” of G1 and G2

4 Undecidable1 and undecidable2

5 Essential incompleteness, or the syndicate of mathematicians

6 Robinson Arithmetic

7 How general are Gödel’s results?

8 Bits of Turing machine

9 G1 and G2 in general

10 Unexpected fish in the formal net

11 Supernatural numbers

12 The culpability of the induction scheme

13 Bits of truth (not too much of it, though)

Part II: The World after Gödel

Chapter 8: Bourgeois Mathematicians! The Postmodern Interpretations

1 What is postmodernism?

2 From Gödel to Lenin

3 Is “Biblical proof” decidable?

4 Speaking of the totality

5 Bourgeois teachers!

6 (Un)interesting bifurcations

Chapter 9: A Footnote to Plato

1 Explorers in the realm of numbers

2 The essence of a life

3 “The philosophical prejudices of our times”

4 From Gödel to Tarski

5 Human, too human

Chapter 10: Mathematical Faith

1 “I’m not crazy!”

2 Qualified doubts

3 From Gentzen to the Dialectica interpretation

4 Mathematicians are people of faith

Chapter 11: Mind versus Computer: Gödel and Artificial Intelligence

1 Is mind (just) a program?

2 “Seeing the truth” and “going outside the system”

3 The basic mistake

4 In the haze of the transfinite

5 “Know thyself”: Socrates and the inexhaustibility of mathematics

Chapter 12: Gödel versus Wittgenstein and the Paraconsistent Interpretation

1 When geniuses meet …

2 The implausible Wittgenstein

3 “There is no metamathematics”

4 Proof and prose

5 The single argument

6 But how can arithmetic be inconsistent?

7 The costs and benefits of making Wittgenstein plausible

Epilogue

References

Index

This edition first published in English 2009

English translation © 2009 Francesco Berto

Original Italian text (*Tutti pazzi per Gödel!*) © 2008, Gius. Laterza & Figli, All rights reserved Published by agreement with Marco Vigevani Agenzia Letteraria

Edition history: Gius. Laterza & Figli (1e in Italian, 2008); Blackwell Publishing Ltd (1e in English, 2009)

Blackwell Publishing was acquired by John Wiley & Sons in February 2007. Blackwell’s publishing program has been merged with Wiley’s global Scientific, Technical, and Medical business to form Wiley-Blackwell.

*Registered Office*

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

*Editorial Offices*

350 Main Street, Malden, MA 02148-5020, USA

9600 Garsington Road, Oxford, OX4 2DQ, UK

The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK

For details of our global editorial offices, for customer services, and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com/wiley-blackwell.

The right of Francesco Berto to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the understanding that the publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

*Library of Congress Cataloging-in-Publication Data*

Berto, Francesco.

[Tutti pazzi per Gödel! English]

There’s something about Gödel! : the complete guide to the incompleteness theorem / Francesco Berto.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-4051-9766-3 (hardcover : alk. paper) — ISBN 978-1-4051-9767-0 (pbk. : alk. paper)

1. Incompleteness theorem. 2. Gödel’s theorem. 3. Mathematics--Philosophy. 4. Gödel, Kurt.

I. Title.

QA9.54B4713 2009

511.3–dc22

2009020156

For Marta Rossi

Prologue

In 1930, a youngster of about 23 proved a theorem in mathematical logic. His result was published the following year in an Austrian scientific review. The title of the paper (written in German) containing the proof, translated, was: “On Formally Undecidable Propositions of *Principia mathematica* and Related Systems I.” *Principia mathematica* is a big three-volume book, written by the famous philosopher Bertrand Russell and by the mathematician Alfred North Whitehead, and including a system of logical-mathematical axioms within which all mathematics was believed to be expressible and provable. The theorem proved by the youngster referred to (a modification of ) that system. It is known to the world as the Incompleteness Theorem, and its proof is one of the most astonishing argumentations in the history of human thought. The unknown youngster’s name was Kurt Gödel, and the book you are now holding in your hands is a guide to his Theorem.

In fact, in his paper Gödel presented a sequence of theorems, but the most important among them are Theorem VI, and the last of the series, Theorem XI. These are nowadays called, respectively, Gödel’s First and Second Incompleteness Theorems. When scholars simply talk of Gödel’s Incompleteness Theorem, they usually refer to the conjunction of the two.

Gödel’s Theorem is a technical result. Its original proof included such innovative techniques that in 1931 (and for years to follow) many logicians, philosophers, and mathematicians of the time–from Ernst Zermelo to Rudolf Carnap and Russell himself–had a hard time understanding exactly what had been accomplished. Nowadays, (the proof of ) the Theorem is not considered too complex, and all logicians have met it, in some version or other, in some textbook of intermediate logic. Nevertheless, it remains a technical fact, inaccessible to amateurs. It is therefore surprising how much this proof has changed our understanding of logic, perhaps of mathematics and, according to some, even of ourselves and our world.

Everyone agrees, to begin with, that Gödel’s result is a *terrific* achievement. Gödel’s official biographer John Dawson has noted that it seems customary to invoke geological metaphors in this context. Here is Karl Popper:

The work on formally undecidable propositions was felt as an earthquake, particularly also by Carnap.^{1}

And here is John von Neumann, Princeton’s “human calculator,” in a speech he gave in 1951 when Gödel was given the Einstein Award:

Kurt Gödel’s achievement in modern logic is singular and monumental – indeed it is more than a monument, it is a landmark which will remain visible far in space and time.^{2}

As for the legendary friendship between Gödel and Einstein, the latter once confessed to the economist Oskar Morgenstern that he had gone to Princeton’s Institute for Advanced Study just “um das Privileg zu haben, mit Gödel zu Fuss nach Hause gehen zu dürfen” – to have the privilege of walking home with Gödel.

But this is not enough. Other technical results in contemporary mathematics have received attention from popular books and newspapers. Recently, this happened with Andrew Wiles’ proof of Fermat’s Last Theorem (a 130 page demonstration – in fact, a proof of the Taniyama–Shimura conjecture on elliptic curves, which in its turn entails Fermat’s Theorem) that has inspired a nice book by Simon Singh.^{3} However, no mathematical result has ever had extra-mathematical outcomes remotely comparable to Gödel’s Theorem. Speaking of geological metaphors, let us listen to Rebecca Goldstein:

This man’s theorem is the third leg, together with Heisenberg’s uncertainty principle and Einstein’s relativity, of that tripod of theoretical cataclysms that have been felt to force disturbances deep down in the foundations of the “exact sciences.” The three discoveries appear to deliver us into an unfamiliar world, one so at odds with our previous assumptions and intuitions that, nearly a century on, we are struggling to make out where, exactly, we have landed.^{4}

Gödel’s Theorem has been taken as an icon of contemporary culture: a culture, it is claimed, dominated by such things as relativism, postmodernism, the twilight of incontrovertible truth, objectivity, and so on. Such words as “indeterminacy” and “incompleteness,” of course, evoke this dominant thought of our time. So it has been claimed that “Gödel’s incompleteness theorem shows that it is not possible to prove that an objective reality exists,” or that “Religious people claim that all answers are found in the Bible [but] Gödel seems to indicate it cannot be true.”^{5} Gödel’s result has been referred to in lots of science fiction stories, such as Christopher Cherniak’s *The Riddle of the Universe*, Rudy Rucker’s *Software*, and Stanislaw Lem’s *Golem XIV*. Hans Magnus Enzensberger has dedicated to it the poem “Hommage à Gödel,” on which Hans Werner Henze has based a violin concerto. Various bigwigs of contemporary thought have felt the need to say something on the Theorem: from Wittgenstein’s very controversial claims in the *Remarks on the Foundations of Mathematics*; to Roger Penrose, who in his famous *The Emperor’s New Mind* has resorted to the Theorem to defend, against the basic tenets of artificial intelligence, the idea that the human mind will never be emulated by a computer; to Douglas Hofstadter, who, with his *Gödel, Escher, Bach: An Eternal Golden Braid*, has captured a generation and has won, among other things, the Pulitzer prize.

Besides explaining what Gödel’s Theorem is, in this book I aim at saying something on the extra-mathematical phenomenon it has originated. I would like, if not myself to answer, to put you in a position to answer the question: why are we all crazy for Gödel? How has it happened that such a hieroglyph as

*For every ω-consistent recursive class κ of* FORMULAS *there are recursive* CLASS SIGNS *r such that neither v* Gen *r nor* Neg(*υ* Gen *r*) *belongs to Flg*(*κ*) (where *υ* is the FREE VARIABLE of *r*)^{6}

has become one of the *emblems* of our culture?

Therefore, the book is divided into two parts. The first part, whose title is “The Gödelian Symphony,” is the real introduction to the Theorem. The title takes seriously Ernest Nagel and James R. Newman, who, in their classic book *Gödel’s Proof*, have claimed that such a proof is an “amazing intellectual symphony.”^{7} After a quick introduction to the historical context in which Gödel’s breakthrough took place (from Frege and Russell’s foundationalist project, to the discovery of the paradoxes of set theory, to the advent of Hilbert’s Program), Gödel’s proof is reconstructed bit by bit through an explanation of each of its key steps in a separate chapter. The details of the proof, as I have said, are intricate, but the overall strategy isn’t; on the contrary, it is based on a couple of beautifully simple ideas.

The second part of the book, called “The World after Gödel,” is for the most part less technical, and takes into account some of the most famous theses based upon, or allegedly following from, the Incompleteness Theorem in metaphysics, the philosophy of mathematics, the philosophy of mind, even sociology and politics. Here I show how some interpretations and uses of the Theorem are red herrings based on curious misunderstandings, whereas others are quite interesting and testify to its extraordinary fruitfulness. It is here that the aforementioned big guys, such as Wittgenstein and Penrose, come into play.

This second part is thoroughly and unashamedly influenced by *Gödel’s Theorem: An Incomplete Guide to Its Use and Abuse* – a 2005 book by Torkel Franzén. In the extensive literature on Gödel, Franzén’s book stands out as a serious, moderate but severe analysis of the arbitrary exploitations of Gödel’s results within postmodern thought, political theory, art, religion, new age philosophy, and so on. In these contexts, the Theorem is often inaccurately quoted, misunderstood, and put to work in order to “prove” more or less anything. Among the metaphors targeted by Franzén are some of those proposed by Hofstadter – whose metaphysical journeys between Escher’s paradoxical images, Bach’s compositions, Zen Buddhism, the issues of artificial intelligence, etc., have been criticized by various experts in mathematical logic:

Finding suggestions, metaphors, and analogies in other fields when studying the human mind is of course perfectly legitimate and may be quite useful. But it can only be a starting point, and actual theories and studies of the human mind would be needed to give substance to reflections like Hofstadter’s. Metaphorical invocations of Gödel’s theorem often suffer from the weakness of giving such satisfaction to the human mind that they tend to be mistaken for incisive and illuminating observations.^{8}

Now my heart lies with Hofstadter, to whom I owe (together with millions of people) my interest in Gödel. I believe Hofstadter has put in *Gödel, Escher, Bach* all the logical and mathematical competence one can expect from a book on the Incompleteness Theorem. His only mistake, perhaps, is to have put there even *more* – specifically, enough strange stuff to make the volume unpalatable to some scholars who take themselves too seriously. I also believe that Franzén’s book is a treasure-trove, and the second part of *this* book is mostly consonant with (and indebted to) his guide to the use and abuse of Gödel’s Theorem. In particular, it is consonant with its underlying motivation: few cultural attitudes are as blameworthy as the instrumental usage of a product of human genius, in order to make it say whatever one wants it to.

To a certain extent, it’s a question of approach. I’d reverse Franzén’s claims of the kind I have just quoted – “This may be interesting, but it’s just an analogy and doesn’t follow logically from the Theorem” – into “This may not follow from the Theorem, but it’s an interesting analogy.” With a slight divergence of attitude, those who write textbooks on Gödel (and there are so many of them) can make the difference between a world in which readers get honestly interested in his Theorem, and one in which people come to believe that, all in all, logic has nothing important to tell us, for it is too difficult and esoteric a subject to matter in our lives.

What should you already know in order to understand this book? Basically, you need to have attended a course of elementary logic, and/ or to have read an introduction to elementary logic (lots of good textbooks are available). Actually, the book presupposes even *less*: it presupposes, roughly, the intersection of the material covered in the standard courses and the handbooks for dummies. For instance, some logic courses explain the basics of set theory, some don’t. To make thing easier, therefore, I have introduced in the first chapter the basic set- theoretic machinery we shall need. Furthermore, no specific mathematical competence is required. However, you are expected to have some idea of what a logical operator is, for if I had to explain these notions as well, the book would have turned out to be far too long. In any case, most of the (not too numerous) logical formulas can be skipped without any substantial loss, since I have usually provided the corresponding translations into ordinary English.

I have tried to explain things in as friendly a way as possible: as a philosopher, I believe one should never dispense with comprehensibility for the sake of exactness. One consequence of this is a certain laxity with the use–mention distinction: Quine’s quasi-quotation marks, as well as other quotation devices, have been avoided in all cases in which no confusion would have resulted. Formal as well as informal expressions have been used as names of themselves, disambiguation being secured by the context.

This brings me to say something about the reasons I wrote this book. The first is the same that led me to write others: in the long run, I want to become rich and famous.

The second reason is that, even though I happen to give undergraduate and postgraduate courses in logic, I am not a mathematician at all, but a philosopher who often encounters logic’s sharpness and incredible levels of accuracy and abstractness. After some years of interest in the discipline, I sometimes still have a hard time when learning new and advanced things. I also believe that most people out there, when it’s about getting in touch with such difficult subjects as mathematical logic, work more or less like me. And this book should resemble as much as possible the book *I* would have liked to have had in my hands when I began to learn about Gödel’s Theorem: a text which would explain things to me without oversimplifying, but also without drowning me in long sequences of formal proofs that my philosophical mind would have had trouble following; a book which would take me by the hand and guide me in my ascent towards the Gödelian peak. If the resulting work in some measure approaches this, I will have achieved one of my goals.

Finally, in case you are wondering, I know why *I* am crazy for Gödel: because following his amazing proof has been one of my most fascinating intellectual experiences. Should I succeed in imparting some of this Gödelian magic, I will have achieved another of my goals.

^{1} Quoted in Dawson (1984), p. 74.

^{2} *The New York Times*, March 15, 1951, p. 31.

^{3} Fermat’s Last Theorem (which before Wiles’ proof should rather have been called Fermat’s *conjecture*) says that no equation of the simple form *x ^{n}* +

^{4} Goldstein (2005), pp. 21–2.

^{5} Quoted in Franzén (2005), p. 2.

^{6} Which is Gödel’s original formulation of the First Incompleteness Theorem (see Gödel (1931), p. 30).

^{7} Nagel and Newman (1958), p. 104.

^{8} Franzén (2005), pp. 124–5.

Acknowledgments

This is the English version of a book I have published in Italian with the title *Tutti pazzi per Gödel!* (Laterza, Roma, 2007), and the number of people I am to credit has, understandably, increased for this new edition.

I am grateful to Nick Bellorini of Wiley-Blackwell and to Anna Gialluca of Laterza for their commitment and support during the whole editorial process.

My general debts to those who supported me in writing (and rewriting) the book range across three continents. To begin with, I have some French debts to Friederike Moltmann, Jacques Dubucs, Alexandra Arapinis, and the members of the Institute of History and Philosophy of Sciences and Techniques of the Sorbonne University (Paris 1/CNRS/ ENS) for hosting me in their prestigious research center. During my “Chaire d’excellence” fellowship in Paris, they have provided me with a very comfortable environment to carry out my work; I hope this book partly repays them for their trust (or at the very least for the hundreds of *cafés avec biscuits* I have guzzled in my bureau at the École Normale Superiéure). Thanks also to my wonderful Parisian friends Valeria, Carlo, and Giulia for great conversations that helped make the life of an Italian émigré more enjoyable.

Next, I have some English debts to Dov Gabbay, John Woods, and Jane Spurr of King’s College London for their proposal to publish my *How to Sell a Contradiction* (College Publications, London, 2007), and for kind permission to reuse material taken from Chapters 1, 4, and 12 of that book throughout this one.

Australia is the place where my heart belongs. Down under, I am indebted to Graham Priest for constant support and tremendously useful comments on my work in paraconsistent logic, Meinongian ontology, and Gödelian issues. Thanks also to Paul Redding and Mark Colyvan of the University of Sydney, Greg Restall of the University of Melbourne, and Ross Brady and Andrew Brennan of La Trobe for support of the most varied kind. Part of the material included in Chapter 12 was presented at the Fourth World Congress on Paraconsistency held in Melbourne in July 2008; I am grateful to all participants and especially to J.C. Beall, Koji Tanaka, Zach Weber, Diderik Batens, and Francesco Paoli for comments, encouragement, and enjoyable discussions.

In the US I am indebted, to begin with, to Vittorio Hösle of the University of Notre Dame: during the scholarship I was offered in 2006, I proposed for the first time my Gödelian reflections in a seminar on the philosophy of mind of the twentieth century, and parts of that talk now appear in Chapter 11. I am grateful to David Leech, Gregor Damschen, Dennis Monokroussos, Dae-Joong Kwon, Miguel Perez, Ricardo Silvestre, Fernando Suàrez, and Nora Kreft for lively discussion and comments during that hot Indiana summer. Next, I am most grateful to Achille Varzi of Columbia, NY, for his wonderful support throughout these years and his very encouraging comments on the manuscript of the book.

Thanks to the professors and researchers of various Italian universities for their efforts to support me in the precarious circumstances of academic life: Vero Tarca, Luigi Perissinotto, Luca Illetterati, Max Carrara, Franco Chiereghin, Antonio Nunziante, Francesca Menegoni, Giuseppe Micheli, Andrea Tagliapietra, Michele Di Francesco, Emanuele Severino, Andrea Bottani, Richard Davies, Mauro Nasti, Vincenzo Vitiello, Massimo Adinolfi, and Franca d’Agostini.

Thanks to Enrico Moriconi and Dario Palladino for their invaluable textbook expositions of Gödel’s Theorem – a secure guide both for beginners and for advanced scholars.

Finally, very special thanks to Diego Marconi, whose philosophical work has influenced me so much in so many ways; and to Marcello Frixione, the amazing Matt Plebani, and Blackwell’s anonymous referee, for accurate and extensive comments to the contents of the whole book.

Part I

The Gödelian Symphony

*One of themselves, even a prophet of their own, said, The Cretans are always liars … This witness is true.* (St Paul, *Epistle to Titus,* 1: 12–13)