There's Something About Gödel E-Book

Francesco Berto

• Herausgeber: John Wiley & Sons
• Kategorie: Geisteswissenschaft
• Sprache: Englisch

Seitenzahl: 445

Veröffentlichungsjahr: 2011

Beschreibung

Berto's highly readable and lucid guide introduces students and the interested reader to Gödel's celebrated Incompleteness Theorem, and discusses some of the most famous - and infamous - claims arising from Gödel's arguments. * Offers a clear understanding of this difficult subject by presenting each of the key steps of the Theorem in separate chapters * Discusses interpretations of the Theorem made by celebrated contemporary thinkers * Sheds light on the wider extra-mathematical and philosophical implications of Gödel's theories * Written in an accessible, non-technical style

Leseprobe

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

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)

1

Foundations and Paradoxes

In this chapter and the following, we shall learn lots of things in a short time.1 Initially, some of the things we will gain knowledge of may appear unrelated to each other, and their overall usefulness might not be clear either. However, it will turn out that they are all connected within Gödel’s symphony. Most of the work of these two chapters consists in preparing the instruments in order to play the music. We will begin by acquiring familiarity with the phenomenon of self-reference in logic–a phenomenon which, according to many, has to be grasped if one is to understand the deep meaning of Gödel’s result. Self-reference is closely connected to the famous logical paradoxes, whose understanding is also important to fully appreciate the Gödelian construction–a construction that, as we shall see, owes part of its timeless fascination to its getting quite close to a paradox without falling into it.

But what is a paradox? A common first definition has it that a paradox is the absurd or blatantly counter-intuitive conclusion of an argument, which starts with intuitively plausible premises and advances via seemingly acceptable inferences. In The Ways of Paradox, Quine claims that “a paradox is just any conclusion that at first sounds absurd but that has an argument to sustain it.”2 We shall be particularly concerned not just with sentences that are paradoxical in the sense of being implausible, or contrary to common sense (“paradox” intended as something opposed to the , or to what is , entren ched in pervasive and/or authoritative opinions), but with sentences that constitute authentic, full-fledged contradictions. A paradox in this strict sense is also called an antinomy.

However, sometimes the whole argument is also called a paradox.3 So we have Graham Priest maintaining that “[logical] paradoxes are all arguments starting with apparently analytic principles … and proceeding via apparently valid reasoning to a conclusion of the form ‘α and not-α’.”4

Third, at times a paradox is considered as a set of jointly inconsistent sentences, which are nevertheless credible when addressed separately.5

The logical paradoxes are usually subdivided into the semantic and set-theoretic. What is semantics, to begin with? We can understand the notion by contrasting it with that of syntax. Talking quite generally, in the study of a language (be it a natural language such as English or German, or an artificial one such as the notational systems developed by formal logicians), semantics has to do with the relationship between the linguistic signs (words, noun phrases, sentences) and their meanings, the things those signs are supposed to signify or stand for. Syntax, on the other hand, has to do with the symbols themselves, with how they can be manipulated and combined to form complex expressions, without taking into account their (intended) meanings.

Typically, such notions as truth and denotation are taken as pertaining to semantics.6 Importantly, a linguistic notion is classified as (purely) syntactic when its specification or definition does not refer to the meanings of linguistic expressions, or to the truth and falsity of sentences. The distinction between syntax and semantics is of the greatest importance: I shall refer to it quite often in the following, and the examples collected throughout the book should help us understand it better and better.

The set-theoretic paradoxes concern more technical notions, such as those of membership and cardinality. These paradoxes have cast a shadow over set theory, whose essentials are due to the great nineteenth-century mathematician Georg Cantor, and which was developed by many mathematicians and logicians in the twentieth century.

Nowadays, set theory is a well-established branch of mathematics. (One should speak of set theories, since there are many of them; but mathematicians refer mainly to one version, that due to Ernst Zermelo and Abraham Fraenkel, to which I shall refer in the following.) But the theory has also a profound philosophical importance, mainly because of the role it has had in the development of (and the debate on) the so-called foundations of mathematics. Between the end of the nineteenth century and the beginning of the twentieth, the great philosophers and logicians Gottlob Frege and Bertrand Russell attempted to provide a definitive, unassailable logical and philosophical foundation for mathematical knowledge precisely by means of set theory. When Gödel published his paper, the dispute on the foundations of mathematics was quite vigorous, because of a crisis produced by the discovery of some important paradoxes in the so-called naïve formulation of set theory.

