After the last two posts by V. A. Uspenskii (check out his site here) which dealt with Post’s Machine, and Pascal’s Triangle, we now come to another book by him in the Little Mathematics Library series titled Gödel’s Incompleteness Theorem.
The back cover of the book reads:
Few discoveries have had as much impact on our perception of human thought as Gödel’s proof in 1930 that any logical system such as usual rules of arithmetic, must be inevitably incomplete, i.e., must contain statements which are true but can never be proved. Professor Uspensky’s makes both a precise statement and also a proof of Gödel’s startling theorem understandable to someone without any advanced mathematical training, such as college students or even ambitious high school student. Also, Uspensky introduces a new method of proving the theorem, based on the theory of algorithms which is taking on increasing importance in modern mathematics because of its connection with computers. This book is recommended for students of mathematics, computer science, and philosophy and for scientific layman interested in logical problems of deductive thought.
The book was translated from the Russian by Neal Koblitz and was first published by Mir in 1987.
Thanks to hawa-ka-jhonka who made this book accessible.
For magnet / torrent links go here.
The contents of the book are as under:
1. Statement of the Problem. 9
2. Basic Concepts from the Theory of Algorithms and Their Application 13
3. The Simplest Incompleteness Criteria 22
4. The Language af Arithmetic 25
5. Three Axioms for the Theory of Algorithms 32
A. The Syntactic and Semantic Formulations of the Incompleteness Theorem 42
B. Arithmetic Sets and Tarski’s Theorem on the Nonarithmeticity of the Set of True Formulas of the Language of Arithmetic 46
C. The Language of Address Programs, the Extended Language of Arithmetic, and the Arithmeticity Axiom 53
D. Languages Connected with Associative Calculi 78
E. Historical Remarks 83
F. Exercises 87
Exercises for Sec. 2 87
Exercises for Sec. 3 89
Exercises for Sec. 4 90
Exercises for Sec. 5 91
Exercises for Appendix A 92
Exercises lor Appendix B 93
Exercises for Appendix C 93
Exercises for Appendix D 94
G. Answers and Hints for the Exercises 96