Cover image for Computability and logic.
Title:
Computability and logic.
Author:
Boolos, George.
Personal Author:
Edition:
Fourth edition / George S. Boolos, John P. Burgess, Richard C. Jeffrey.
Publication Information:
Cambridge ; New York : Cambridge University Press, [2002]

©2002
Physical Description:
xi, 356 pages : illustrations ; 26 cm
Language:
English
ISBN:
9780521809757

9780521007580
Format :
Book

Available:*

Library
Call Number
Material Type
Home Location
Status
Item Holds
Searching...
QA9.59 .B66 2002 Adult Non-Fiction Non-Fiction Area
Searching...

On Order

Summary

Summary

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.


Table of Contents

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