In these initial chapters, therefore, we shall learn some history and some theory. On the one hand, we will have a look at the changes that logic and mathematics were undergoing at the beginning of the twentieth century, mainly because of the paradoxes: to know something of the logical and mathematical context Gödel was living in will help us understand why the Theorem was the extraordinary breakthrough it was. But we shall also learn some basic mathematical and set- theoretical concepts. Among the most important notions we will meet in this chapter is that of algorithm. By means of it, we should come to understand what it means for a given set to be (intuitively) decidable; what it means for a given set to be (intuitively) enumerable; and what it means for a given function to be (intuitively) computable. If this list of announcements on the subjects we shall learn sounds alarming, I can only say that the initial pain will be followed by the gain of seeing these separate pieces come together in the marvelous Gödelian jigsaw.

1 “This sentence is false”

I have claimed that the semantic paradoxes can involve different semantic concepts, such as denotation, definability, etc. We shall focus only on those employing the notions of truth and falsity, which are usually grouped under the label of the Liar. These are the most widely discussed in the literature–those for which most tentative solutions have been proposed. They are also the most classical, having been on the philosophical market for more than 2,000 years–a fact which, by itself, says something about the difficulty of dealing with them. The ancient Greek grammarian Philetas of Cos is believed to have lost sleep and health trying to solve the Liar paradox, his epitaph claiming: “It was the Liar who made me die/And the bad nights caused thereby.”

One of the most ancient versions of semantic paradox appears in St Paul’s Epistle to Titus. Paul blames a “Cretan prophet,” who was to be identified as the poet and philosopher Epimenides, and who was believed to have at one time said:

(1) All Cretans always lie.

Actually, (1) is not a real paradox in the strict sense of a sentence which, on the basis of our bona fide intuitions, would entail a violation of the Law of Non-Contradiction. It is just a sentence that, on the basis of those intuitions, cannot be true. It is self-defeating for a Cretan to say that Cretans always lie: if this were true–that is, if it were the case that all sentences uttered by any Cretan are false–then (1), being uttered by the Cretan Epimenides, would have to be false itself, against the initial hypothesis. However, there is no contradiction yet: (1) can be just false under the (quite plausible) hypothesis that some Cretan sometimes said something true.

We are dealing with a full-fledged Liar paradox (also attributed to a Greek philosopher, and probably the greatest paradoxer of Antiquity: Eubulides) when we consider the following sentence:

(2) (2) is false.

As we can see, (2) refers to itself, because it is no. 2 of the sentences highlighted in this chapter, and tells something of the very sentence no. 2. Also (1) refers to itself, but does it in a different way from (2). This is what makes (1) not strictly paradoxical. Sentence (1) claims that all the members of a set of sentences (those uttered by Cretans) are false. In addition, it belongs to that very set, due to its being uttered by a Cretan. Therefore (1) can be simply false, under the empirical hypothesis that some sentence uttered by a Cretan, and different from (1), is true. This is also what makes it look so odd: it is unsatisfactory that a logical paradox is avoided only via the empirical fact that some Cretan sometimes said something true.

Some form of self-reference can be detected in (almost) all paradoxes, so that the phenomenon of self-reference as such has been held responsible for the antinomies. Nevertheless, lots of self-referential sentences are harmless, in that we seem to be able to ascertain their truth value in an unproblematic way. For instance, you may easily observe that, among the following, (3) and (4) are true, whereas (5) is false:

(3) (3) is a grammatically well-formed sentence.

(4) (4) is a sentence contained in There’s Something About Gödel!

(5) (5) is a sentence printed with yellow ink.

In contrast, (2) is not harmless at all. Let us reason by cases. Suppose (2) is true: then what it says is the case, so it’s false. Suppose then (2) is false. This is what it claims to be, so it’s true. If we accept the Principle of Bivalence, that is, the principle according to which all sentences are either true or false, both alternatives lead to a paradox: (2) is true and false! To claim that something is both true and false is to produce a denial of the Law of Non-Contradiction. And this is how our bona fide intuitions lead us to a contradiction, via a simple reasoning by cases.

