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

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

by Rene Cori, Daniel Lascar, Donald H. Pelletier
     
 

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)

Table of Contents

Contents of Part IIxiv
Notes from the translatorxvi
Notes to the readerxvii
Introduction1
1Propositional calculus7
1.1Syntax8
1.1.1Propositional formulas8
1.1.2Proofs by induction on the set of formulas11
1.1.3The decomposition tree of a formula13
1.1.4The unique decomposition theorem15
1.1.5Definitions by induction on the set of formulas18
1.1.6Substitutions in a propositional formula19
1.2Semantics21
1.2.1Assignments of truth values and truth tables21
1.2.2Tautologies and logically equivalent formulas27
1.2.3Some tautologies31
1.3Normal forms and complete sets of connectives34
1.3.1Operations on [0, 1] and formulas34
1.3.2Normal forms38
1.3.3Complete sets of connectives40
1.4The interpolation lemma42
1.4.1Interpolation lemma42
1.4.2The definability theorem44
1.5The compactness theorem45
1.5.1Satisfaction of a set of formulas45
1.5.2The compactness theorem for propositional calculus48
1.6Exercises for Chapter 153
2Boolean algebras63
2.1Algebra and topology review64
2.1.1Algebra64
2.1.2Topology67
2.1.3An application to propositional calculus71
2.2Definition of Boolean algebra71
2.2.1Properties of Boolean algebras, order relations72
2.2.2Boolean algebras as ordered sets75
2.3Atoms in a Boolean algebra79
2.4Homomorphisms, isomorphisms, subalgebras81
2.4.1Homomorphisms and isomorphisms81
2.4.2Boolean subalgebras86
2.5Ideals and filters88
2.5.1Properties of ideals88
2.5.2Maximal ideals91
2.5.3Filters93
2.5.4Ultrafilters94
2.5.5Filterbases96
2.6Stone's theorem97
2.6.1The Stone space of a Boolean algebra98
2.6.2Stone's theorem102
2.6.3Boolean spaces are Stone spaces102
2.7Exercises for Chapter 2106
3Predicate calculus112
3.1Syntax113
3.1.1First order languages113
3.1.2Terms of the language115
3.1.3Substitutions in terms121
3.1.4Formulas of the language122
3.1.5Free variables, bound variables, and closed formulas125
3.1.6Substitutions in formulas127
3.2Structures130
3.2.1Models of a language131
3.2.2Substructures and restrictions133
3.2.3Homomorphisms and isomorphisms135
3.3Satisfaction of formulas in structures137
3.3.1Interpretation in a structure of the terms137
3.3.2Satisfaction of the formulas in a structure140
3.4Universal equivalence and semantic consequence147
3.5Prenex forms and Skolem forms157
3.5.1Prenex forms157
3.5.2Skolem forms160
3.6First steps in model theory165
3.6.1Satisfaction in a substructure165
3.6.2Elementary equivalence170
3.6.3The language associated with a structure and formulas with parameters174
3.6.4Functions and relations definable in a structure176
3.7Models that may not respect equality179
3.8Exercises for Chapter 3182
4The completeness theorems193
4.1Formal proofs (or derivations)194
4.1.1Axioms and rules194
4.1.2Formal proofs196
4.1.3The finiteness theorem and the deduction theorem200
4.2Henkin models202
4.2.1Henkin witnesses203
4.2.2The completeness theorem205
4.3Herbrand's method209
4.3.1Some examples209
4.3.2The avatars of a formula212
4.4Proofs using cuts217
4.4.1The cut rule217
4.4.2Completeness of the method221
4.5The method of resolution224
4.5.1Unification224
4.5.2Proofs by resolution230
4.6Exercises for Chapter 4241
Solutions to the exercises of Part I
Chapter 1245
Chapter 2270
Chapter 3293
Chapter 4320
Bibliography330
Index332
5Recursion theory
5.1Primitive recursive functions and sets
5.1.1Some initial definitions
5.1.2Examples and closure properties
5.1.3Coding of sequences
5.2Recursive functions
5.2.1Ackerman's functions
5.2.2The [mu]-operator and the partial recursive functions
5.3Turing machines
5.3.1Description of Turing machines
5.3.2T-computable functions
5.3.3T-computable partial functions are recursive
5.3.4Universal Turing machines
5.4Recursively enumerable sets
5.4.1Recursive and recursively enumerable sets
5.4.2The halting problem
5.4.3The smn theorem
5.4.4The fixed point theorems
5.5Exercises for Chapter 5
6Formalization of arithmetic, Godel's theorems
6.1Peano's axioms
6.1.1The axioms
6.1.2The ordering on the integers
6.2Representable functions
6.3Arithmetization of syntax
6.3.1The coding of formulas
6.3.2The coding of proofs
6.4Incompleteness and undecidability theorems
6.4.1Undecidability of arithmetic and predicate calculus
6.4.2Godel's incompleteness theorems
6.5Exercises for Chapter 6
7Set theory
7.1The theories Z and ZF
7.1.1The axioms
7.1.2Pairs, relations and maps
7.2Ordinal numbers and integers
7.2.1Well-ordered sets
7.2.2The ordinals
7.2.3Operations on ordinal numbers
7.2.4The integers
7.3Inductive proofs and definitions
7.3.1Induction
7.3.2The axiom of choice
7.4Cardinality
7.4.1Cardinal equivalence classes
7.4.2Operations on cardinal equivalence classes
7.4.3The finite cardinals
7.4.4Countable sets
7.4.5The cardinal numbers
7.5The axiom of foundation and the reflection scheme
7.5.1The axiom of foundation
7.5.2Some relative consistency results
7.5.3Inaccessible cardinals
7.5.4The reflection scheme
7.6Exercises for Chapter 7
8Some model theory
8.1Elementary substructures and extensions
8.1.1Elementary substructures
8.1.2The Tarski-Vaught test
8.2Construction of elementary extensions
8.2.1Elementary maps
8.2.2The method of diagrams
8.3The interpolation and definability theorems
8.4Reduced products and ultraproducts
8.5Preservation theorems
8.5.1Preservation by substructures
8.5.2Preservation by unions of chains
8.5.3Preservation by reduced products
8.6Aleph-zero categorical theories
8.6.1The omitting types theorem
8.6.2Aleph-zero categorical structures
8.7Exercises for Chapter 8
Solutions to the exercises of Part II

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >