An Introduction to Gödel's Theorems

Front Cover
Cambridge University Press, Feb 21, 2013 - Mathematics - 388 pages
1 Review
In 1931, the young Kurt Gödel published his First Incompleteness Theorem, which tells us that, for any sufficiently rich theory of arithmetic, there are some arithmetical truths the theory cannot prove. This remarkable result is among the most intriguing (and most misunderstood) in logic. Gödel also outlined an equally significant Second Incompleteness Theorem. How are these Theorems established, and why do they matter? Peter Smith answers these questions by presenting an unusual variety of proofs for the First Theorem, showing how to prove the Second Theorem, and exploring a family of related results (including some not easily available elsewhere). The formal explanations are interwoven with discussions of the wider significance of the two Theorems. This book - extensively rewritten for its second edition - will be accessible to philosophy students with a limited formal background. It is equally suitable for mathematics students taking a first course in mathematical logic.
 

What people are saying - Write a review

User Review - Flag as inappropriate

I have read the first edition of this title and have found it to be one of the best, if not _the_ best introductions to the topic (possibly second only to Boolos et. al. "Computability and Logic". I am looking forward to the 2nd Edition.
Please note that at present (October 2013) the 'View Ebook' link on the page for the 2nd edition takes you to the purchase page for the *1st* edition ebook. Caveat Emptor.
Google, when this was pointed out to them, suggested I contact Peter Smith to get the issue corrected.
 

Contents

Functions and enumerations
8
Effective computability
14
Effectively axiomatized theories
25
Capturing numerical properties
36
The truths of arithmetic
46
Induction
56
What Q can prove
71
Firstorder Peano Arithmetic
90
Speedup
201
Incompleteness and lsaacsons Thesis
219
Godels Second Theorem For PA
233
On the unprovability of consistency
239
Generalizing the Second Theorem
245
Lobs Theorem and other matters
252
Deriving the derivability conditions
258
The Second Theorem Hilbert minds and machines
272

l5 LA can express every p r function
113
A very little about Principia
130
The arithmetization of syntax
136
2O Arithmetization in more detail
144
PA is incomplete
152
Godels First Theorem
161
About the First Theorem
167
The Diagonalization Lemma
177
Rossers proof
185
Broadening the scope
191
Tarskis Theorem
197
u Recu rsive fu nctions
285
Q is recursively adequate
297
Turing machines
310
Turing machines and recursiveness
321
Halting and incompleteness
328
The ChurchTu ring Thesis
338
Proving the Thesis?
348
Looking back
367
Index
383
Copyright

Other editions - View all

Common terms and phrases

About the author (2013)

Peter Smith was formerly Senior Lecturer in Philosophy at the University of Cambridge. His books include Explaining Chaos (1998) and An Introduction to Formal Logic (2003) and he is also a former editor of the journal Analysis.

Bibliographic information