Computability and Logic

Preface; Preface to the third edition; 1. Enumerability; 2. Diagonalization; 3. Turing machines; 4. Uncomputability via the busy beaver problem; 5. Uncomputability via diagonalization; 6. Abacus computable functions are Turing computable; 7. Recursive functions are abacus computable; 8. Turing computable functions are recursive; 9. First-order logic revisited; 10. First-order logic is undecidable; 11. First-order logic formalized: derivations and soundness; 12. Completeness of the formalization: compactness; 13. The Skolem-Löwenheim theorem; 14. Representability in Q; 15. Undecidability, indefinability and incompleteness; 16. Provability predicates and the unprovability of consistency; 17. Non-standard models of arithmetic; 18. Second-order logic; 19. On defining arithmetical truth; 20. Definability arithmetic and forcing; 21. The decidability of arithmetic with addition, but not multiplication; 22. Dynadic logic is undecidable: ‘eliminating’ names and function symbols; 23. The Craig interpolation lemma; 24. Two applications of Craig‘s lemma; 25. Monadic versus dyadic logic; 26. Ramsey’s theorem; 27. Provability considered modal-logically; 28. Undecidable sentences; 29. Non-standard models of Z are not recursive; Index.