Coverart for item
The Resource Computability and logic, George S. Boolos, John P. Burgess, Richard C. Jeffrey

Computability and logic, George S. Boolos, John P. Burgess, Richard C. Jeffrey

Label
Computability and logic
Title
Computability and logic
Statement of responsibility
George S. Boolos, John P. Burgess, Richard C. Jeffrey
Creator
Contributor
Subject
Language
eng
Cataloging source
VVC
http://library.link/vocab/creatorName
Boolos, George
Illustrations
illustrations
Index
index present
Literary form
non fiction
Nature of contents
bibliography
http://library.link/vocab/relatedWorkOrContributorDate
1948-
http://library.link/vocab/relatedWorkOrContributorName
  • Burgess, John P.
  • JEFFREY, Richard Carl
http://library.link/vocab/subjectName
  • Computable functions
  • Recursive functions
  • Logic, Symbolic and mathematical
Label
Computability and logic, George S. Boolos, John P. Burgess, Richard C. Jeffrey
Instantiates
Publication
Note
  • Reprint, with corrections, of edition originally published 2002
  • Includes index
  • Contents list contains erroneous reference to an annotated bibliography
Contents
  • Preface
  • Computability Theory
  • 1.
  • Enumerability.
  • p. 3
  • 1.1.
  • Enumerability.
  • p. 3
  • 1.2.
  • Enumerable Sets.
  • p. 7
  • 2.
  • Diagonalization.
  • p. 16
  • 3.
  • Turing Computability.
  • p. 23
  • 4.
  • Uncomputability.
  • p. 35
  • 4.1.
  • Halting Problem.
  • p. 35
  • 4.2.
  • Productivity Function.
  • p. 40
  • 5.
  • Abacus Computability.
  • p. 45
  • 5.1.
  • Abacus Machines.
  • p. 45
  • 5.2.
  • Simulating Abacus Machines by Turing Machines.
  • p. 51
  • 5.3.
  • Scope of Abacus Computability.
  • p. 57
  • 6.
  • Recursive Functions.
  • p. 63
  • 6.1.
  • Primitive Recursive Functions.
  • p. 63
  • 6.2.
  • Minimization.
  • p. 70
  • 7.
  • Recursive Sets and Relations.
  • p. 73
  • 7.1.
  • Recursive Relations.
  • p. 73
  • 7.2.
  • Semirecursive Relations.
  • p. 80
  • 7.3.
  • Further Examples.
  • p. 83
  • 8.
  • Equivalent Definitions of Computability.
  • p. 88
  • 8.1.
  • Coding Turing Computations.
  • p. 88
  • 8.2.
  • Universal Turing Machines.
  • p. 94
  • 8.3.
  • Recursively Enumerable Sets.
  • p. 96
  • Basic Metalogic
  • 9.
  • Precis of First-Order Logic: Syntax.
  • p. 101
  • 9.1.
  • First-Order Logic.
  • p. 101
  • 9.2.
  • Syntax.
  • p. 106
  • 10.
  • Precis of First-Order Logic: Semantics.
  • p. 114
  • 10.1.
  • Semantics.
  • p. 114
  • 10.2.
  • Metalogical Notions.
  • p. 119
  • 11.
  • Undecidability of First-Order Logic.
  • p. 126
  • 11.1.
  • Logic and Turing Machines.
  • p. 126
  • 11.2.
  • Logic and Primitive Recursive Functions.
  • p. 132
  • 12.
  • Models.
  • p. 137
  • 12.1.
  • Size and Number of Models.
  • p. 137
  • 12.2.
  • Equivalence Relations.
  • p. 142
  • 12.3.
  • Lowenheim-Skolem and Compactness Theorems.
  • p. 146
  • 13.
  • Existence of Models.
  • p. 153
  • 13.1.
  • Outline of the Proof.
  • p. 153
  • 13.2.
  • First Stage of the Proof.
  • p. 156
  • 13.3.
  • Second Stage of the Proof.
  • p. 157
  • 13.4.
  • Third Stage of the Proof.
  • p. 160
  • 13.5.
  • Nonenumerable Languages.
  • p. 162
  • 14.
  • Proofs and Completeness.
  • p. 166
  • 14.1.
  • Sequent Calculus.
  • p. 166
  • 14.2.
  • Soundness and Completeness.
  • p. 174
  • 14.3.
  • Other Proof Procedures and Hilbert's Thesis.
  • p. 179
  • 15.
  • Arithmetization.
  • p. 187
  • 15.1.
  • Arithmetization of Syntax.
  • p. 187
  • 15.2.
  • Godel Numbers.
  • p. 192
  • 15.3.
  • More Godel Numbers.
  • p. 196
  • 16.
  • Representability of Recursive Functions.
  • p. 199
  • 16.1.
  • Arithmetical Definability.
  • p. 199
  • 16.2.
  • Minimal Arithmetic and Representability.
  • p. 207
  • 16.3.
  • Mathematical Induction.
  • p. 212
  • 16.4.
  • Robinson Arithmetic.
  • p. 215
  • 17.
  • Indefinability, Undecidability, Incompleteness.
  • p. 221
  • 17.1.
  • Diagonal Lemma and the Limitative Theorems.
  • p. 221
  • 17.2.
  • Undecidable Sentences.
  • p. 225
  • 17.3.
  • Undecidable Sentences without the Diagonal Lemma.
  • p. 227
  • 18.
  • Unprovability of Consistency.
  • p. 233
  • Further Topics
  • 19.
  • Normal Forms.
  • p. 243
  • 19.1.
  • Disjunctive and Prenex Normal Forms.
  • p. 243
  • 19.2.
  • Skolem Normal Form.
  • p. 247
  • 19.3.
  • Herbrand's Theorem.
  • p. 253
  • 19.4.
  • Eliminating Function Symbols and Identity.
  • p. 255
  • 20.
  • Craig Interpolation Theorem.
  • p. 260
  • 20.1.
  • Craig's Theorem and Its Proof.
  • p. 260
  • 20.2.
  • Robinson's Joint Consistency Theorem.
  • p. 264
  • 20.3.
  • Beth's Definability Theorem.
  • p. 265
  • 21.
  • Monadic and Dyadic Logic.
  • p. 270
  • 21.1.
  • Solvable and Unsolvable Decision Problems.
  • p. 270
  • 21.2.
  • Monadic Logic.
  • p. 273
  • 21.3.
  • Dyadic Logic.
  • p. 275
  • 22.
  • Second-Order Logic.
  • p. 279
  • 23.
  • Arithmetical Definability.
  • p. 286
  • 23.1.
  • Arithmetical Definability and Truth.
  • p. 286
  • 23.2.
  • Arithmetical Definability and Forcing.
  • p. 289
  • 24.
  • Decidability of Arithmetic without Multiplication.
  • p. 295
  • 25.
  • Nonstandard Models.
  • p. 302
  • 25.1.
  • Order in Nonstandard Models.
  • p. 302
  • 25.2.
  • Operations in Nonstandard Models.
  • p. 306
  • 25.3.
  • Nonstandard Models of Analysis.
  • p. 312
  • 26.
  • Ramsey's Theorem.
  • p. 319
  • 26.1.
  • Ramsey's Theorem: Finitary and Infinitary.
  • p. 319
  • 26.2.
  • Konig's Lemma.
  • p. 322
  • 27.
  • Modal Logic and Provability.
  • p. 327
  • 27.1.
  • Modal Logic.
  • p. 327
  • 27.2.
  • Logic of Provability.
  • p. 334
  • 27.3.
  • Fixed Point and Normal Form Theorems.
  • p. 337
  • Hints for Selected Problems.
  • p. 341
  • Annotated Bibliography.
  • p. 348
  • Index.
  • p. 349
