This thesis takes an algorithmic perspective on the correspondence between modal and hybrid logics on the one hand, and first-order logic on the other. The canonicity of formulae, and by implication the completeness of logics, is simultaneously treated. Modal formulae define second-order condit
Internal Definability and Completeness in Modal Logic [PhD Thesis]
โ Scribed by Marcus Kracht
- Publisher
- Freien Universitat
- Year
- 1990
- Tongue
- English
- Leaves
- 113
- Category
- Library
No coin nor oath required. For personal study only.
โฆ Table of Contents
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
I Internal Definability 19
1 Basic Definitions 21
1.1 The Internal Language of Modal Logic . . . . . . . . . . . . . . . . . . . 21
1.2 Modal Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Frames as Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4 General Framesโboth Algebras and Frames . . . . . . . . . . . . . . . . 24
1.5 The External Language of Modal Logic . . . . . . . . . . . . . . . . . . 25
1.6 Some Classes of General Frames . . . . . . . . . . . . . . . . . . . . . . 27
1.7 Completeness and Persistence . . . . . . . . . . . . . . . . . . . . . . . 29
1.8 Some Small Theorems on Persistence . . . . . . . . . . . . . . . . . . . 30
2 Internal Describability 33
2.1 Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Definabilityโan Example . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3 Internal Describability . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Definability and Completeness . . . . . . . . . . . . . . . . . . . . . . . 37
2.5 Results on Describable Concepts . . . . . . . . . . . . . . . . . . . . . . 38
2.6 Universal Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Some General Results on Internal Definability 43
3.1 General Correspondence . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Preservation, Reflection and Invariance . . . . . . . . . . . . . . . . . . . 44
3.3 Quasi-elementary Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4 Closure Conditions and Syntactic Classes . . . . . . . . . . . . . . . . . 46
3.5 A Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4 Sahlqvistโs Theorem 49
4.1 The Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 Esakiaโs Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Proof of Sahlqvistโs Theorem . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4 A Worked Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.5 Some Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.6 The Converse of Sahlqvistโs Theorem does not Hold . . . . . . . . . . . 55
II Completeness 57
5 Logics from the Drawing-Board 59
5.1 Sketches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 SketchโOmission Logics . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3 Subframe Logics as Sketch-Omission Logics . . . . . . . . . . . . . . . 63
5.4 Splittings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.5 Differentiation Sketches . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6 The Structure of Finitely Generated K4-Frames 67
6.1 Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2 Depth defined . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.3 The Structure of Finitely Generated K4-Frames . . . . . . . . . . . . . . 70
6.4 Blocks and Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.5 Points of Depth One . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.6 Points of Finite Depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.7 Some Consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.8 Quasi-Maximal Points . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.9 Logics of finite width . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7 Logics Containing K4 with and without F.M.P. 85
7.1 Subframe Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.2 Homogenization of Models . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.3 Logics of finite width once again . . . . . . . . . . . . . . . . . . . . . . 89
7.4 Logics of Tightness Two . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.5 Scattered Sketches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.6 More Preservation Properties . . . . . . . . . . . . . . . . . . . . . . . . 97
B Symbols 100
C Index 102
D Logics 105
11 German Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
12 Curriculum Vitae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
๐ SIMILAR VOLUMES
This is a doctoral dissertation of Edith Spaan under the supervision of prof. Johan van Benthem.
This is a doctoral dissertation of Edith Spaan under the supervision of prof. Johan van Benthem.
This thesis was carried out under the supervision of Prof. A. Pnueli. This research deals with decidability, completeness, and extensions of linear time temporal logic. These properties are examined first for a general class of models, that are not restricted to the execution of a specific p
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).
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).