Other versions of the Liar are called strengthened Liars,7 or also revenge Liars (whereas (2) may be called the “standard” Liar):

(6) (6) is not true.

(7) (7) is false or neither true nor false.

The reason why sentences such as (6) deserve the title of strengthened Liars is the following. Some logicians (including the best one of our times, Saul Kripke) have proposed circumventing the standard Liar (2) by dispensing with the Principle of Bivalence, that is, by admitting that some sentences can be neither true nor false, and that (2) is among them. Sentence (2) is a statement such that, if it were false, it would be true, and if it were true, it would be false. But we can avoid the contradiction by granting that (2) is neither. Such a solution has some problems with sentences such as (6), which appear to deliver a contradiction even when we dismiss Bivalence. In this case, the set of sentences is divided into three subsets: the true ones, the false ones, and those which are neither. Now we can reason by cases again with (6): either (6) is true, or it is false, or neither. If it’s true, then what it says is the case, so it’s not true. If it’s false or neither true nor false, then it is not true. However, this is what it claims to be, so in the end it’s true. Whatever option we pick, (6) turns out to be both true and untrue, and we are back to contradiction. This Liar thus gains “revenge” for its cousin (2).8

2 The Liar and Gödel

A sentence can refer to itself in various ways, so we can have various versions of (2). For instance:

(2a) This sentence is false.

(2b) I am false.

(2c) The sentence you are reading is false.

The paradox can also be produced without any immediate self- reference, but via a short-circuit of sentences. For instance:

(2d) (2e) is true.

(2e) (2d) is false.

This is as old as Buridan (his sophism 9: Plato saying, “What Socrates says is true”; Socrates replying, “What Plato says is false”). If what (2d) says is true, then (2e) is true. However, (2e) says that (2d) is false … and so on: we are in a paradoxical loop.

However, it seems that self-reference is obtained in all cases by means of an unavoidable “empirical,” i.e., contextual or indexical, component. In fact, in the paradoxical sentences we have examined so far, selfreference is achieved via the numbering device, or via indexical expressions such as “I”, “this sentence,” and so on. Only factual and contextual information tells us that the denotation of (those tokens of) such expressions is the very sentence in which they appear as the grammatical subjects. This holds for the “looped Liar”: suppose (2d) is as above, but (2e) now is “Perth is in Australia.” Then (2d) is just true, and no paradox is expected. But it happens also with the immediately selfreferential paradoxical statements above: for instance, if I uttered (a token of) (2a) by pointing, say, at (a token of) the sentence “2 + 2 = 5” written on a blackboard, there would be no self-reference at all, for “this sentence,” in the context, would refer to (the token of) “2 + 2 = 5” (and, besides, I would be claiming something true). Ditto if I uttered (2c) referring to you, while you are reading the false sentence written on the blackboard.

Because of this, some (among which the Italian mathematician Giuseppe Peano, of whom I shall talk again later) have believed that the semantic paradoxes involve some non-logical phenomenon: they depend on contextual, empirical factors. Frank Ramsey, to whom the distinction between semantic and set-theoretic paradoxes is usually ascribed, depicted the situation thus by referring to the list of paradoxes examined in Russell and Whitehead’s Principia mathematica:

Group A [i.e., antinomies no. 2, 3, and 4 of the original list of Principia: among them, the Russell and Burali-Forti paradoxes, which I will introduce later] consists of contradictions which, were no provision made against them, would occur in a logical or mathematical system itself. They involve only logical or mathematical terms such as class and number, and show that there must be something wrong with our logic and mathematics. But the contradictions in Group B [i.e., antinomies no. 1, 5, 6, 7 of Principia: among them, the Liar] are not purely logical, and cannot be stated in logical terms alone; for they all contain some reference to thought, language, or symbolism, which are not formal but empirical terms.9

However, just after Ramsey had proposed the distinction, Gödel himself showed how to build, within a formal logical system, self-referential constructions with no empirical trespassers of any kind: self-referential statements whose content is as empirical and contextual as that of “2 + 2 = 4.” To achieve this, Gödel used the language of mathematical logic as nobody had done before; and the apparatus he put to work is probably the most inspired aspect of the proof of the Theorem that bears his name.

