Customer Reviews

On Formally Undecidable Propositions of Principia Mathematica and Related Systems

5 star:		(11)
4 star:		(0)
3 star:		(3)
2 star:		(0)
1 star:		(0)

 

 

Reading through the reviews of self-proclaimed math geniuses (see some of the below unhelpful reviews for examples) is hardly edifying, so I feel compelled to lend a hand. Here are a few comments about this publication:

First, the introduction does a poor job in explicating the theory. I suppose it gives you the basic idea, but this is hardly the first account of the theory one should read. Brathwaite does not connect all of the dots, and it will take a long time to figure out how the proof works from his intro, if you can do it all. (And that's not a challenge or insult; it simply isn't that well written.)

Second, forget about wading through Godel's proof on your own. The reviewer who claimed to do so with two years of algebra and a really good dictionary is simply lying. You do not wade through difficult theorems in mathematical logic without the appropriate tools. And the appropriate tools include having done similar but simpler proofs on your own and having a solid background in mathematical logic. Without this background, it doesn't matter whether you have the ability to be a mathematics professor at Princeton or place top five in the Putnam - you simply will not understand the proof in a rigorous manner. By all means, take a look at it to get a general feel for what's going on, but if you want a semi-technical account read Smullyan's "Godel's Incompleteness Theorems."

Third, as one reviewer pointed out, there are multiple errors in this printing of the proof. This makes what was a tall task virtually impossible.

So what did Godel do that was so interesting?
He proved that there were certain arithmetical statements about whole numbers that were not provable but true. (This was important because it shattered the widely held belief that if you stated a problem in mathematics clearly enough you would be able to determine whether it was true or false. Godel showed this isn't always the case. As an aside, simpler mathematical systems have been shown complete; that is to say, they can answer any well formed question.)
So, how can something be true but unprovable?
The sentence Godel constructed said this, more or less: I am not provable. This statement, if true, is not provable. If it is provable it's false, and correct systems (systems that do not prove false statements) cannot prove false statements. Therefore, it must not be provable. But then it's saying something true, and thus it's true but unprovable. Now, I'm simplifying and being sloppy, and you need to know about the difference between mathematical statements and metamathematical statements, but in a nutshell that's the thrust of his first theorem.

The other interesting aspect of his proof is that he constructed a statement that referred to itself indirectly. Russell, in Principia Mathematica - the work that contains the arithmetical system that served as the model for the arithmetical system in Godel's proof - created a "Theory of Types" which did not allow statements to mention themselves. But the sentence "I am not provable" references itself so it would seem that I've erred. But in fact I haven't; I just didn't fully explain how that sentence worked. (I know you were worried, if for just an instant.) Where was I . . . Godel created a sentence which referred to itself indirectly. The sentenced said, "Sentences with such and such characteristics are unprovable." It so happened that a sentence with such characteristics was itself. Thus, it referred to itself, but only indirectly and not in violation of the "Theory of Types."

All of my blathering, I hope, has impressed on you . . .
1) That this proof is worth understanding.
2) That you shouldn't believe anyone who tells you they worked through and understood the proof without having a signficant background in mathematical logic and the history of the proof. If you don't understand certain basic features of Principia Mathematica you're not going to grasp fully his proof.
3) That you should get an introductory account. Nagle's "Godel's Proof" is excellent and easy to understand. Smullyan's "Godel's Incompleteness Theorems" is more difficult, but not impossible and amounts to what would serve as the textbook of a solid mathematical logic course or two at an elite university.
4) That you shouldn't buy this work if you're hoping to work through his proof, unless of course you have the requisite training. Brain power is not enough.

Anyone who wants to trace this proof is free to do so. Though the formal logic can be formidable, and must be learned before tackling the proof, only the basic structure is necessary and it is not difficult to learn. It is also necessary to know a little about prime numbers, specifically that every composite number can be decomposed into some unique group of prime factors. Otherwise, all the technical aspects of the proof (barring the conclusion of theorem VI and a bit of the recursion) can be perfectly understood by someone outside of the world of formal mathmatics.

