This book is actually" An introduction to mathematical logic"
by Micha l Walicki
Contents
The History of Logic 1
A Logic { patterns of reasoning 1
A.1 Reductio ad absurdum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
A.2 Aristotle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
A.3 Other patterns and later developments . . . . . . . . . . . . . . . . . . . . . . . . . 4
B Logic { a language about something 5
B.1 Early semantic observations and problems . . . . . . . . . . . . . . . . . . . . . . . 5
B.2 The Scholastic theory of supposition . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
B.3 Intension vs. extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
B.4 Modalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
C Logic { a symbolic language 7
C.1 The \universally characteristic language" . . . . . . . . . . . . . . . . . . . . . . . . 8
D 19th and 20th Century { mathematization of logic 9
D.1 George Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
D.2 Gottlob Frege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
D.3 Set theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
D.4 20th century logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
E Modern Symbolic Logic 16
E.1 Formal logical systems: syntax. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
E.2 Formal semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
E.3 Computability and Decidability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
F Summary 23
Bibliography 23
Part I. Basic Set Theory 28
1. Sets, Functions, Relations 28
1.1. Sets and Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2. Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.3. Ordering Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.4. Innities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2. Induction 42
2.1. Well-Founded Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.1.1. Inductive Proofs on Well-founded Orderings . . . . . . . . . . . . . . . . . . 43
2.2. Inductive Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2.1. \1-1" Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2.2. Inductive Denitions and Recursive Programming . . . . . . . . . . . . . . . 50
2.2.3. Proofs by Structural Induction . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.3. Transnite Induction [optional] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Part II. Turing Machines 59
3. Turing Machines 59
3.1. Alphabets and Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2. Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.1. Composing Turing machines . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2.2. Alternative representation of TMs [optional] . . . . . . . . . . . . . . . . . . 65
3.3. Universal Turing Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4. Decidability and the Halting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Part III. Statement Logic 73
4. Syntax and Proof Systems 73
4.1. Axiomatic Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2. Syntax of SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.3. The axiomatic system of Hilbert's . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4. Natural Deduction system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.5. Hilbert vs. ND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.6. Provable Equivalence of formulae . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.7. Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.8. The axiomatic system of Gentzen's . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.8.1. Decidability of the axiomatic systems for SL . . . . . . . . . . . . . . . . . . 84
4.8.2. Gentzen's rules for abbreviated connectives . . . . . . . . . . . . . . . . . . . 85
4.9. Some proof techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5. Semantics of SL 88
5.1. Semantics of SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2. Semantic properties of formulae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.4. Sets, Propositions and Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4.1. Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4.2. Sets and SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4.3. Boolean Algebras [optional] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6. Soundness and Completeness 101
6.1. Adequate Sets of Connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.2. DNF, CNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.3. Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.4. Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.4.1. Some Applications of Soundness and Completeness . . . . . . . . . . . . . . 108
Part IV. Predicate Logic 113
7. Syntax and Proof System of FOL 113
7.1. Syntax of FOL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.1.1. Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.2. Scope of Quantiers, Free Variables, Substitution . . . . . . . . . . . . . . . . . . . 116
7.2.1. Some examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.2.2. Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.3. Proof System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.3.1. Deduction Theorem in FOL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.4. Gentzen's system for FOL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8. Semantics 126
8.1. Semantics of FOL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
8.2. Semantic properties of formulae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.3. Open vs. closed formulae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
8.3.1. Deduction Theorem in G and N . . . . . . . . . . . . . . . . . . . . . . . . . 133
9. More Semantics 136
9.1. Prenex operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
9.2. A few bits of Model Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.2.1. Substructures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.2.2. - classication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.3. \Syntactic" semantic and Computations . . . . . . . . . . . . . . . . . . . . . . . . 141
9.3.1. Reachable structures and Term structures . . . . . . . . . . . . . . . . . . . . 141
9.3.2. Herbrand's theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
9.3.3. Horn clauses and logic programming . . . . . . . . . . . . . . . . . . . . . . . 144
10. Soundness, Completeness 151
10.1. Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
10.2. Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
10.2.1. Some Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
11. Identity and Some Consequences 159
11.1. FOL with Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
11.1.1. Axioms for Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
11.1.2. Some examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
11.1.3. Soundness and Completeness of FOL= . . . . . . . . . . . . . . . . . . . . . 162
11.2. A few more bits of Model Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
11.2.1. Compactness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
11.2.2. Skolem-Lowenheim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
11.3. Semi-Decidability and Undecidability of FOL . . . . . . . . . . . . . . . . . . . . . 165
11.4. Why is First-Order Logic \First-Order"? . . . . . . . . . . . . . . . . . . . . . . . 166
12. Summary 170
12.1. Functions, Sets, Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
12.2. Relations, Orderings, Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
12.3. Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
12.4. Formal Systems in general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
12.4.1. Axiomatic System { the syntactic part . . . . . . . . . . . . . . . . . . . . . 172
12.4.2. Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
12.4.3. Syntax vs. Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
12.5. Statement Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
12.6. First Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
12.7. First Order Logic with identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
http://ifile.it/x5b2jlp/book.pdf