Behind the Gödelian construction hide precisely the simple intuitions concerning the conundrum originated by the Liar which made the ancient Greeks lose their sleep. However, Gödel did not exploit those intuitions to engender a contradiction, via a sentence that claims of itself to be false, like (2), or untrue, like (6). He produced a sentence that walks on the edge of paradox, without falling into it. I shall talk of this mysterious Gödelian sentence at length: it is, in fact, the main character of the story I have begun to tell.

3 Language and metalanguage

The great Polish logician Alfred Tarski, and many after him, have held responsible for such semantic paradoxes as the Liars certain features of natural language, grouped under the label of “semantic closure conditions.” Roughly, a semantically closed language is a language capable of talking of its own semantics, of the meanings of the expressions of the language itself. Less roughly, “a semantically closed language is one with semantic predicates, like ‘true’, ‘false’, and ‘satisfies’, that can be applied to the language’s own sentences.”10 It is because English can mention its own expressions, and ascribe semantic properties to them, that we can have such sentences as (2) or (6): some expressions of our everyday language can somehow refer to themselves; “true” and “false” are perfectly meaningful predicates of English; and they can be applied to sentences of English.

In a Tarskian approach, the semantic paradoxes are due to a mixture of object language and metalanguage. Logicians and philosophers usually call “object language” the language we speak about, or we give a theory of, this being precisely the object of the theory. However, the theory itself will obviously be phrased in some language or other; and the language in which the theory is formulated can be labeled as a metalanguage, that is to say, a “language on a language.”

That (object) language and metalanguage may be distinct is fairly clear. If you are studying a basic French grammar written in English, you will find that French figures in it mostly as the object language, whereas English is employed mainly as the metalanguage. But in our self-referential statements above, the two levels are mixed: these are English sentences talking of English sentences (specifically, of themselves). And this fusion, according to the Tarskian approach, gives rise to the paradox.

The Tarskian treatment maintains that the truth predicate cannot be univocal. A single surface grammar expression, “is true,” has an ambiguous function for different languages, each of which is semantically open at the level of some deep logical grammar. Instead of a unique language, we would have a hierarchy, more or less with the following structure. For any ordinal n we have a language Ln, and n is the order of Ln. Let us begin with L0, taken as our “basic” level language. The semantic concepts concerning L0 cannot be expressed within L0 itself, but must be expressed in a language, say L1, which is its metalanguage. L1 will contain predicates that refer to the semantic concepts of L0 (and, in particular, by means of which we can provide a definition of truth for sentences of L0: I shall come to the details of the Tarskian definition of truth in Chapter 9). However, L1 is itself “semantically open”: it cannot express its own semantic concepts. So a definition of truth for L1 will be expressed in a language, L2, which is the metalanguage of L1; and so on.11 The Tarskian solution parameterizes the semantic predicates along the hierarchy of the metalanguages: the metalinguistic “true” and “false” are now abbreviations for “true in the object language,” “false in the object language.” In particular, the standard Liar turns into “This sentence is false in the object language.” Its place is in the metalanguage, and it is just false there, not paradoxical: since metalinguistic sentences do not belong in the object language at all, the Liar does not have the property it claims to have.12

In point of fact, however, Tarski proposed his hierarchy as a structure for the artificial languages of formal logic, and did not claim his strategy to be applicable to natural languages (though others after him have been less restrained on this). Tarski’s prudence is easily understood. First, there is no evidence that the predicate “true” performs some ambiguous function along some hidden hierarchy of languages, metalanguages, metametalanguages, etc. This makes the proposal to apply the theory to ordinary English look like a form of revisionism: a suggestion to the effect that ordinary English be somehow regimented. If the idea came to Tarski’s mind, he certainly found it unsatisfactory.13

Second, a decisive difference between such a hierarchy and English is that there does not seem to be any metalanguage for English. This becomes manifest if we accept the principle according to which ordinary language is, so to speak, “transcendental”: anything that is linguistically expressible can be expressed within ordinary language–there is no limit to it. In Tarski’s own words:

A characteristic feature of colloquial language (in contrast to various scientific languages) is its universality. It would not be in harmony with the spirit of this language if in some other language a word occurred which could not be translated into it; it could be claimed that “if we can speak meaningfully about anything at all, we can also speak about it in colloquial language.”14