The proof itself is meant for a professional mathmatician. If you are interested and willing this will not dissuade you. To say Godel was not a master of exposition is misleading for he is ,if nothing else, just that. I have heard working through the proof compared to a mystical experience and the proof itself to a symphony. It is truly beautiful to even the mere math enthusiast. Godel is not, however, a college professor and does not wish to explain what need not be explained. This will not be of much consolation when he prefaces a statement with, "of course," for the twentieth time and you have no idea what he is talking about. But if you are not afraid to go ahead when you have tried and failed to understand, and are not afraid to return when you have gained some small piece of the puzzle and try again, everything will come clear. This is the original. All the commentaries are great, and some are even helpful before you get to the conclusion, but they are not the proof and should not be taken as a substitute. They do not suffice the way a generic drug does. There is no way to understand the full scope of the proof if you are not willing to immerse yourself in it and the language it uses. Everything in it is self-referential, you miss the reference when you skip the proof.

Don't worry if it seems to be going nowhere, because you'll get there soon enough yourself and it turns out everything matters(although nothing has meaning). If you want you can skip everything after theorem VI is proved up to the beginning of theorem XI. Then you will have everything you read about.

Perhaps, if you can, you should get a couple other people to work through it with; different perspectives make all the difference, even in math. It's nice to have someone to share your frustration with and sometimes to have it relieved. Plus the delight of watching the theorem build like a wave and crash down upon itself is best shared with others.

Last, and particularly directed toward anyone at DOVER: The proof as you have printed it is horribly mangled! There are countless misprints (more than fifty). This is bad enough in prose but absolutely disgusting in a math text. The second to last line of theorem VI (the proof of undecidability) has a misprint to the effect of changing a negative statement into a positive one. The proof is hard enough as it is. There is a much better translation (without any misprints) in "Frege and Godel" and "From Frege to Godel," which are sadly out of print but may be found at a library. The DOVER is cheap and it reads that way.

If you're interested, do it, and don't worry about it being too hard. You will realize the technical aspects are almost all quite easy when you plow through them. So wade in and enjoy!

This book is a translation of one of the most important papers in 20th-century mathematics. It's wonderful that Dover has published it at such a cheap price, so everyone interested in the incompleteness theorems can take a look at it. However, I should warn potential readers that it is _not_ the best introduction, for three reasons:

(1) Goedel was not the world's greatest expositor.

(2) We now have nearly 70 years worth of insight Goedel didn't have when writing this paper.

(3) Goedel never intended the paper to be read by anyone but professional mathematicians.

