Mathematical Logic: A Course with Exercises Part I: Propositional Calculus, Boolean Algebras, Predicate Calculus, Completeness Theorems / Edition 1

ISBN-10: 0198500483

ISBN-13: 9780198500483

Pub. Date: 11/09/2000

Publisher: Oxford University Press, USA

Logic forms the basis of mathematics and is a fundamental part of any mathematics course. This book provides students with a clear and accessible introduction to this important subject, using the concept of model as the main focus and covering a wide area of logic. The chapters of the book cover propositional calculus, boolean algebras, predicate calculus and…  See more details below

Overview

Logic forms the basis of mathematics and is a fundamental part of any mathematics course. This book provides students with a clear and accessible introduction to this important subject, using the concept of model as the main focus and covering a wide area of logic. The chapters of the book cover propositional calculus, boolean algebras, predicate calculus and completelness theorems with answeres to all of the exercises and the end of the volume. This is an ideal introduction to mathematics and logic for the advanced undergraduate student.

Product Details

ISBN-13:
9780198500483
Publisher:
Oxford University Press, USA
Publication date:
11/09/2000
Edition description:
New Edition
Pages:
360
Product dimensions:
9.60(w) x 7.30(h) x 0.70(d)

Related Subjects

 Contents of Part II xiv Notes from the translator xvi Notes to the reader xvii Introduction 1 1 Propositional calculus 7 1.1 Syntax 8 1.1.1 Propositional formulas 8 1.1.2 Proofs by induction on the set of formulas 11 1.1.3 The decomposition tree of a formula 13 1.1.4 The unique decomposition theorem 15 1.1.5 Definitions by induction on the set of formulas 18 1.1.6 Substitutions in a propositional formula 19 1.2 Semantics 21 1.2.1 Assignments of truth values and truth tables 21 1.2.2 Tautologies and logically equivalent formulas 27 1.2.3 Some tautologies 31 1.3 Normal forms and complete sets of connectives 34 1.3.1 Operations on [0, 1] and formulas 34 1.3.2 Normal forms 38 1.3.3 Complete sets of connectives 40 1.4 The interpolation lemma 42 1.4.1 Interpolation lemma 42 1.4.2 The definability theorem 44 1.5 The compactness theorem 45 1.5.1 Satisfaction of a set of formulas 45 1.5.2 The compactness theorem for propositional calculus 48 1.6 Exercises for Chapter 1 53 2 Boolean algebras 63 2.1 Algebra and topology review 64 2.1.1 Algebra 64 2.1.2 Topology 67 2.1.3 An application to propositional calculus 71 2.2 Definition of Boolean algebra 71 2.2.1 Properties of Boolean algebras, order relations 72 2.2.2 Boolean algebras as ordered sets 75 2.3 Atoms in a Boolean algebra 79 2.4 Homomorphisms, isomorphisms, subalgebras 81 2.4.1 Homomorphisms and isomorphisms 81 2.4.2 Boolean subalgebras 86 2.5 Ideals and filters 88 2.5.1 Properties of ideals 88 2.5.2 Maximal ideals 91 2.5.3 Filters 93 2.5.4 Ultrafilters 94 2.5.5 Filterbases 96 2.6 Stone's theorem 97 2.6.1 The Stone space of a Boolean algebra 98 2.6.2 Stone's theorem 102 2.6.3 Boolean spaces are Stone spaces 102 2.7 Exercises for Chapter 2 106 3 Predicate calculus 112 3.1 Syntax 113 3.1.1 First order languages 113 3.1.2 Terms of the language 115 3.1.3 Substitutions in terms 121 3.1.4 Formulas of the language 122 3.1.5 Free variables, bound variables, and closed formulas 125 3.1.6 Substitutions in formulas 127 3.2 Structures 130 3.2.1 Models of a language 131 3.2.2 Substructures and restrictions 133 3.2.3 Homomorphisms and isomorphisms 135 3.3 Satisfaction of formulas in structures 137 3.3.1 Interpretation in a structure of the terms 137 3.3.2 Satisfaction of the formulas in a structure 140 3.4 Universal equivalence and semantic consequence 147 3.5 Prenex forms and Skolem forms 157 3.5.1 Prenex forms 157 3.5.2 Skolem forms 160 3.6 First steps in model theory 165 3.6.1 Satisfaction in a substructure 165 3.6.2 Elementary equivalence 170 3.6.3 The language associated with a structure and formulas with parameters 174 3.6.4 Functions and relations definable in a structure 176 3.7 Models that may not respect equality 179 3.8 Exercises for Chapter 3 182 4 The completeness theorems 193 4.1 Formal proofs (or derivations) 194 4.1.1 Axioms and rules 194 4.1.2 Formal proofs 196 4.1.3 The finiteness theorem and the deduction theorem 200 4.2 Henkin models 202 4.2.1 Henkin witnesses 203 4.2.2 The completeness theorem 205 4.3 Herbrand's method 209 4.3.1 Some examples 209 4.3.2 The avatars of a formula 212 4.4 Proofs using cuts 217 4.4.1 The cut rule 217 4.4.2 Completeness of the method 221 4.5 The method of resolution 224 4.5.1 Unification 224 4.5.2 Proofs by resolution 230 4.6 Exercises for Chapter 4 241 Solutions to the exercises of Part I Chapter 1 245 Chapter 2 270 Chapter 3 293 Chapter 4 320 Bibliography 330 Index 332 5 Recursion theory 5.1 Primitive recursive functions and sets 5.1.1 Some initial definitions 5.1.2 Examples and closure properties 5.1.3 Coding of sequences 5.2 Recursive functions 5.2.1 Ackerman's functions 5.2.2 The [mu]-operator and the partial recursive functions 5.3 Turing machines 5.3.1 Description of Turing machines 5.3.2 T-computable functions 5.3.3 T-computable partial functions are recursive 5.3.4 Universal Turing machines 5.4 Recursively enumerable sets 5.4.1 Recursive and recursively enumerable sets 5.4.2 The halting problem 5.4.3 The smn theorem 5.4.4 The fixed point theorems 5.5 Exercises for Chapter 5 6 Formalization of arithmetic, Godel's theorems 6.1 Peano's axioms 6.1.1 The axioms 6.1.2 The ordering on the integers 6.2 Representable functions 6.3 Arithmetization of syntax 6.3.1 The coding of formulas 6.3.2 The coding of proofs 6.4 Incompleteness and undecidability theorems 6.4.1 Undecidability of arithmetic and predicate calculus 6.4.2 Godel's incompleteness theorems 6.5 Exercises for Chapter 6 7 Set theory 7.1 The theories Z and ZF 7.1.1 The axioms 7.1.2 Pairs, relations and maps 7.2 Ordinal numbers and integers 7.2.1 Well-ordered sets 7.2.2 The ordinals 7.2.3 Operations on ordinal numbers 7.2.4 The integers 7.3 Inductive proofs and definitions 7.3.1 Induction 7.3.2 The axiom of choice 7.4 Cardinality 7.4.1 Cardinal equivalence classes 7.4.2 Operations on cardinal equivalence classes 7.4.3 The finite cardinals 7.4.4 Countable sets 7.4.5 The cardinal numbers 7.5 The axiom of foundation and the reflection scheme 7.5.1 The axiom of foundation 7.5.2 Some relative consistency results 7.5.3 Inaccessible cardinals 7.5.4 The reflection scheme 7.6 Exercises for Chapter 7 8 Some model theory 8.1 Elementary substructures and extensions 8.1.1 Elementary substructures 8.1.2 The Tarski-Vaught test 8.2 Construction of elementary extensions 8.2.1 Elementary maps 8.2.2 The method of diagrams 8.3 The interpolation and definability theorems 8.4 Reduced products and ultraproducts 8.5 Preservation theorems 8.5.1 Preservation by substructures 8.5.2 Preservation by unions of chains 8.5.3 Preservation by reduced products 8.6 Aleph-zero categorical theories 8.6.1 The omitting types theorem 8.6.2 Aleph-zero categorical structures 8.7 Exercises for Chapter 8 Solutions to the exercises of Part II