We need not enter into subtle issues in the philosophy of language, though. Two important things to be kept in mind in following this book are (a) the idea of the distinction between (object) language and metalanguage, and (b) the basic intuition behind the kind of self-reference taking place when we can see a certain linguistic expression as talking of itself, and as ascribing to itself some features and properties.

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

We have seen that the Liar has been around since the ancient Greeks. We also need to start from ancient Greece to understand what the axiomatic method is, and why this method has enjoyed an almost spotless reputation throughout Western thought. We need to refer, in fact, to Euclidean geometry–a theory we all know from elementary school, and which has been the paradigm of axiomatization for centuries.

In his Elements of Geometry, the Greek mathematician Euclid introduced some simple geometrical definitions (such as “A point is that which has no part”), and the celebrated five postulates, or axioms, that bear his name (for instance, the first says, “Any two points can be joined by a straight line”; the fourth says, “All right angles are congruent”). In the axiomatic approach, axioms are sentences accepted without a proof, as principles of deduction–principles from which we can infer other sentences, via purely deductive reasoning. The sentences with which the various deductive chains come to an end are called the theorems of Euclidean geometry. Such deductive chains are the proofs of Euclidean geometry; the closures of such chains, i.e., the theorems, are what are properly said to have been demonstrated, or proved, from the axioms.

Axioms, proofs, theorems: this beautifully simple and powerful pattern of knowledge has always fascinated scholars. Beginning with a small amount of what Quine would have called “ideology,” that is, with a few intuitive notions and the initial postulates, Euclidean geometry delivered a large amount of theorems by means of deductive procedures which appeared to be fairly clear and rigorous. And the axioms were considered–keep this in mind for the following–as (manifestly) true. In the so-called classical conception of axiomatic systems, axioms were taken as evident, if not trivial, truths. This is exactly how we wanted them, so that we could accept them without further argumentation. The chain of deductions and inferences has to come to an end somewhere, and what better place to append it than the obvious? The proofs of Euclidean geometry being valid proofs, truth could go downstairs from the axioms to often more complex and less evident theorems. This, after all, is the fundamental virtue of valid deductive reasoning: transmitting truth from premises to conclusions.

For these reasons, numerous philosophers (from Descartes to Spinoza and Kant) took Euclidean geometry as a paradigm of rigorous knowledge. They sometimes even tried to export the model and its successful features to other compartments of science, so as to raise them to a comparable level of certitude and precision. The case of “export” we are most interested in takes the stage in the next paragraph.

5 Peano’s axioms …

A closer ancestor of Gödel’s results is constituted by the amazing developments of mathematics in the nineteenth century. Some of them had to do with the so-called arithmetization of analysis, which allowed the reduction of higher parts of mathematics to elementary arithmetic, that is, to the theory of natural numbers (the positive integers, including zero: 0, 1, 2, …). Thanks to the work of mathematicians like Weierstrass, Cantor, and Dedekind, other kinds of number were referred to rational numbers (the numbers representable as ratios of integers) and, via these, to the natural numbers.

The two mathematical results we are most interested in, however, are (a) the aforementioned theory of infinite numbers and sets due to Cantor, and (b) an axiomatic achievement: the formulation of the axioms for arithmetic due to Dedekind and Peano. While the axiomatization of geometry dated back to the ancient Greeks, an analogue account for arithmetic became available only at the end of the nineteenth century, when Dedekind provided the recursive equations for addition and multiplication (which will be met and explained in a later chapter), and immediately afterwards Peano proposed the famous axioms for arithmetic that bear his name.

Only three notions appear in Peano’s axioms–three notions taken as primitive and fundamental: zero, (natural) number, and (immediate) successor, the (immediate) successor of a number being the one that follows it immediately in the ordering of the naturals, i.e., 1 is the successor of 0, 2 is the successor of 1, and so on. In the Arithmetices principia, nova methodo exposita Peano employed the three basic notions to formulate the following five principles:

(P1) Zero is a number.

(P2) The successor of any number is a number.

(P3) Zero is not the successor of any number.

(P4) Any two numbers with the same successor are the same number.

(P5) Any property of zero that is also a property of the successor of any number having it is a property of all numbers.

