Computability and logic.

Now in its fourth edition, this book has become a classic because of its accessibility to students without a mathematical background, and because it covers not only the staple topics of an intermediate logic course such as Godel's Incompleteness Theorems, but also a large number of optional topics from Turing's theory of computability to Ramsey's theorem. John Burgess has enhanced the book by adding a selection of problems at the end of each chapter.

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

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

Available:*

On Order

Summary

Summary

Table of Contents