Book:George S. Boolos/Computability and Logic/Third Edition

George S. Boolos and Richard C. Jeffrey: Computability and Logic (3rd Edition)

Published $\text {1989}$, Cambridge University Press

ISBN 0-521-38923-2

Subject Matter

• Mathematical Logic

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-Löwenheim theorem

$14$ Representability in $Q$

$15$ Undecidability, undefinability 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 in arithmetic and forcing

$21$ The decidability of arithmetic with addition, but not multiplication

$22$ Dyadic 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

Next

Further Editions

• 1974: George S. Boolos and Richard C. Jeffrey: Computability and Logic
• 1980: George S. Boolos and Richard C. Jeffrey: Computability and Logic (2nd ed.)
• 2002: George S. Boolos, Richard C. Jeffrey and John P. Burgess: Computability and Logic (4th ed.)
• 2007: George S. Boolos, John P. Burgess and Richard C. Jeffrey: Computability and Logic (5th ed.)

Source work progress

• 1989: George S. Boolos and Richard C. Jeffrey: Computability and Logic (3rd ed.) ... (previous): $1$ Enumerability

In-depth discussion about partial functions and enumerations which needs attention