An Introduction To Metalogic

Description

An Introduction to Metalogic is a uniquely accessible introduction to the metatheory of first-order predicate logic. No background knowledge of logic is presupposed, as the book is entirely self-contained and clearly defines all of the technical terms it employs. Yaqub begins with an introduction to predicate logic and ends with detailed outlines of the proofs of the incompleteness, undecidability, and indefinability theorems, covering many related topics in between. Contents......Page 9 Introduction......Page 13 1.1.1 The basic vocabulary of PL......Page 19 1.1.2 PL term......Page 23 1.1.3 PL formulas......Page 25 1.1.4 Bound and free variables and PL sentences......Page 26 1.2.1 PL interpretations......Page 28 1.2.2 Examples of PL interpretations......Page 32 1.2.3 Objectual and substitutional quantification......Page 37 1.2.4 The size of a PL interpretation......Page 39 1.2.5 The truth conditions of PL sentences......Page 40 1.2.6 Possible objections to substitutional quantification and replies......Page 46 1.3.3 Definition of a valid argument......Page 49 1.3.4 Definition of an invalid argument......Page 51 1.3.5 Definition of a valid sentence......Page 52 1.3.6 Definition of a contradictory sentence......Page 53 1.3.7 Definition of a contingent sentence......Page 54 1.3.8 Definition of logically equivalent sentences......Page 55 1.3.9 Definition of a satisfiable set......Page 56 1.3.10 Definition of an unsatisfiable set......Page 57 1.3.11 Decidable and semidecidable concepts......Page 58 1.4.1 The notion of formal derivation......Page 59 1.4.2 The statements of the Soundness and Completeness Theorems for PL......Page 61 1.4.3 Corollaries of the Soundness and Completeness Theorems......Page 63 1.4.4 The structure and application of inference rules......Page 65 1.4.5 The Natural Deduction System (NDS)......Page 70 1.4.6 A justification for the rule Explosion......Page 77 1.4.7 The Gentzen Deduction System (GDS)......Page 79 1.5 Exercises......Page 82 Solutions to the Starred Exercises......Page 87 2.1.1 The metatheory of PL......Page 105 2.1.2 The language of the metatheory......Page 106 2.1.3 Logical resources......Page 107 2.2.1 The structure of the natural numbers......Page 108 2.2.2 The Principle of Mathematical Induction......Page 109 2.3.1 Basic concepts and principles......Page 112 2.3.2 Russell’s Paradox......Page 115 2.3.3 Relations and functions......Page 116 2.3.4 Cardinalities of sets......Page 119 2.3.5 Cantor’s Diagonal Argument......Page 123 2.4.1 Expressive completeness......Page 126 2.4.2 The Mini Deduction System (MDS)......Page 133 2.5 Exercises......Page 142 Solutions to the Starred Exercises......Page 145 3.1 The Soundness Theorem......Page 157 3.2.1 An equivalent formulation of the Completeness Theorem......Page 162 3.2.2 Lindenbaum’s Lemma......Page 166 3.2.3 Henkin sets......Page 170 3.2.4 Henkin interpretations of Henkin sets without the identity predicate......Page 175 3.2.5 Henkin interpretations of Henkin sets with the identity predicate......Page 179 3.3.1 The Compactness Theorem......Page 182 3.3.2 The Finite-Satisfiability Theorem......Page 183 3.4 Elementary Equivalence and Isomorphism......Page 185 3.5.1 PL theories......Page 187 3.5.2 Axiomatizable PL theories......Page 190 3.5.3 Complete and categorical PL sets......Page 193 3.6.1 A proof of the theorem......Page 195 3.6.2 Skolem’s Paradox......Page 196 3.7 Exercises......Page 198 Solutions to the Starred Exercises......Page 200 4.1 Effective Procedures and Computable Functions......Page 207 4.2.1 Turing machines......Page 211 4.2.2 An example......Page 212 4.2.3 Instruction lines and diagrams of Turing machines......Page 213 4.2.4 The zero, successor, and addition functions......Page 215 4.2.5 Turing-computable functions and Church’s Thesis......Page 221 4.2.6 Decidable and semidecidable sets......Page 223 4.3 The Halting Problem......Page 227 4.4 Partial Recursive Functions......Page 231 4.5 Exercises......Page 236 Solutions to the Starred Exercises......Page 237 5.1 Peano Arithmetic......Page 241 5.2 Representability in Peano Arithmetic......Page 246 5.3 Arithmetization of the Metatheory......Page 249 5.4.1 The Diagonalization Lemma......Page 256 5.4.2 Gödel’s First Incompleteness Theorem......Page 259 5.5.1 The undecidability of consistent extensions of Peano Arithmetic......Page 263 5.5.2 Tarski’s Indefinability Theorem......Page 268 5.5.3 Church’s Undecidability Theorem......Page 270 5.6.1 Second-Order Predicate Logic (PL2)......Page 275 5.6.2 Second-Order Peano Arithmetic......Page 278 5.6.3 PL2 and the Compactness Theorem......Page 283 5.6.4 The incompleteness of PL2......Page 286 5.7.1 Hilbert’s Program......Page 290 5.7.2 The Provability Conditions......Page 293 5.8 Exercises......Page 299 Solutions to the Starred Exercises......Page 302 Index......Page 309