Computability and logic

Author(s)

Bibliographic Information

Computability and logic

George S. Boolos, Richard C. Jeffrey

Cambridge University Press, 1989

3rd ed

  • : pbk

Available at  / 44 libraries

Search this Book/Journal

Note

Includes bibliographical references and index

Description and Table of Contents

Description

A text for a second course in logic for graduate and advanced undergraduate students. This third edition has been corrected and contains thoroughly revised versions of the chapters on Ramsey and provability, with new exercises provided for three other chapters. There are also two new chapters dealing with undecidable sentences and on the non-existence of non-standard recursive models of Z.

Table of Contents

  • 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-Loewenheim 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.

by "Nielsen BookData"

Details

Page Top