Computability and Logic

ISBN: 9780521007580 出版年：2002 页码：370 Boolos Burgess Jeffrey Cambridge University Press

Part I. Computability Theory: 1. Enumerability 2. Diagonalization 3. Turing computability 4. Uncomputability 5. Abacus computability 6. Recursive functions 7. Recursive sets and relations 8. Equivalent definitions of computability Part II. Basic Metalogic: 9. A precis of first-order logic: syntax 10. A precis of first-order logic: semantics 11. The undecidability of first-order logic 12. Models 13. The existence of models 14. Proofs and completeness 15. Arithmetization 16. Representability of recursive functions 17. Indefinability, undecidability, incompleteness 18. The unprovability of consistency Part III. Further Topics: 19. Normal forms 20. The Craig interpolation theorem 21. Monadic and dyadic logic 22. Second-order logic 23. Arithmetical definability 24. Decidability of arithmetic without multiplication 25. Non-standard models 26. Ramsey's theorem 27. Modal logic and provability.