A Course in Mathematical Logic

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