Completeness and definability: Applications of the Ehrenfeucht game in second-order and intensional logic [PhD Thesis]

✍ Scribed by Kees Doets

• Publisher: University of Amsterdam
• Year: 1987
• Tongue: English
• Leaves: 134
• Category: Library

✦ Synopsis

Dissertation completed under supervision of prof. Johan van Benthem. The dissertation contains results on classical first- and second-order logic (parts I and II) and their intensional colleagues: modal- tense- and intuitionistic (propositional) logic (part III).

✦ Table of Contents

Preface ......Page 8
1.0 Introduction ......Page 11
1.1 Notation and terminology ......Page 15
1.2 α-equivalence ......Page 16
1.3 Ordinal-bounded Ehrenfeucht games ......Page 17
1.4 Fraïssé-Karp sequences ......Page 22
1.5 Logic ......Page 23
1.6 Scott sentences ......Page 25
1.7 The finite case ......Page 27
1.8 The unbounded case ......Page 28
1.9 Basis results ......Page 30
2.1 Introduction ......Page 33
2.2 Playing in trees ......Page 34
2.3 Characterizing n-equivalence of Bm ......Page 38
2.4 Finiteness of binary trees is not Σ11 ......Page 42
3.1 Introduction: ω and finite orderings ......Page 46
3.2 Monadic Π11-theory of scattered ordering ......Page 54
3.3 Monadic Π11-theory of complete orderings, of well-orderings and of the reals ......Page 57
3.4 Appendix: strengthening 3.2.4 and 3.3.4 ......Page 65
4. Monadic Π11-theory of well-founded trees ......Page 68
5. Fine structure of modal correspondence theory ......Page 76
6. Game theory for intensional logics, exact universal Kripke models and normal forms ......Page 92
7. Completeness for Z-time ......Page 99
8. Rodenburg’s tree-problem ......Page 104
9. First-order definability of one-variable intuitionistic formulas on finite partial orderings ......Page 108
Appendix A: Can time be directional? ......Page 118
Appendix B: Reduction of higher-order logic ......Page 122
References ......Page 126
Samenvatting ......Page 130