Computability and logic.

Format:

Book

Author/Creator:

Boolos, George.

Contributor:

Burgess, John P., 1948-

Jeffrey, Richard C.

Language:

English

Subjects (All):

Computable functions.

Recursive functions.

Logic, Symbolic and mathematical.

Physical Description:

xi, 356 pages : illustrations ; 27 cm

Edition:

Fourth edition / George S. Boolos, John P. Burgess, Richard C. Jeffrey.

Place of Publication:

Cambridge ; New York : Cambridge University Press, 2002.

Summary:

Now in its fourth edition, this book on logic has been enhanced and rewritten.

Contents:

Computability Theory

1 Enumerability 3

1.2 Enumerable Sets 7

2 Diagonalization 16

3 Turing Computability 23

4 Uncomputability 35

4.1 The Halting Problem 35

4.2 The Productivity Function 40

5 Abacus Computability 45

5.1 Abacus Machines 45

5.2 Simulating Abacus Machines by Turing Machines 51

5.3 The Scope of Abacus Computability 57

6 Recursive Functions 63

6.1 Primitive Recursive Functions 63

6.2 Minimization 70

7 Recursive Sets and Relations 73

7.1 Recursive Relations 73

7.2 Semirecursive Relations 80

7.3 Further Examples 83

8 Equivalent Definitions of Computability 88

8.1 Coding Turing Computations 88

8.2 Universal Turing Machines 94

8.3 Recursively Enumerable Sets 96

Basic Metalogic

9 A Precis of First-Order Logic: Syntax 101

9.1 First-Order Logic 101

9.2 Syntax 106

10 A Precis of First-Order Logic: Semantics 114

10.1 Semantics 114

10.2 Metalogical Notions 119

11 The Undecidability of First-Order Logic 126

11.1 Logic and Turing Machines 126

11.2 Logic and Primitive Recursive Functions 132

12 Models 137

12.1 The Size and Number of Models 137

12.2 Equivalence Relations 142

12.3 The Lowenheim-Skolem and Compactness Theorems 146

13 The Existence of Models 153

13.1 Outline of the Proof 153

13.5 Nonenumerable Languages 162

14 Proofs and Completeness 166

14.1 Sequent Calculus 166

14.2 Soundness and Completeness 174

14.3 Other Proof Procedures and Hilbert's Thesis 179

15 Arithmetization 187

15.1 Arithmetization of Syntax 187

15.2 Godel Numbers 192

15.3 More Godel Numbers 196

16 Representability of Recursive Functions 199

16.1 Arithmetical Definability 199

16.2 Minimal Arithmetic and Representability 207

16.3 Mathematical Induction 212

16.4 Robinson Arithmetic 215

17 Indefinability, Undecidability, Incompleteness 221

17.1 The Diagonal Lemma and the Limitative Theorems 221

17.2 Undecidable Sentences 225

17.3 Undecidable Sentences without the Diagonal Lemma 227

18 The Unprovability of Consistency 233

Further Topics

19 Normal Forms 243

19.1 Disjunctive and Prenex Normal Forms 243

19.2 Skolem Normal Form 247

19.3 Herbrand's Theorem 253

19.4 Eliminating Function Symbols and Identity 255

20 The Craig Interpolation Theorem 260

20.1 Craig's Theorem and Its Proof 260

20.2 Robinson's Joint Consistency Theorem 264

20.3 Beth's Definability Theorem 265

21 Monadic and Dyadic Logic 270

21.1 Solvable and Unsolvable Decision Problems 270

21.2 Monadic Logic 273

21.3 Dyadic Logic 275

22 Second-Order Logic 279

23 Arithmetical Definability 286

23.1 Arithmetical Definability and Truth 286

23.2 Arithmetical Definability and Forcing 289

24 Decidability of Arithmetic without Multiplication 295

25 Nonstandard Models 302

25.1 Order in Nonstandard Models 302

25.2 Operations in Nonstandard Models 306

25.3 Nonstandard Models of Analysis 312

26 Ramsey's Theorem 319

26.1 Ramsey's Theorem: Finitary and Infinitary 319

26.2 Konig's Lemma 322

27 Modal Logic and Provability 327

27.1 Modal Logic 327

27.2 The Logic of Provability 334

27.3 The Fixed Point and Normal Form Theorems 337.

Notes:

Includes bibliographical references (page 348) and index.

ISBN:

0521809754

0521007585

OCLC:

47755792

Online:

Publisher description