Lattices of intermediate and cylindric modal logics [PhD Thesis]

1 Introduction 1
I Lattices of intermediate logics 9
2 Algebraic semantics for intuitionistic logic 11
2.1 Intuitionistic logic and intermediate logics . . . . . . . . . . . . . 11
2.1.1 Syntax and semantics . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 Basic properties of intermediate logics . . . . . . . . . . . 17
2.2 Heyting algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Lattices, distributive lattices and Heyting algebras . . . . . 19
2.2.2 Algebraic completeness of IPC and its extensions . . . . . 23
2.2.3 Heyting algebras and Kripke frames . . . . . . . . . . . . . 26
2.3 Duality for Heyting algebras . . . . . . . . . . . . . . . . . . . . . 28
2.3.1 Descriptive frames . . . . . . . . . . . . . . . . . . . . . . 28
2.3.2 Subdirectly irreducible Heyting algebras . . . . . . . . . . 32
2.3.3 Order-topological duality . . . . . . . . . . . . . . . . . . . 33
2.3.4 Duality of categories . . . . . . . . . . . . . . . . . . . . . 36
2.3.5 Properties of logics and algebras . . . . . . . . . . . . . . . 37
3 Universal models and frame-based formulas 39
3.1 Finitely generated Heyting algebras . . . . . . . . . . . . . . . . . 39
3.2 Free Heyting algebras and n-universal models . . . . . . . . . . . 46
3.2.1 n-universal models . . . . . . . . . . . . . . . . . . . . . . 46
3.2.2 Free Heyting algebras . . . . . . . . . . . . . . . . . . . . . 49
3.3 The Jankov-de Jongh and subframe formulas . . . . . . . . . . . . 56
3.3.1 Formulas characterizing point generated subsets . . . . . . 56
3.3.2 The Jankov-de Jongh theorem . . . . . . . . . . . . . . . . 58
3.3.3 Subframes, subframe and cofinal subframe formulas . . . . 59
3.4 Frame-based formulas . . . . . . . . . . . . . . . . . . . . . . . . . 65
4 The logic of the Rieger-Nishimura ladder 79
4.1 n-conservative extensions, linear and vertical sums . . . . . . . . . 80
4.1.1 The Rieger-Nishimura lattice and ladder . . . . . . . . . . 80
4.1.2 n-conservative extensions and the n-scheme logics . . . . . 83
4.1.3 Sums of Heyting algebras and descriptive frames . . . . . . 85
4.2 Finite frames of RN . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.3 The Kuznetsov-Gerciu logic . . . . . . . . . . . . . . . . . . . . . 93
4.4 The finite model property in extensions of RN . . . . . . . . . . . 98
4.5 The finite model property in extensions of KG . . . . . . . . . . . 105
4.5.1 Extensions of KG without the finite model property . . . 105
4.5.2 The pre-finite model property . . . . . . . . . . . . . . . . 111
4.5.3 The axiomatization of RN . . . . . . . . . . . . . . . . . . 114
4.6 Locally tabular extensions of RN and KG . . . . . . . . . . . . . 117
II Lattices of cylindric modal logics 121
5 Cylindric modal logic and cylindric algebras 123
5.1 Modal Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.1.1 Modal algebras . . . . . . . . . . . . . . . . . . . . . . . . 126
5.1.2 Jonsson-Tarski representation . . . . . . . . . . . . . . . . 127
5.2 Many-dimensional modal logics . . . . . . . . . . . . . . . . . . . 130
5.2.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . 130
5.2.2 Products of modal logics . . . . . . . . . . . . . . . . . . . 131
5.3 Cylindric modal logics . . . . . . . . . . . . . . . . . . . . . . . . 132
5.3.1 S5 x S5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.3.2 Cylindric modal logic with the diagonal . . . . . . . . . . . 135
5.3.3 Product cylindric modal logic . . . . . . . . . . . . . . . . 137
5.3.4 Connection with FOL . . . . . . . . . . . . . . . . . . . . 139
5.4 Cylindric algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.4.1 Df2-algebras . . . . . . . . . . . . . . . . . . . . . . . . . . 140
5.4.2 Topological representation . . . . . . . . . . . . . . . . . . 141
5.4.3 CA2-algebras . . . . . . . . . . . . . . . . . . . . . . . . . 143
5.4.4 Representable cylindric algebras . . . . . . . . . . . . . . . 145
6 Normal extensions of S52 149
6.1 The finite model property of S52 . . . . . . . . . . . . . . . . . . 149
6.2 Locally tabular extensions of S52 . . . . . . . . . . . . . . . . . . 155
6.3 Classification of normal extensions of S52 . . . . . . . . . . . . . . 160
6.4 Tabular and pre tabular extension of S52 . . . . . . . . . . . . . . 161
7 Normal extensions of CML2 167
7.1 Finite CML2-frames . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.1.1 The finite model property . . . . . . . . . . . . . . . . . . 167
7.1.2 The Jankov-Fine formulas . . . . . . . . . . . . . . . . . . 170
7.1.3 The cardinality of Λ(CML2) . . . . . . . . . . . . . . . . . 172
7.2 Locally tabular extensions of CML2 . . . . . . . . . . . . . . . . 173
7.3 Tabular and pre-tabular extensions of CML2 . . . . . . . . . . . 178
8 Axiomatization and computational complexity 187
8.1 Finite axiomatization . . . . . . . . . . . . . . . . . . . . . . . . . 188
8.2 The poly-size model property . . . . . . . . . . . . . . . . . . . . 195
8.3 Logics without the linear-size model property . . . . . . . . . . . 199
8.4 NP-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
Bibliography 209
Index 219