Introduction To Mathematical Logic

✍ Scribed by Michal Walicki

• Publisher: World Scientific
• Year: 2011
• Tongue: English
• Leaves: 302
• Edition: 1
• Category: Library

✦ Synopsis

This is a systematic and well-paced introduction to mathematical logic. Excellent as a course text, the book presupposes only elementary background and can be used also for self-study by more ambitious students. Starting with the basics of set theory, induction and computability, it covers propositional and first-order logic - their syntax, reasoning systems and semantics. Soundness and completeness results for Hilbert's and Gentzen's systems are presented, along with simple decidability arguments. The general applicability of various concepts and techniques is demonstrated by highlighting their consistent reuse in different contexts. Unlike in most comparable texts, presentation of syntactic reasoning systems precedes the semantic explanations. The simplicity of syntactic constructions and rules - of a high, though often neglected, pedagogical value - aids students in approaching more complex semantic issues. This order of presentation also brings forth the relative independence of syntax from the semantics, helping to appreciate the importance of the purely symbolic systems, like those underlying computers. An overview of the history of logic precedes the main text, while informal analogies precede introduction of most central concepts. These informal aspects are kept clearly apart from the technical ones. Together, they form a unique text which may be appreciated equally by lecturers and students occupied with mathematical precision, as well as those interested in the relations of logical formalisms to the problems of computability and the philosophy of logic.

✦ Table of Contents

Cover Page
Title Page
Copyright Page
Dedication Page
Acknowledgements
Table of Contents
A HISTORY OF LOGIC
A. Patterns of reasoning
A.1 Reductio ad absurdum
A.2 Aristotle
A.3 Other patterns and later developments
B.A LANGUAGE AND ITS MEANING
B.1 Early semantic observations and problems
B.2 The Scholastic theory of supposition
B.3 Intension vs. extension
B.4 Modalities
C.A SYMBOLIC LANGUAGE
C.1 The “universally characteristic language”
C.2 Calculus of reason
D.1850-1950 - MATHEMATICAL LOGIC
D.1 George Boole
D.2 Gottlob Frege
D.3 Set theory
D.4 20th century logic
E. Modern symbolic logic
E.1 Formal logical systems: Syntax
E.2 Formal semantics
E.3 Computability and decidability
F.Summary
Part I Elements of Set Theory
1. Sets, functions, relations
1.1 Sets and functions
1.2 Relations
1.3 Ordering relations
1.4 Infinities
Exercises I
2. Induction
2.1 Well-founded relations
2.1.1 Inductive proofs
2.2 Inductive definitions
2.2.1 “1-1” Definitions
2.2.2 Recursive programming [optional]
2.2.3 P roofs by structural induction
2.3 Transfinite induction [optional]
Exercises 2
Part II Turing Machines
3. Computability and decidability
3.1 Alphabets and languages
3.2 Turing machines
3.2.1 Composing Turing machines [optional]
3.3 Universal Turing machine
3.4 Undecidability
Exercises 3
Part III Propositional Logic
4. Syntax and proof systems
4.1 Axiomatic systems
4.2 P ropositional syntax
4.3 Hilbert’s axiomatic system I - L
4.4 The axiomatic system A f
4.5 Provable equivalence
4.6 Consistency
4.7 H versus M
4.8 Gentzen’s axiomatic system Q
4.8.1 Decidability of P L
4.8.2 Rules for abbreviated connectives
4.9 Some proof techniques
Exercises 4
5. Semantics of PL
5.1 The Boolean semantics
5.1.1 Syntactic abbreviations
5.2 Semantic properties
5.2.1 Some propositional laws
5.3 Set-based semantics
5.3.1 Sets and propositions
5.3.2 Boolean algebras [optional]
Exercises 5
6. Soundness and completeness
6.1 Expressive completeness
6.2 Disjunctive and conjunctive normal forms
6.2.1 CNF, clauses and SAT [optional]
6.3 Soundness
6.4 Completeness
6.5 Some applications
Exercises 6
7. Diagnosing paradoxes
7.1 Semantic paradoxes
7.2 Finitary paradoxes are circular
7.3 Acyclic paradoxes and infinitary logic
7.4 GNF and SAT
Exercises 7
Part IV First Order Logic
8. Syntax and proof systems of FOL
8.1 Syntax of F O L
8.2 Scope of quantifiers
8.2.1 Some examples
8.2.2 Substitution
8.3 The axiomatic system A f
8.3.1 Deduction Theorem in FOL
8.4 Gentzen’s system for FOL
Exercises 8
9. Semantics of FOL
9.1 The basic definitions
9.2 Semantic properties
9.3 Open vs. closed formulae
9.3.1 Deduction T heorem in Q and A f
Exercises 9
10. More semantics
10.1 P renex normal form
10.1.1 PNF HIERARCHY
10.2 Substructures: An example from model theory
10.3 “Syntactic” semantics
10.3.1 Reachable and term structures
10.3.2 Herbrand’s theorem
10.3.3 Horn clauses
10.3.4 Herbrand models of Horn theories
10.3.5 Computing with Horn clauses
10.3.6 Computational completeness
Exercises 1 0
11. Soundness and completeness
11.1 Soundness of A f
11.2 Completeness of A f
11.2.1 Completeness of Gentzen’s system [optional]
11.3 Some applications
Exercises 1 1
Why is first order logic “first order”?
Index
Index of symbols
The Greek alphabet