Non-mathematicians who really want to understand this material should also take a look at "Goedel's Proof" by Nagel and Newman (and perhaps Hofstadter's "Goedel, Escher, Bach: An Eternal Golden Braid" for cultural background). Mathematicians can find lots of more technical expositions.

The original paper should not be the only source one tries to learn from, but I think it can be very valuable to take a look at it side-by-side with more modern treatments to get a feeling for how the ideas really arose. In principle one could learn everything straight from the source, but it just isn't the most efficient way. (I say this as a professional who has read the original paper and lots of other accounts of the proof, as well as written one of my own.)

Net recommendation: this book is so cheap that one should buy it and a modern treatment.

THE proof as Goedel wrote it (plus typos). I have seen modern proofs of this theorem which are much easier to follow (as an example, a Mir book on mathematical logic by a Russian mathematician whose name I cannot recall), but this one is the REAL thing.

Modern proofs can be much clearer, but the original always has an added value. The writing style is not the best, but by reading this version you get a clearer idea of how Goedel came up with his theorem and the many difficulties he faced. Remember, by the time most of us read or heard about this for the first time, mathematical logic had advanced quite a few decades.

Speaking not as a math specialist but one disposed to read a number of the popular explications of Godel's famous proof I can say that it was Godel's original text that did it for me. The reason is that it is the proof and not a lot of verbiage about the proof. And it is short and sweet. One problem is that the more common Turing Machine approach is actually 'easier', where Godel's approach is that of recursive functions which are more obscure, or at least less often discussed. If you can sort of glare at the recursive function issue and proceed with the basics of the proof it will stand out suddenly better than many of the popularizations. At least give it a try.

Godel's incompleteness theorem's are without a doubt genious. However, this day in age, no logician actually reads Godel's original work unless they are only interested in the historical aspect of it. Godel himself is not a very good writer. If you want to study Godel's incompleteness theorems there are other books out there that prove his theorems in a much more refined, shorter, and easier fasion.

Gödel proves that a formal system containing arithmetic must be incomplete (i.e. incapable of proving all true statements). The proof consists in creating a statement that says "this statement cannot be proved", for then it follows that either this this statement can be proved and we have proved something false, or it cannot be proved but it is still true. In either case our formal system is flawed. This is in a way an instance of the liar paradox, which was of course well know long before, but no-one had expected it to materialise inside a seemingly sensible formal system. Gödel shows that it does by means of his arithmetisation trick that enables the system to speak about itself. All symbols in the system's alphabet is given a unique number. Then all formulas in the system is assigned the following number: the product of all the factors (n:th prime)^(n:th symbol in the formula). By unique prime factorisation one can recreate the formula from its number. Sequences of formulas---proofs in particular---can be coded by the same method. We can now express the relation "x is a proof of y" inside the formal system. This relation takes two arguments: x*, the Gödel number for the sequence of formulas x, and y*, the Gödel number for the formula y. Inside the formal system it is a perfectly well defined and finite problem to decide whether x is a proof of y, as is quite plausible, although Gödel has to work hard with his recursion theory to prove this strictly. Now that we can express "x is a proof of y" we can also express "x is a proof of y(z)", i.e. a relation that takes three arguments: x*, y*, z*, the Gödel numbers for a sequence x of formulas, a formula y with a free variable, and a formula z. Thus we can also express "there exists no x such that x is a proof of y(z)". In particular, we can send in y* for z, and the statement becomes: "there exists no x such that x is a proof of y(y*)". This expression has one free variable, y. Call it F(y). F(y) is a formula in our formal system, so it has a Gödel number, say F*. Now we can formulate the statement "this statement cannot be proved" inside our formal system as follows: "F(F*)"="there exists no x such that x is a proof of F(F*)"="F(F*) cannot be proved". So if our formal system is consistent (i.e. does not prove false things) then we must accept that it cannot prove F(F*), but then F(F*) is true, so our formal system is incomplete.

This is indeed one of the most influential treatises of all time. In a nutshell, Godel's Undecidability Theorem proved that within a formal system, there are questions that exist which are neither provable nor disprovable on the basis of the axioms that define the system. He also showed that in formal system, a decidability of all questions is required. Given that, there will be contradictory and unfinished statements. This makes up his Incompleteness Theorem.

With these two theorems, Godel showed that there are problems that simply can't be solved by any set of rules or procedures.

This disproved a common belief at the time (primarily via Whitehead & Russell in Principia Mathematica) that mathematics could be completely integrated into a single foundation of logic.

For those that had attempted to make a deity out of logic and mathematics, Godel simply nailed their coffin closed. Mathematics indeed has its limits.

While I found the underlying logic and proofs often perplexing, the importance of the book can't be overemphasized.

As other reviewers have noted, there are numerous easier expositions of the work Godel reports in his 1931 paper. Before you tackle the 1931 paper itself, read and internalize at least a couple of those. But then it's very worth while to struggle through the 1931 paper, obscurities, typos and all. Why? Because Godel somehow was led to think in a direction that was almost inconceivable in 1930 (when he completed the work and this paper). Now, in 2011, I can glibly say that there can be no consistent formal axiomatization including addition and multiplication for the natural numbers that is also complete. I can say that as glibly as a stage magician can pull a rabbit out of a hat. But consider the situation of mathematics from 1900 to 1930. Almost all mathematicians of that era would have taken it for granted that a consistent and complete formal axiomatization was possible, even though none had been demonstrated. Then Godel overturned this conventional wisdom. The interest of the paper is less what's in it (which by now has been expressed more simply and clearly by others) than the clues the paper gives into how Godel thought, and the painful process of slowly coming to the conclusion that everybody's conventional wisdom was wrong.

Compare this to the proof of "Fermat's Last Theorem"; this latter requires a great deal more machinery, and a huge amount of exposition, but for a number of years before "Fermat's Last Theorem" was finally proved, a high proportion of good mathematicians thought that it ought to be true, and that what was needed was a proof. Andrew Wiles came up with a proof, a very difficult proof, but none the less a proof of something one might have expected and hoped would be true. Godel, however, was groping into the unknown, and the thought processes that led to his paper must have led him to question his own reasoning over and over again. This shows most clearly in some of the footnotes, in which he is convincing not only his reader but himself. It's a very unusual insight into the mental processes of a great mathematician.

Wow! If you don't already own this, and you know anything about advanced number theory, buy it now! You should also probably pick up a deciphering guide, as well, because the symbolism is quite intense in places. A true classic with a deserved place in any 'Mathmatical Recreationalists' shelf.