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

From ProofWiki
Jump to navigation Jump to search

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


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


Source work progress

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