## An Introduction to Gödel's TheoremsIn 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 |

### Other editions - View all

### Common terms and phrases

A0 wff algorithm argument assuming assumption axiomatized theory axioms basic arithmetic captures chapter characteristic function Church’s Thesis claim code number computable functions consistency proofs consistent deﬁned deﬁnition Diagonalization Lemma effectively axiomatized effectively decidable effectively enumerable Entscheidungsproblem equivalent example express ﬁnd ﬁnite ﬁrst ﬁrst—order ﬁxed point follows formal language formal theory function f G6del numbers G6del sentence Gbdel given Godel halts Hence idea incompleteness theorem inﬁnite input interpretation intuitive language logic mathematics natural numbers negation—complete nice theory notion numerical properties one—place open wff p.r. function PA’s predicate primitive recursive primitive recursive function provable prove quantiﬁers recursive function recursively decidable reﬂection relation result Robinson Arithmetic scanned cell Second Theorem second—order Section semantic sequence sets of numbers successor suﬁiciently Suppose symbols syntactic theory of arithmetic there’s total function trivially true truths Turing machine u—recursive undecidable unprovable w—consistent we’ll wﬁ zero