- Paperback: 172 pages
- Publisher: A. K. Peters; 1st edition (June 8, 2005)
- Language: English
- ISBN-10: 1568812388
- ISBN-13: 978-1568812380
- Product Dimensions: 6 x 0.4 x 9 inches
- Shipping Weight: 5.6 ounces (View shipping rates and policies)
- Average Customer Review: 26 customer reviews
- Amazon Best Sellers Rank: #817,442 in Books (See Top 100 in Books)
Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
To get the free app, enter your mobile phone number.
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 1st Edition
Use the Amazon App to scan ISBNs and compare prices.
The Amazon Book Review
Author interviews, book reviews, editors picks, and more. Read it now
Frequently bought together
Customers who bought this item also bought
" ""Franzén's book is accessible, well written, and often funny..."" -Richard Zach, History and Philosophy of Logic, July 2005
""Ich möchte allen meinen Lesern . . . ein Buch ans Herz legen, und zwar ""das Neue"" von Torkel Franzén: Gödel's Theorem - An Incomplete Guide to Its Use and Abuse..."" -Altpapier, October 2005
""If the reader is serious about understanding the scope and limitations of Gödel's theorems, this book will serve them well."" -Don Vestal, MAA Online, November 2005
"". . . This is an excellent book, carefully considered and well-written. It will be read by layman and expert alike with pleasure and profit."" -Peter A. Fillmore, CMS Notes, Volume 37 No. 8, December 2005
""... a welcome tourist's guide not only to the correct but also to many incorrect interpretations of the theorems, both in their immediate contexts and in wider circumstances."" -I. Grattan-Guinness, LMS, February 2007
""This is a marvelous book. It is both highly competent and yet enjoyably readable. ... At last there is available a book that one can wholeheartedly recommend for anyone interested in Gödel’s incompleteness theorem―one of the most exciting and wide-ranging achievements of scientific thought ever."" -Panu Raatikainen, Notices of the AMS, February 2007
""This is a marvelous book. It is both highly competent and yet enjoyably readable. ... At last there is available a book that one can wholeheartedly recommend for anyone interested in Gödel’s incompleteness theorem―one of the most exciting and wide-ranging achievements of scientific thought ever."" -Panu Raatikainen, Notices of the AMS, March 2007
""... an extraordinary addition to the literature. ... The book is ideal reading for people with a basic logical background, be they computer scientists, philosophers, mathematicians, physicists, cognitive psychologists, or engineers ... and a real desire to understand quite deeply one of the intellectual gems of the 20th century."" -Wilfried Sieg, Mathematiacl Reviews, March 2007
""... lively and a pleasure to read ... provides remarkably sharp formulations of the usual confusions. There is no doubt that readers of this journal should recommend this book to any friends or colleagues who ask about the ramifications of incompleteness."" -Stewart Shapiro, Philosophia Mathematica, June 2006
""Dawson's biography of GÄodel is provocative and interesting on several fronts, and is highly recommended to anyone with an interest in logic, the foundations of mathematics or the history of mathematics."" -Samuel R. Buss Buss, December 1998
""This book presents an exceptional exposition of Gödel's incompleteness theorems for non-specialists ... a valuable addition to the literature."" -EMS, March 2006
""The book explains fully, without using any technical logical apparatus, Gödel's two theorems about the incompleteness of any formal system which includes elementary arithmetic ... It is a great success in the way that the proofs of the theorems, while not given in full, are outlined in sufficient detail to make a discussion of the different versions that have been given worthwhile. I do not think there is any non-specialist exposition comparable for clarity and thoroughness."" -Clive Kilmister, The Mathematical Gazette, March 2007
""Franzen touches upon contemporary issues in logic that otherwise only rarely find their way into books of an introductory character like this one."" -The Review of Modern Logic, March 2007
""Torkel Franzen's ""Goedel's Theorem"" is a wonderful book, destined to become a classic ... In ""Goedel's Theorem,"" Torkel Franzen does a superb job of explaining clearly and carefully what the incompleteness theorem says and its implications as well as skewering much of the nonsense that has been written about it. ... However, while ""Goedel's Theorem"" should be accessible to a general audience, ""Inexhaustibility"" may be rather rough going for a reader who has not seriously studied mathematical logic."" -Mathematics and Comupter Science, March 2008"
About the Author
A philosopher by training (PhD, University of Stockholm), Torkel Franzén has for the past twenty years been active working in computer science (at the Swedish Institute of Computer Science) and teaching programming (at Luleå University of Technology). He is the author of a number of books, among them Inexhaustibility: A Non-Exhaustive Treatment.
Browse award-winning titles. See more
Top customer reviews
There was a problem filtering reviews right now. Please try again later.
And I guess I can't blame them because the last thing you'd want to do in a review talking about the wrongful use of Godel's theorem is to wrongfully use it yourself!
That being said, I'll cast aside caution and just say that chapters 4 and 6 in regards to Rucker and Penrose are helpful reading along with the book's cautionary message to be mindful in invoking theorem, well, only where it actually applies.
Because the book is so short (just 170 pages), it's a pretty quick read. Reader's new to Godel's theorem may wish to read the excellent Ernest Nagel book entitled simply "Godel's Theorem."
Founder of Literate Scientist Blog
However important Gödel's theorem in its own right, I found the book interesting as a review of the basics of the foundations of mathematics. Without introducing any equations, Franzén manages to do a very serious job of explaining the issues. The math is needed to verify the validity of some key assertions made in the book, but there is nothing very enlightening about the math itself, so one gets a good feel for the subject just through a mostly-verbal overview.
Franzén deals with "formal systems," which have enough logic and arithmetic to state and prove theorems. Franzén's basic formal systems are the "basic arithmetic" embodied in the Peano Axioms for the natural numbers, including enough propositional and first-order predicate logic to permit proving propositions about numbers (PA), and the Zermelo-Fraenkel axioms of set theory, including the Axiom of Choice (ZFC).
We say a proposition p about the natural number is true precisely if p. For instance, "every even natural number is the sum of two primes" is true if every even natural number is the sum of two primes (Goldbach's conjecture---still unproven). Note that the notion of "truth" is not formulated within PA or ZFC. What formal systems do is to turn axioms and inference rules into theorems. A theorem in a formal system is a sequence of symbols that can be proved within the system. A proof of a theorem is a sequence of statements, each of which is either an axiom or the result of applying the rules of inference to previous statements in the sequence. The theorem proved is simply the last statement of the proof. Thus, a proof can proceed without any concern with the "meanings" of the axioms and inference rules, whereas the concept of "truth" is inherently semantic: a true proposition means something, and what it means is in fact the case.
The foundations of mathematics revolve around assessing the plausibility and value of alternative axiomatic systems, and characterizing the relationship between theorems (strings of symbols legally derived from the axioms and other legally-derived strings of symbols) and the truth of what these theorems assert. We say a formal system S is "valid" if all of its theorems are true, and "complete" if all true statements that can be expressed in the system are theorems (i.e., can be proved). The best of all possible worlds for a formal system is that (a) has interesting theorems, and (b) is valid and complete. A minimum necessity for an acceptable formal system is that it be "consistent," meaning if p is a theorem, then not p is not a theorem. An inconsistent system that contains the propositional calculus (the logical symbols "and", "or", "not", and "implies," and the inference principle modus ponens, which says that "if you prove p, and if you prove p implies q, then you have proved q") can prove anything, so is useless. Consistency, however, is a very weak condition, because a consistent system need not be valid or complete; i.e., a consistent system can prove things that are false and can fail to prove things that are true. Note that a proposition p is provable in a system S if and only if the system S + not-p, gotten by adding non-p as an axiom, is inconsistent.
We say a proposition p is "decidable" in formal system S if it can be either proved or disproved in S. A proposition that can be neither proved nor disproved in S is called "undecidable." Note that p is undecidable in formal system S if and only if both S + p (adding p as an axiom to S) and S + not p (adding not p as an axiom) are consistent.
A Turing machine is basically a computer with a memory that can be expanded to be as large as we want. An "algorithm" is a program for a Turing machine that, given any number or finite sequence of numbers, terminates with an answer in a finite number of steps. Of course, a useful algorithm actually computes something useful. For instance, given two positive integers, there is a well-known algorithm for calculating their least common divisor. Similarly, given a polynomial function f(x,y,z) and a set of numerical inputs a, b, c, there is always an algorithm for calculating f(a,b,c).
We say a property P of numbers is "computable" if it can be checked by applying an algorithm. Consider, for instance, Goldbach's conjecture that every even natural number is the sum of two primes is computable, because given any even natural number k, we can simply run through the primes less than k until we find a pair that sums to k, or we run out of primes less than k. Franzén calls propositions that can be refuted by a computable process "Goldbach-like." A Goldbach-like proposition, if false, can always be proved false by a formal system that includes basic arithmetic, simply by running through all possibilities until a counter-example is found. If a Goldbach-like proposition is true, however, an algorithm for finding a counter-example will simply run forever. If a system is complete, then all its theorems are computable, because we can simultaneously check a statement and its negation, and by completeness, we will find one or the other true eventually, in finite amount of time.
An example of a non-Goldbach like proposition is "there are infinitely many primes p such that p+2 is also prime (we call these "prime pairs"). If this is false, a counterexample is a number k such that there are no prime pairs greater than k. Such a number may exist, but we cannot prove than any number k has this property by a finite algorithmic process.
This totally elementary analysis leads to one important conclusion. In a formal system that can do basic arithmetic, all propositions whose negation is Goldbach-like can be proved, and if the system is consistent, all propositions whose negation is Goldbach-like and can be proved, are true (the latter holds because if a Goldbach-like proposition is false, its negation can be proved, so a consistent system cannot also prove the proposition itself).
The connection between provability and truth is difficult only with respect to non-Goldbach propositions. The great mathematician David Hilbert, at the turn of the Twentieth Century, had the grand ambition to reduce all of mathematics to a finite algorithmic process, thus proving basic mathematical formal systems valid and complete. Kurt Gödel (with important additions provided later by Barkley Rosser, Sr.), in 1931 proved that in any consistent formal system with a certain amount of elementary arithmetic (e.g., PA), there statements of elementary arithmetic that can be neither proved nor disproved. Thus, if S is consistent, there are propositions about the natural numbers that are undecidable in S.
To understand why Gödel's theorem is true, as Franzén makes clear, we must understand the broad outlines of its proof. I confess that I found Franzén's explanation of Gödel numbering, fixpoint constructions, and self-reference statements inscrutable, so I will provide a really simple alternative (see Charlesworth, Mathematics Magazine 54,3 May 1981 for details).
Let us assume that our formal system S has a finite number of symbols, legal combinations of which we may call "formal statements," each of which is may be true or false. We think of a formal statement as containing no "free variables," whose value can affect the truth or falsity of the statement. We assume that given any sentence, there is a mechanical (algorithmic) process for determining whether or not it is a formal statement (i.e., it checks that the sentence is meaningful and does not have any "free variables.")
The system has axioms and rules of inference, so it produces theorems, which are the final lines of proofs, which in turn are sequences of axioms and the result of applying rules of inference to the axioms and other such products. Theorems are thus formal statements. Again, we can check mechanically to determine whether a sequence of sentences is or is not the proof of a theorem. We assume the system can perform negation (i.e. if f is a formal statement, then not-f is also a formal statement). Thus, we can say that the system is consistent if and only if does not prove both f and not-f for any formal statement f.
We assume that the system has a unique representation of each natural number k, and if one such representation is replaced by the representation of any other number in a formal statement, the result is another formal statement. We need a way of expressing functions f(x), where x is a "variable," in the system. We say that a sentence f is a "number predicate" if it is not a formal statement, but it has a recognizable segment that, when replaced by the systems representation for the number 1, becomes a formal statement (there is nothing special about 1, because above we have assumed any number can replace any other number in a formal expression). We write this expression as f(1), thereby defining f(n) for any natural number n.
Our final condition for the formal system is really the key assumption. It is not obviously true for such formal systems as PA and ZFC, but it is in fact true for these and many other systems, as Gödel showed. The assumption is that any computer program P that takes as input a single number and eventually stops, printing either "Yes" or "No" as its output, there is a number predicate fP in the system such that P prints "Yes" when given input n if and only if fP(n) is a theorem.
The rest is easy. With these assumptions, it is clear that a consistent system has a mechanical process (an algorithm) for generating all theorems. It does this by sifting through a list of all strings of the system, looking for proofs of theorems. For any formal statement, either it or its negation is a theorem, and since the system is consistent, eventually a mechanical process with find a proof of one or the other, and then stop. We say that the theorems of S are "computably enumerable." Similarly, there is an algorithm for generating a list of all number predicates f1, f2, f3, and so on. It follows that if the system is complete, there is an algorithm that determines whether any formal statement is a theorem.
We can now prove Gödel's theorem, which states that if our system has the above properties and is consistent, then it is incomplete; i.e., there is a formal statement that cannot be either proved or disproved. In other words, the set of non-theorems, while computable enumerable, is not computably decidable: given a sentence f that is not true but whose negation cannot be proved, we will search forever for a proof of f or not-f. To that when S is complete, there are meaningful sentences in S that are neither provable nor disprovable, assume the system is complete, so the algorithms described above actually exist. Consider a computer program P that, for input n, computes the number predicate fn, then computes whether or not fn(n) is a theorem using the above algorithms, and outputs "No" if fn(n) is a theorem, and "Yes" if fn(n) is not a theorem. By assumption, this program is has a corresponding number predicate. Say fm is the number predicate of P. Thus, by construction, P with input n prints "Yes" if and only if fm(n) is a theorem. It follows that P with input m prints "Yes" if and only if fm(m) is a theorem. But, we originally constructed P to say "No" when it sees input m if and only if its number predicate fm(m) is a theorem. Therefore, our original assumption that the system is complete is incorrect.
This proof makes it clear why the second Gödel theorem is true. This theorem, which Gödel proved informally shortly after his first proof, but was fully proved by Hilbert and Bernays some years after, is that in any consistent system with the above properties, the systems consistency cannot be proved within the system. Thus, if such a system proves its own consistency, then it must be inconsistent (and hence can prove anything). To see, the note that if there is a proof of consistency, this can be used to prove the existence of the algorithms described above, and hence the existence of the computer program P, which we have seen does not exist if the system is consistent.
The above argument seems to me extremely plausible, provided we are capable of showing that every computer program P that outputs "Yes" or "No" for all numerical inputs can be represented by a numerical predicate f(n) that is a theorem precisely when P prints "Yes." This seems quite provable.
Franzén's approach is closer to Gödel's, and less intuitive. First we give to each well-forms string of symbols in the formal system S a unique number, which we call the "Gödel number" of the string. We write the Gödel number of A as <A> (Franzén does not do this---he tries to avoid all mathematical notation). Suppose f is a numerical predicate, which is therefore either true or false when applied to any particular Gödel number. By a "fixpoint" numerical predicate for f we mean a sentence A such that "A if and only if f(<A>)" is a theorem of S. It is certainly not obvious that this construction is possible, but we'll take it on faith. Then, if f(n) asserts "n is not the Gödel number of a theorem of S," the fixpoint for f is denoted G, and is called a "Gödel sentence" for S. Thus, "G if and only if <G> is not the Gödel number of a theorem of S." However, if this sentence is a theorem, then it is provable that it is a theorem if S is consistent, since in this case we can go through all sentences looking for the proof of either G or not-G. This search necessarily halts, and if G is a theorem, it halts by proving this fact. Now, if G is a theorem, the <G> is not the Gödel number of a theorem of S, which is a contradiction.
Both Franzén's proof and the one I sketched use self-referencing sentences in a fundamental way. There is nothing wrong with this (unlike the supposed antinomies like Richard's Paradox, which involve inadmissible self-referencing), but Franzén show that there are computational proof that do not involve self-referencing at all.
Gödel's theorem proves that no consistent system that supports simple arithmetic can either prove its own consistency, or be a self-contained system of all mathematical truths. Some have claimed that this supports having a skeptical attitude towards mathematics, or even science. This is a mistake. One can have a skeptical attitude if one desires, but Gödel's theorem in no way supplies arguments in favor of skepticism. The fact that a formals system can prove its consistency is not a mark in favor of such a system, because an inconsistent system can always prove its consistency. Moreover, our confidence in the axioms of mathematical systems must ultimate come from an irreducible faith in them, based on evidence or reason. This remains true with or without Gödel's theorem.
This book puts it all straight - 'nuff said ;-)