An Introduction to Gödel's Theorems

Table of Contents

Preface
1. What Gödel's theorems say
2. Functions and enumerations
3. Effective computability
4. Effectively axiomatized theories
5. Capturing numerical properties
6. The truths of arithmetic
7. Sufficiently strong arithmetics
8. Interlude: taking stock
9. Induction
10. Two formalized arithmetics
11. What Q can prove
12. I∆o, an arithmetic with induction
13. First-order Peano arithmetic
14. Primitive recursive functions
15. LA can express every p.r. function
16. Capturing functions
17. Q is p.r. adequate
18. Interlude: a very little about Principia
19. The arithmetization of syntax
20. Arithmetization in more detail
21. PA is incomplete
22. Gödel's First Theorem
23. Interlude: about the First Theorem
24. The Diagonalization Lemma
25. Rosser's proof
26. Broadening the scope
27. Tarski's Theorem
28. Speed-up
29. Second-order arithmetics
30. Interlude: incompleteness and Isaacson's thesis
31. Gödel's Second Theorem for PA
32. On the 'unprovability of consistency'
33. Generalizing the Second Theorem
34. Löb's Theorem and other matters
35. Deriving the derivability conditions
36. 'The best and most general version'
37. Interlude: the Second Theorem, Hilbert, minds and machines
38. μ-Recursive functions
39. Q is recursively adequate
40. Undecidability and incompleteness
41. Turing machines
42. Turing machines and recursiveness
43. Halting and incompleteness
44. The Church–Turing thesis
45. Proving the thesis?
46. Looking back.

Look Inside

• Index (767 KB)
• Copyright Information Page (122 KB)
• Front Matter (1131 KB)
• Marketing Excerpt (1103 KB)
• Table of Contents (925 KB)