Peano’s fifth axiom, (P5), is usually called the (mathematical) induction principle. I’ll come back to it repeatedly in the following (as we will see, “induction” here has little to do with inductive reasoning; on the contrary, it is a typical procedure of deductive sciences).

6 … and the unsatisfied logicists, Frege and Russell

Peano’s axiomatization of arithmetic, just like Euclid’s for geometry, was still considered by some scholars to be an inadequate account. They complained especially about the insufficient logical rigor in the proof chains. In fact, in his Elements Euclid had formulated some socalled “common notions” which looked like general rules of logical inference (“Two things identical to a third one are identical to each other,” for instance). However, Euclid’s language lacked the rigor of modern logical languages. To establish that a given deductive chain is valid (that is, that it will never lead us from true premises to a false conclusion), one has to look at the meanings of (some of) the words and phrases used to express it. But ordinary language expressions, as we noted when we mentioned Tarski’s position on natural language, are often vague, equivocal, or both. Because of this, at least since Leibniz’s Characteristica universalis, philosophers have been envisaging artificial, formal languages to serve as antidotes to the deficiencies of natural language, and in which rigorous science could be formulated: languages whose syntax was to be absolutely precise, and whose expressions were to have completely precise and univocal meanings.

Now, some of Euclid’s proofs appeared to include notions captured neither by the explicit definitions, nor by the postulates; and they certainly adopted principles of logical inference which were not listed among the common notions. As for Peano, he had already introduced a formal notation in 1888 (in fact, one including symbols which are nowadays embedded in the canonical logical and set-theoretical notation). However, his axiomatization of arithmetic lacked a rigorous specification of the logical principles employed in the deductions from the axioms. Peano’s proofs were rather informal, and the task of establishing the correctness of the deductive passages was often simply left to the reader. By contrast, since the introduction to his 1879 Ideography–the text whose publication is considered the founding act of modern logic–Gottlob Frege had begun to show how arithmetical claims could be proved by means of precise, explicitly stated logical rules. On the one hand, arithmetical proof sequences had to be translated into an artificial symbolic language. On the other hand, the logical rules operating in the proofs had to be made rigorously explicit. Frege provided a first precise characterization of what we nowadays call a formal system–a notion to which I will return again and again, and whose richness will be explored little by little as this book develops.

Once “higher” mathematics had been reduced to the natural numbers, and secure (or so it seemed) logical rules to reason on them were available, one might have gained the impression that mathematical knowledge had reached safe ground. Infinitesimals and irrational numbers had a problematic status. For a long time, mathematicians and philosophers had had qualms concerning the consistency of mathematical analysis; but everyone considered the good old integers to be reliable guys. However, Frege had a deeper ambition: that of providing a foundation, on pure logic, for arithmetic itself. Such an ambition was shared, between the end of the nineteenth century and the beginning of the twentieth, by Bertrand Russell. It was Russell, in fact, who brought Frege’s work to the attention of a wider audience; and “logicism” was the name given to the project, precisely because of its aiming at a rigorous logical foundation of arithmetic. Both Frege and Russell believed there to be no theoretical distinction between the two domains. The notions of zero, (natural) number, and (immediate) successor, taken by Peano as primitive for arithmetic, and its fundamental principles as captured by Peano’s axiomatization, were to be defined and deduced in their turn from still more fundamental and purely logical principles. Specifically, they were to be obtained precisely from the principles of set theory, which at the time was considered a limb of logic.16

7 Bits of set theory

To understand what the logicist program consisted of–and, most importantly, what major obstacle it stumbled upon–we need to swallow some of the medicine of set theory. What’s a set, to begin with? In the first instance, a set is just a collection of objects. In the following, I will usually refer to sets by means of capital Latin letters: A, B, C, ….17 The fundamental and primitive relation at issue in set theory is that of an object belonging to a set, or being a member of a set. This is expressed by the symbol “” (and non-membership is expressed by “”). I will write, then, such things as “x A” (“x A”), to mean that a given object x is (is not) a member or an element of set A, that is, it belongs (does not belong) to the set.

One can sometimes specify a set simply by providing a complete list of its elements, which is usually written thus: {x1, …, xn} is the set whose members are indeed x1, …, xn. For instance, one can specify the set whose sole elements are Frege, Juliette Binoche, and the city of Melbourne, thus:

{Gottlob Frege, Juliette Binoche, Melbourne}.