A Problem Course in Mathematical Logic

Title Page......Page 1
Contents......Page 3
Preface......Page 5
Introduction......Page 9
Part I: Propositional Logic......Page 13
1 Language......Page 15
2 Truth Assignments......Page 19
3 Deductions......Page 23
4 Soundness and Completeness......Page 27
Hints for Chapters 1–4......Page 29
Part II: First-Order Logic......Page 33
5 Languages......Page 35
6 Structures and Models......Page 45
7 Deductions......Page 53
8 Soundness and Completeness......Page 59
9 Applications of Compactness......Page 65
Hints for Chapters 5–9......Page 71
Part III: Computability......Page 77
10 Turing Machines......Page 79
11 Variations and Simulations......Page 87
12 Computable and Non-Computable Functions......Page 93
13 Recursive Functions......Page 99
14 Characterizing Computability......Page 107
Hints for Chapters 10–14......Page 113
Part IV: Incompleteness......Page 121
15 Preliminaries......Page 123
16 Coding First-Order Logic......Page 125
17 Defining Recursive Functions In Arithmetic......Page 129
18 The Incompleteness Theorem......Page 135
Hints for Chapters 15–18......Page 139
Appendices......Page 143
A A Little Set Theory......Page 145
B The Greek Alphabet......Page 147
C Logic Limericks......Page 149
D GNU Free Documentation License......Page 151
Bibliography......Page 159
Index......Page 161