Control code
ocm54992001
Dimensions
27 cm.
Edition
4th ed. reprinted with corrections
Extent
xi, 356 p.
Isbn
9780521007580
Lccn
2001043302
Other physical details
ill.
Label
Computability and logic, George S. Boolos, John P. Burgess, Richard C. Jeffrey
Publication
Note
  • Reprint, with corrections, of edition originally published 2002
  • Includes index
  • Contents list contains erroneous reference to an annotated bibliography
Contents
  • Preface
  • Computability Theory
  • 1.
  • Enumerability.
  • p. 3
  • 1.1.
  • Enumerability.
  • p. 3
  • 1.2.
  • Enumerable Sets.
  • p. 7
  • 2.
  • Diagonalization.
  • p. 16
  • 3.
  • Turing Computability.
  • p. 23
  • 4.
  • Uncomputability.
  • p. 35
  • 4.1.
  • Halting Problem.
  • p. 35
  • 4.2.
  • Productivity Function.
  • p. 40
  • 5.
  • Abacus Computability.
  • p. 45
  • 5.1.
  • Abacus Machines.
  • p. 45
  • 5.2.
  • Simulating Abacus Machines by Turing Machines.
  • p. 51
  • 5.3.
  • Scope of Abacus Computability.
  • p. 57
  • 6.
  • Recursive Functions.
  • p. 63
  • 6.1.
  • Primitive Recursive Functions.
  • p. 63
  • 6.2.
  • Minimization.
  • p. 70
  • 7.
  • Recursive Sets and Relations.
  • p. 73
  • 7.1.
  • Recursive Relations.
  • p. 73
  • 7.2.
  • Semirecursive Relations.
  • p. 80
  • 7.3.
  • Further Examples.
  • p. 83
  • 8.
  • Equivalent Definitions of Computability.
  • p. 88
  • 8.1.
  • Coding Turing Computations.
  • p. 88
  • 8.2.
  • Universal Turing Machines.
  • p. 94
  • 8.3.
  • Recursively Enumerable Sets.
  • p. 96
  • Basic Metalogic
  • 9.
  • Precis of First-Order Logic: Syntax.
  • p. 101
  • 9.1.
  • First-Order Logic.
  • p. 101
  • 9.2.
  • Syntax.
  • p. 106
  • 10.
  • Precis of First-Order Logic: Semantics.
  • p. 114
  • 10.1.
  • Semantics.
  • p. 114
  • 10.2.
  • Metalogical Notions.
  • p. 119
  • 11.
  • Undecidability of First-Order Logic.
  • p. 126
  • 11.1.
  • Logic and Turing Machines.
  • p. 126
  • 11.2.
  • Logic and Primitive Recursive Functions.
  • p. 132
  • 12.
  • Models.
  • p. 137
  • 12.1.
  • Size and Number of Models.
  • p. 137
  • 12.2.
  • Equivalence Relations.
  • p. 142
  • 12.3.
  • Lowenheim-Skolem and Compactness Theorems.
  • p. 146
  • 13.
  • Existence of Models.
  • p. 153
  • 13.1.
  • Outline of the Proof.
  • p. 153
  • 13.2.
  • First Stage of the Proof.
  • p. 156
  • 13.3.
  • Second Stage of the Proof.
  • p. 157
  • 13.4.
  • Third Stage of the Proof.
  • p. 160
  • 13.5.
  • Nonenumerable Languages.
  • p. 162
  • 14.
  • Proofs and Completeness.
  • p. 166
  • 14.1.
  • Sequent Calculus.
  • p. 166
  • 14.2.
  • Soundness and Completeness.
  • p. 174
  • 14.3.
  • Other Proof Procedures and Hilbert's Thesis.
  • p. 179
  • 15.
  • Arithmetization.
  • p. 187
  • 15.1.
  • Arithmetization of Syntax.
  • p. 187
  • 15.2.
  • Godel Numbers.
  • p. 192
  • 15.3.
  • More Godel Numbers.
  • p. 196
  • 16.
  • Representability of Recursive Functions.
  • p. 199
  • 16.1.
  • Arithmetical Definability.
  • p. 199
  • 16.2.
  • Minimal Arithmetic and Representability.
  • p. 207
  • 16.3.
  • Mathematical Induction.
  • p. 212
  • 16.4.
  • Robinson Arithmetic.
  • p. 215
  • 17.
  • Indefinability, Undecidability, Incompleteness.
  • p. 221
  • 17.1.
  • Diagonal Lemma and the Limitative Theorems.
  • p. 221
  • 17.2.
  • Undecidable Sentences.
  • p. 225
  • 17.3.
  • Undecidable Sentences without the Diagonal Lemma.
  • p. 227
  • 18.
  • Unprovability of Consistency.
  • p. 233
  • Further Topics
  • 19.
  • Normal Forms.
  • p. 243
  • 19.1.
  • Disjunctive and Prenex Normal Forms.
  • p. 243
  • 19.2.
  • Skolem Normal Form.
  • p. 247
  • 19.3.
  • Herbrand's Theorem.
  • p. 253
  • 19.4.
  • Eliminating Function Symbols and Identity.
  • p. 255
  • 20.
  • Craig Interpolation Theorem.
  • p. 260
  • 20.1.
  • Craig's Theorem and Its Proof.
  • p. 260
  • 20.2.
  • Robinson's Joint Consistency Theorem.
  • p. 264
  • 20.3.
  • Beth's Definability Theorem.
  • p. 265
  • 21.
  • Monadic and Dyadic Logic.
  • p. 270
  • 21.1.
  • Solvable and Unsolvable Decision Problems.
  • p. 270
  • 21.2.
  • Monadic Logic.
  • p. 273
  • 21.3.
  • Dyadic Logic.
  • p. 275
  • 22.
  • Second-Order Logic.
  • p. 279
  • 23.
  • Arithmetical Definability.
  • p. 286
  • 23.1.
  • Arithmetical Definability and Truth.
  • p. 286
  • 23.2.
  • Arithmetical Definability and Forcing.
  • p. 289
  • 24.
  • Decidability of Arithmetic without Multiplication.
  • p. 295
  • 25.
  • Nonstandard Models.
  • p. 302
  • 25.1.
  • Order in Nonstandard Models.
  • p. 302
  • 25.2.
  • Operations in Nonstandard Models.
  • p. 306
  • 25.3.
  • Nonstandard Models of Analysis.
  • p. 312
  • 26.
  • Ramsey's Theorem.
  • p. 319
  • 26.1.
  • Ramsey's Theorem: Finitary and Infinitary.
  • p. 319
  • 26.2.
  • Konig's Lemma.
  • p. 322
  • 27.
  • Modal Logic and Provability.
  • p. 327
  • 27.1.
  • Modal Logic.
  • p. 327
  • 27.2.
  • Logic of Provability.
  • p. 334
  • 27.3.
  • Fixed Point and Normal Form Theorems.
  • p. 337
  • Hints for Selected Problems.
  • p. 341
  • Annotated Bibliography.
  • p. 348
  • Index.
  • p. 349
Control code
ocm54992001
Dimensions
27 cm.
Edition
4th ed. reprinted with corrections
Extent
xi, 356 p.
Isbn
9780521007580
Lccn
2001043302
Other physical details
ill.

Library Locations

    • Sydney Jones LibraryBorrow it
      Chatham Street, Liverpool, L7 7BD, GB
      53.403069 -2.963723
Processing Feedback ...