Handbook of Mathematical Logic

Frontmatter......Page 1
Foreword......Page 3
Contributors......Page 4
Contents......Page 5
Introduction......Page 76
Part A. Model Theory......Page 6
1. First-Order Logic - Barwise......Page 8
2. How to tell if you are in the realm of first-order logic......Page 9
3. The formalization of first-order logic......Page 14
4. The completeness theorem......Page 17
5. Beyond first-order logic......Page 26
References......Page 28
2. Fundamentals of Model Theory - Keisler......Page 29
2. Theories......Page 30
3. Diagrams and compactness......Page 34
4. Lowenheim-Skolem theorems......Page 37
5. Recursively saturated models......Page 40
6. Large and small models......Page 42
7. Stable theories......Page 47
8. Model-theoretic forcing......Page 50
9. Infinite formulas and extra quantifiers......Page 53
References......Page 56
3. Ultraproducts for Algebraists - Eklof......Page 58
1. Filters......Page 59
2. Reduced products......Page 60
3. The fundamental theorem......Page 61
4. Ultraproducts as functors......Page 63
5. An ultraproduct version of the compactness theorem......Page 65
6. Embedding theorems......Page 66
7. Bounds in polynomial ideals......Page 68
8. Ultraproducts which are ω_1-saturated......Page 69
9. Ultraproducts of valued fields......Page 72
References......Page 73
4. Model Completeness - MacIntyre......Page 75
1. Basic concepts and Robinson\'s test......Page 77
2. Applications: Nullstellensatz, Hilbert\'s 17th problem, Artin\'s conjecture and integral definite functions......Page 79
3. Model completions, existentially closed structures and forcing......Page 83
4. Applications: Differentially closed fields and prime model extensions......Page 88
5. Negative applications: groups, skew fields and number theories......Page 89
6. Sheaves and model completeness......Page 92
References......Page 93
5. Homogenous Sets - Morley......Page 96
2. Partition theorems and the E.M. theorem......Page 97
3. Skolem functions and elementary submodels......Page 98
4. ω-logic......Page 99
5. Types and Ehrenfeucht-Mostowski models......Page 100
6. Partition theorems for large cardinals and the constructible universe......Page 102
6. Infinitesimal Analysis of Curves and Surfaces - Stroyan......Page 104
1. Robinson\'s formulation of Leibniz\' principle......Page 105
2. Elements of infinitesimal calculus......Page 110
3. Continuous curvature and differentials......Page 114
4. Kissing curves......Page 116
5. Gauss\' investigations of surfaces......Page 118
References......Page 121
7. Admissible Sets and Infinitary Logic - Makkai......Page 122
1. Introduction......Page 123
2. The Kripke-Platek axiom system......Page 124
3. Examples of admissible sets. The truncation lemma......Page 128
4. Hintikka sets, model existence and Σ-compactness......Page 130
5. Conjuctive game formulas......Page 132
6. Applications of game formulas; completeness......Page 137
7. Σ-saturated structures......Page 139
8. The covering theorem......Page 141
9. The perfect subset theorem......Page 144
References......Page 146
8. Doctrines in Categorical Logic - Kock & Reyes......Page 147
1. Algebraic theories......Page 148
2. Cartesian theories......Page 150
3. Elementary doctrines: quantifiers as adjoints......Page 152
4. Logical categories: coherent logic......Page 153
5. Grothendieck topoi: infinitary coherent logic......Page 155
6. Elementary topoi......Page 157
7. Topoi and axiomatic set theory......Page 160
References......Page 161
Part B. Set Theory......Page 163
1. Axioms of Set Theory - Shoenfield......Page 166
2. Sets and set formation......Page 167
3. The axioms......Page 168
4. Development of set theory......Page 169
5. Ordinals......Page 171
6. The axiom of choice......Page 173
7. Classes......Page 175
8. New axioms......Page 176
2. The Axiom of Choice - Jech......Page 178
1. Introduction......Page 179
2. Do we need the axiom of choice?......Page 180
3. The \"paradoxical\" decomposition of a ball......Page 181
4. Some uses of the axiom of choice......Page 183
6. Independence of the axiom of choice......Page 185
7. Transfer theorems......Page 187
8. Mathematics without the axiom of choice......Page 188
10. Determinancy - an alternative to the axiom of choice......Page 190
3. Combinatorics - Kunen......Page 191
2. C.u.b. and stationary sets......Page 192
3. Enumeration principles......Page 193
4. Trees......Page 196
5. Almost disjoint sets......Page 199
6. Partition calculus......Page 201
7. Large cardinals......Page 204
Appendix. Ridiculously large cardinals......Page 205
References......Page 206
4. Forcing - Burgess......Page 207
Introduction......Page 208
1. A closer look at models of set theory......Page 210
2. Forcing......Page 212
3. The Continuum Hypothesis......Page 216
4. Useful combinatorial principles......Page 220
5. Doing two things at once......Page 225
6. Martin\'s Axiom......Page 228
References......Page 231
5. Constructibility - Devlin......Page 232
2. The constructible universe......Page 233
3. Arithmetisation of L_V......Page 234
4. The structure of the constructible hierachy......Page 236
6. The axiom of choice in L......Page 237
7. The condensation lemma. The GCH in L......Page 238
8. Σ_1 Skolem functions......Page 239
9. Admissible ordinals......Page 241
11. The generalised Souslin hypothesis......Page 242
12. The fine structure of the constructible hierachy......Page 244
13. Square_κ......Page 245
14. Weakly compact cardinals in L......Page 247
15. Other results......Page 249
References......Page 250
6. Martin\'s Axiom - Rudin......Page 251
7. Consistency Results in Topology - Juhasz......Page 257
1. Applications of Martin\'s Axiom......Page 258
2. Combinatorial principles valid in L......Page 261
Part C. Recursion Theory......Page 267
1. Elements of Recursion Theory - Enderton......Page 269
1. Informal computability......Page 270
2. Turing machines......Page 271
3. Church\'s thesis......Page 272
4. Universal machines and normal form......Page 273
5. Oracles and functionals......Page 275
6. Recursive enumerability......Page 276
7. Logic and recursion theory......Page 279
8. Degrees of unsolvability......Page 280
9. Creative and lesser sets......Page 282
10. Definability and recursion......Page 283
11. Recursive analogues of classical objects......Page 286
References......Page 288
2. Unsolvable Problems - Davis......Page 289
1. The halting problem revisited......Page 290
2. Semi-Thue processes......Page 291
3. Semigroups and groups......Page 293
4. Other combinatorial problems......Page 296
5. Diophantine equations......Page 298
References......Page 302
3. Decidable Theories - Rabin......Page 303
Survey and basic notions......Page 304
1. The method of elimination of quantifiers......Page 306
2. Model theoretic methods......Page 309
3. The method of interpretations......Page 312
4. Complexity of decision procedures......Page 316
References......Page 319
4. Degrees of Unsolvability: A Survey of Results - Simpson......Page 321
1. Introduction......Page 322
2. Structure of the degrees without jump......Page 323
3. The jump operator......Page 325
4. V=L versus PD......Page 326
5. Between 0 and 0\'......Page 328
6. Degrees of complete theories......Page 329
References......Page 330
5. α-Recursion Theory - Shore......Page 332
1. Ideas and definitions......Page 333
2. Questions and answers......Page 335
3. An example......Page 337
4. Interactions and applications......Page 339
Annotated bibliography......Page 341
6. Recursion in Higher Types......Page 346
2. Suitable classes of functionals......Page 347
3. The basic constructions......Page 349
4. Relations with ordinary recursion theory......Page 351
5. Recursion in type 2 objects and quantifiers......Page 352
6. The Stage Comparison Theorem......Page 354
8. The Enumeration Theorem......Page 356
9. Consequences of enumeration......Page 358
10. The type structure over ω......Page 359
11. Kleene classes of functionals on T*......Page 360
12. Kleene recursion relative to objects of higher type and quantifiers......Page 361
13. Normality and enumeration in higher type recursion......Page 363
14. The original definition of Kleene......Page 364
15. Equivalences of the original Kleene definition with ours......Page 365
16. The Substitution Theorems of Kleene......Page 367
17. Sections and envelopes......Page 370
18. Inductive analysis of semirecursive sets......Page 371
19. Closure under higher existential quantification......Page 372
20. A guide to the literature......Page 373
References......Page 374
7. Inductive Definitions - Aczel......Page 375
1. What are inductive defintions?......Page 376
2. Induction in recursion theory......Page 381
3. Classes of inductive definitions......Page 385
4. Induction in foundations......Page 395
References......Page 396
8. Descriptive Set Theory: Projective Sets - Martin......Page 397
1. Basic concepts of classical descriptive set theory......Page 398
2. Borel and projective sets......Page 399
3. Structural and regularity properties of pointclasses......Page 403
4. Effective descriptive set theory......Page 405
5. The axiom of constructibility and large cardinals......Page 408
6. Projective determinancy......Page 409
References......Page 413
Part D. Proof Theory and Constructive Mathematics......Page 414
1. The Incompleteness Theorem - Smorynski......Page 416
1. Hilbert\'s program......Page 417
2. Godel\'s theorems......Page 418
3. Encoding......Page 420
4. Metamathematical properties other than consistency......Page 428
5. Two applications......Page 434
6. The formalized completeness theorem......Page 436
References......Page 438
2. Proof Theory: Applications of Cut-Elimination - Schwichtenberg......Page 439
1. Introduction......Page 440
2. Cut elimination for first-order logic......Page 441
3. Transfinite induction......Page 444
4. Bounds from proofs of existential theorems......Page 448
5. Transfinite induction and the reflection principle......Page 452
References......Page 453
3. Herbrand\'s Theorem and Gentzen\'s Notion of a Direct Proof - Statman......Page 454
1. Introduction......Page 455
2. Preliminaries......Page 456
3. Direct computations......Page 458
4. Conclusion......Page 461
4. Theories of Finite Type related to Mathematical Practice - Feferman......Page 462
1. Introduction......Page 463
2. Closure conditions on universes and finite-type structures......Page 465
3. Relations of the closure conditions to mathematical practice......Page 468
4. Theories of finite type based on the closure conditions......Page 470
5. Second-order comprehension and choice schemes......Page 474
6. Transfinite induction, recursion and iterated principles......Page 476
7. Recursion-theoretic models of finite type......Page 480
8. Second-order content of the theories; proof-theoretical models......Page 484
References......Page 490
5. Constructive Mathematics - Troelstra......Page 492
1. Introduction......Page 493
2. Logic......Page 494
3. Languages, formal systems, notations, the Godel negative translation......Page 497
4. Realizability and Church\'s thesis......Page 499
5. Some elementary mathematics......Page 502
6. Continuity; choice sequences......Page 508
7. Lawless sequences......Page 515
8. Markov\'s principle......Page 516
9. Truth-value semantics for intuitionistic logic; validity in all structures......Page 518
10. Finite type structures......Page 519
11. The Dialectica interpretation......Page 522
12. \"Local\" and \"global\"......Page 526
References......Page 529
6. The Logic of Topoi - Fourman......Page 532
2. Category-theoretic preliminaries......Page 533
3. The logic of partial elements......Page 535
4. Categories from logic......Page 538
5. Topoi......Page 540
6. Logical constructs in topoi......Page 541
7. Interpretations in topoi......Page 544
8. Topoi as theories......Page 547
References......Page 550
7. Type Free Lambda Calculus - Barendregt......Page 551
0. Introduction......Page 552
1. Towards the theory......Page 553
2. Classical λ-calculus......Page 556
3. Construction of the graph model P_ω......Page 559
4. Construction of D_ω......Page 561
5. Solvability......Page 564
6. Bohm trees......Page 565
7. Analysis of D_ω......Page 568
References......Page 571
8. A Mathematical Incompleteness in PA - Paris & Harrington......Page 572
2. Proofs......Page 573
3. Refinements......Page 576
Index of Names......Page 577
Subject Index......Page 581