Godel's Incompleteness TheoremsKurt Godel, the greatest logician of our time, startled the world of mathematics in 1931 with his Theorem of Undecidability, which showed that some statements in mathematics are inherently "undecidable." His work on the completeness of logic, the incompleteness of number theory, and the consistency of the axiom of choice and the continuum theory brought him further worldwide fame. In this introductory volume, Raymond Smullyan, himself a well-known logician, guides the reader through the fascinating world of Godel's incompleteness theorems. The level of presentation is suitable for anyone with a basic acquaintance with mathematical logic. As a clear, concise introduction to a difficult but essential subject, the book will appeal to mathematicians, philosophers, and computer scientists. |
Contents
The General Idea Behind Gödels Proof | 1 |
Tarskis Theorem for Arithmetic | 14 |
The Incompleteness of Peano Arithmetic With Exponentiation | 28 |
Arithmetic Without the Exponential | 40 |
Gödels Proof Based on 969Consistency | 56 |
Rosser Systems | 75 |
Shepherdsons Representation Theorems | 86 |
Other editions - View all
Common terms and phrases
25 are provable Arithmetic set axiom scheme axiom system base 10 notation base 13 believe Bp Boolos C₁ called consistent axiomatizable Corollary disjoint Do-formula Do-sentences are provable E-formula E₁-sets En(n Exercise expresses the set F(v₁ first-order logic formula F(v1 formulas of 24 free occurrences free variable G is provable Gödel number Gödel sentence Gödel's incompleteness theorem Gödel's second H(v₁ Hence incompleteness theorem induction knave knight last chapter Lemma Löb's Theorem mathematical induction modal logic modus ponens native natural numbers never believe number n Peano Arithmetic printable proof of Theorem propositional logic provability predicate provable in P.A. provable sentences reasoner believes reasoner of type recursive refutable relation xy representable Rosser system sentence G sentences F(0 sequence number set of Gödel simply consistent strongly definable subsystem Suppose symbols system P.A. Tarski's theorem true Do-sentences true iff true sentence undecidable v₁ v₂ w-consistent w-inconsistent Σ₁ Σο