A course in mathematical logic

Title......Page 0001
Copyright......Page 0002
Dedication......Page 0005
Acknowledgements......Page 0007
Contents......Page 0008
Interdependence Scheme for the Chapters......Page 0012
Introduction......Page 0013
Recommended Reading......Page 0017
0 – Prerequisites......Page 0019
1 – Beginning Mathematical Logic......Page 0023
§1.  General considerations......Page 23
§2.  Structures and formal languages......Page 0027
§3.  Higher-order languages......Page 0032
§4.  Basic syntax......Page 0033
§5.  Notational conventions......Page 0036
§6.  Propositional semantics......Page 0038
§7.  Propositional tableaux......Page 0043
§8.  The Elimination Theorem for propositional tableaux......Page 0049
§9.  Completeness of propositional tableaux......Page 0051
§10.  The propositional calculus......Page 0052
§11.  The propositional calculus and tableaux......Page 0058
§12.  Weak completeness of the propositional calculus......Page 0061
§13.  Strong completeness of the propositional calculus......Page 0062
§14.  Propositional logic based on ¬ and ∧......Page 0064
§15.  Propositional logic based on ¬, →, ∧ and ∨......Page 0065
§16.  Historical and bibliographical remarks......Page 0066
2 – First-Order Logic......Page 0067
§1.  First-order semantics......Page 67
§2.  Freedom and bondage......Page 0072
§3.  Substitution......Page 0075
§4.  First-order tableaux......Page 0085
§5.  Some “book-keeping” lemmas......Page 0090
§6.  The Elimination Theorem for first-order tableaux......Page 0097
§7.  Hintikka sets......Page 0101
§8.  Completeness of first-order tableaux......Page 0106
§9.  Prenex and Skolem forms......Page 0111
§10.  Elimination of function symbols......Page 0115
§11.  Elimination of equality......Page 0119
§12.  Relativization......Page 0120
§13.  Virtual terms......Page 0122
§14.  Historical and bibliographical remarks......Page 0125
3 – First-Order Logic (continued)......Page 0126
§1.  The first-order predicate calculus......Page 126
§2.  The first-order predicate calculus and tableaux......Page 0133
§3.  Completeness of the first-order predicate calculus......Page 0135
§4.  First-order logic based on ∃......Page 0140
§5.  What have we achieved?......Page 140
§6.  Historical and bibliographical remarks......Page 0142
4 – Boolean Algebras......Page 0143
§1.  Lattices......Page 143
§2.  Boolean algebras......Page 0147
§3.  Filters and homomorphisms......Page 0151
§4.  The Stone Representation Theorem......Page 0159
§5.  Atoms......Page 0168
§6.  Duality for homomorphisms and continous mappings......Page 171
§7.  The Rasiowa-Sikorski Theorem......Page 0175
§8.  Historical and bibliographical remarks......Page 0177
5 – Model Theory......Page 0179
§1.  Basic ideas of model theory......Page 179
§2.  The Löwenheim-Skolem Theorems......Page 0186
§3.  Ultraproducts......Page 0192
§4.  Completeness and categoricity......Page 0202
§5.  Lindenbaum algebras......Page 0209
§6.  Element types and ℵ₀-categoricity......Page 0221
§7.  Indiscernibles and models with automorphisms......Page 0232
§8.  Historical and bibliographical remarks......Page 0242
6 – Recursion Theory......Page 0244
§1.  Basic notation and terminology......Page 244
§2.  Algorithmic functions and functionals......Page 0248
§3.  The computer URIM......Page 0250
§4.  Computable functionals and functions......Page 0255
§5.  Recursive functionals and functions......Page 0257
§6.  A stockpile of examples......Page 0265
§7.  Church’s Thesis......Page 0275
§8.  Recursiveness of computable functionals......Page 0277
§9.  Functionals with several sequence arguments......Page 0283
§10.  Fundamental theorems......Page 0284
§11.  Recursively enumerable sets......Page 0295
§12.  Diophantine relations......Page 0302
§13.  The Fibonacci sequence......Page 0306
§14.  The power function......Page 314
§15.  Bounded universal quantification......Page 0323
§16.  The MRDP Theorem and Hilbert’s Tenth Problem......Page 0329
§17.  Historical and bibliographical remarks......Page 0332
7 – Logic-Limitative Results......Page 0334
§1.  General notation and terminology......Page 334
§2.  Nonstandard models of Ω......Page 0336
§3.  Arithmecity......Page 0342
§4.  Tarski’s Theorem......Page 0345
§5.  Axiomatic theories......Page 0350
§6.  Baby arithmetic......Page 0352
§7.  Junior arithmetic......Page 0354
§8.  A finitely axiomatized theory......Page 0358
§9.  First-order Peano arithmetic......Page 0360
§10.  Undecidability......Page 0365
§11.  Incompleteness......Page 0371
§12.  Historical and bibliographical remarks......Page 0377
8 – Recursion Theory (continued)......Page 0379
§1.  The arithmetical hierarchy......Page 379
§2.  A result concerning TΩ......Page 0387
§3.  Encoded theories......Page 0388
§4.  Inseparable pairs of sets......Page 0390
§5.  Productive and creative sets; reducibility......Page 0394
§6.  One-one reducibility; recursive isomorphisms......Page 0402
§7.  Turing degrees......Page 0406
§8.  Post’s problem and its solution......Page 0410
§9.  Historical and bibliographical remarks......Page 0416
9 – Intuitionistic First-Order Logic......Page 0418
§1.  Preliminary discussion......Page 418
§2.  Philosophical remark......Page 0421
§3.  Constructive meaning of sentences......Page 421
§4.  Constructive interpretations......Page 0422
§5.  Intuitionistic tableaux......Page 0426
§6.  Kripke’s semantics......Page 0434
§7.  The Elimination Theorem for intuitionistic tableaux......Page 0440
§8.  Intuitionistic propositional calculus......Page 0451
§9.  Intuitionistic predicate calculus......Page 0452
§10.  Completeness......Page 0456
§11.  Translations from classical to intuitionistic logic......Page 0460
§12.  The Interpolation Theorem......Page 0463
§13.  Some results in classical logic......Page 0470
§14.  Historical and bibliographical remarks......Page 0475
10 – Axiomatic Set Theory......Page 0477
§1.  Basic developments......Page 477
§2.  Ordinals......Page 0486
§3.  The Axiom of Regularity......Page 0495
§4.  Cardinality and the Axiom of Choice......Page 0505
§5.  Reflection Principles......Page 0509
§6.  The formalization of satisfaction......Page 0515
§7.  Absoluteness......Page 0520
§8.  Constructible sets......Page 0527
§9.  The consistency of AC and GCH......Page 0534
§10.  Problems......Page 0540
§11.  Historical and bibliographical remarks......Page 0547
11 – Nonstandard Analysis......Page 0549
§1.  Enlargements......Page 0550
§2.  Zermelo structures and their enlargements......Page 0554
§3.  Filters and monads......Page 0561
§4.  Topology......Page 0571
§5.  Topological groups......Page 0579
§6.  The real numbers......Page 0584
§7.  A methodological discussion......Page 0590
§8.  Historical and bibliographical remark......Page 0591
Bibliography......Page 0594
A-B-C......Page 594
D-E-F-G......Page 0595
H......Page 0596
I-J-K-L......Page 0597
M......Page 0598
P-R......Page 0599
S-T......Page 0600
V-W......Page 0601
General Index......Page 0603
A-B......Page 603
C......Page 0604
D-E-F......Page 0605
G-H-I......Page 0606
J-K-L......Page 0607
M-N-O-P......Page 0608
Q-R......Page 0609
S-T......Page 0610
U-V-W-Z......Page 0611
Index of Symbols......Page 0613