On Formally Undecidable Propositions of Principia Mathematica and Related Systems |
|
|
List Price: $6.95
Our Price: $6.95
Availability: Usually ships in 24 hours
Manufacturer: Dover Publications
Average Customer Rating:  
|
| |
PRODUCT DESCRIPTION
Binding: Paperback
Dewey Decimal Number: 511.3
EAN: 9780486669809
ISBN: 0486669807
Label: Dover Publications
Manufacturer: Dover Publications
Number Of Items: 1
Number Of Pages: 80
Publication Date: 1992-04-01
Publisher: Dover Publications
Studio: Dover Publications
|
|
|
|
|
|
Editorial Reviews:
|
First English translation of revolutionary paper (1931) that established that even in elementary parts of arithmetic, there are propositions which cannot be proved or disproved within the system. It is thus uncertain that the basic axioms of arithmetic will not give rise to contradictions. Introduction by R. B. Braithwaite.
|
|
|
Spotlight customer reviews:
|
Customer Rating: 
Summary: Mathematical Rationalism has limits
Comment: It is very hard to find faults in what may be the most famous proof of the 20th century.
For those not familiar with the Russell-Whitehead Principia Mathematica notation
this is a very hard book. I had the benefit of the Kac-Ulam explanation.
I did find what might be problems with this proof.
1) One is the reliance on number theory proofs about prime numbers that are assumed true
in the Gödelization of the primes coding of the mathematical axioms.
2) The second is the assumption that the axioms statements represent the minimal
representation of such a system of axioms.
Both are slim if none chances, but ones the Gödel doesn't consider.
Information theory was after this time where we discovered that a system of symbols can indeed at times be more efficiently coded.
The best example of this seems to be Gray code compared to ordinary binary number code ( a number theory code
like Gödel's prime code) where less turns out to be more in information terms.
The theory of primes suffers from the new doctrine of strings that says
that infinite scales don't exist in the "real" world: that a maximum and a minimum
of measure are fixed parts of our reality. This kind of assumption can't be "proved"
but is an axiom of a system of a mathematical sort and is counter to the Euclidean proof of an infinite number of primes.
Primes already discovered by use of computers are much bigger than the numbers of ordinary physics, but
we are already reaching the Turing "stopping" problem in finding new ones.
Some people equate in algorithmic information theory and number theory
the stopping problem with Infinity. That point of view of people like G. J. Chaitin
is itself an unproved assumption. So the metamathematics used in the proof itself may be unprovable propositions.
If so, then the proof based on such propositions can't itself be true.
This argument in no way takes away from the greatness of Gödel and his unique genius
as shown by this line of reasoning.
Customer Rating:
Summary: The following is a dissenting view
Comment: As indicated in two other reviews of mine here, my comprehension of Goedel's work is opposite to the general one. My marking three stars regardless for this book is motivated by his extensive influence, but also by his fair admission later in life that his thesis could amount to hocus-pocus.
Indeed, I see it as one of the prominent mistakes in logical history, and I shall endeavor to explain as best I can. It should suffice to consider his Section 1, an outline of his proposed proof.
Although that section is brief, it already foreshadows an oppressingly complex logical symbolism for statements that in my view can be made much clearer using ordinary language. The symbolism, to be sure, is intended to establish a formal language, whose meaning is to be decided separately. This will be seen one of the problems.
For now, let me give the principal statement Goedel contended to be true but undecidable (neither provable nor disprovable):
"This statement is unprovable."
He symbolized it (p.40) as: "~Bew[R(n);n]". Font limitations made me slightly change it; the tilde "~" means "not", "Bew" is a German abbreviation for "provable", and within brackets "R(n)" says "Statement n" and "n" stands for the full statement.
Goedel proceeds: "...supposing...~Bew[R(n);n] were provable, it would also be correct; but that means...that...~Bew[R(n);n] would hold good, in contradiction to our initial assumption. If, on the contrary, the negation of ~Bew[R(n);n] were provable, then [its provability] would hold good. ~Bew[R(n);n] would thus be provable [in contradiction to the unprovability it states], which again is impossible." (I corrected some errors within brackets.)
So since both ~Bew[R(n);n] and its negation are unprovable, it is undecidable, and Goedel continues (p.41): "...it follows at once that ~Bew[R(n);n] is correct, since...certainly unprovable (because undecidable). So the proposition which is undecidable in the system...turns out to be decided by metamathematical considerations."
"Metamathematical", in excusing the contradiction, designates the above formal system void of assigned meaning, whereas the statement discussed is to have meaning. Not quite a lucid argument. Overlooked, furthermore, is a contradiction using the same reasoning as in the preceding.
Coupled with the preceding finding that ~Bew[R(n);n] CANNOT be proved unprovable (for if so proved, it would be contradicted), can in contradiction be that it CAN be proved unprovable. For if it were instead provable, it would again be contradicted. The statement in question thus becomes a paradox, rather than true, similar to paradoxes like the "liar", mentioned by Goedel (p.40).
He strangely adds to it the footnote: "Every epistemological [paradox] can likewise be used for a similar undecidability proof." The "liar", however, is, like all paradoxes, not a true statement, as required, but one harboring a contradiction. (I deal in my book with, and offer solutions to, paradoxes more fully, including Goedel's resulting one, without naming him.)
There occurs, further, another huge blunder in the alleged proof. The undecidability is said to apply to some of mathematics; in the above formula, ~Bew[R(n);n], the "n" refers to a number, with this justification by Goedel (p.38): "For metamathematical purposes it is naturally immaterial what objects are taken as basic signs, and we propose to use natural numbers for them." Adding (p.39): "Metamathematical concepts and propositions thereby become concepts and propositions concerning natural numbers..."
How so? In one breath he proposes using natural numbers as immaterial signs, and in the next breath the material concerns natural numbers!
The fallaciousness can indeed be made clear by considering our statement, ~Bew[R(n);n], interpreted as "This statement is unprovable." As noted, in ~Bew[R(n);n] the "n", now a number, is to name the whole statement, inside which it is also used in "Statement n..." But whether or not the statement is named by a number, the point is that the name must refer to the intended content of the statement to correspondingly function, not to the usual number possibly represented. Therefore the statement, or anything else similarly used, has nothing to do with numbers, or mathematics generally.
Customer Rating:
Summary: Gödel's proof of the inadequacy of formalism
Comment: 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.
Customer Rating:
Summary: One of the Best Books You Should Never Read
Comment: 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.
Customer Rating:
Summary: Unbelievable theorem
Comment: 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.
|
|
|
|
|
|
|
|
