Boolos G. Computability and Logic 5ed 2007

Textbook in PDF format

Computability and Logichas become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as G¨ odel’s incompleteness theorems, but also a large number of optional topics, from Turing’s theory of computability to Ramsey’s theorem. This fifth edition has been thoroughly revised by John P. Burgess. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, a traditional stumbling block for students on the way to the G¨ odel incompleteness theorems. This new edition is also accompanied by a Web site as well as an instructor’s manual.
Preface to the Fifth Edition.
COMPUTABILITY THEORY.
Enumerability.
Diagonalization.
Turing Computability.
Uncomputability.
Abacus Computability.
Recursive Functions.
Recursive Sets and Relations.
Equivalent Definitions of Computability.
BASIC METALOGIC.
A Precis of First-Order Logic Syntax.
A Precis of First-Order Logic Semantics.
The Undecidability of First-Order Logic.
Models.
The Existence of Models.
Proofs and Completeness.
Arithmetization.
Representability of Recursive Functions.
Indefinability, Undecidability, Incompleteness.
The Unprovability of Consistency.
FURTHER TOPICS.
Normal Forms.
The Craig Interpolation Theorem.
Monadic and Dyadic Logic.
Second-Order Logic.
Arithmetical Definability.
Decidability of Arithmetic without Multiplication.
Nonstandard Models.
Ramsey’s Theorem.
Modal Logic and Provability.
Annotated Bibliography