Modal Logic

PART I. Introduction ......Page 16
1.1 Syntax and semantics ......Page 18
1.2 Semantic tableaux ......Page 21
1.3 Classical calculus ......Page 24
1.4 Basic properties of Cl ......Page 30
1.5 Exercises ......Page 34
1.6 Notes ......Page 36
2.1 Motivation ......Page 38
2.2 Kripke frames and models ......Page 40
2.3 Truth-preserving operations ......Page 43
2.4 Hintikka systems ......Page 50
2.5 Intuitionistic frames and formulas ......Page 55
2.6 Intuitionistic calculus ......Page 60
2.7 Embeddings of Cl into Int ......Page 61
2.8 Basic properties of Int ......Page 64
2.9 Realizability logic and Medvedev's logic ......Page 67
2.10 Exercises ......Page 69
2.11 Notes ......Page 71
3.1 Possible world semantics ......Page 76
3.2 Modal frames and models ......Page 79
3.3 Truth-preserving operations ......Page 84
3.4 Hintikka systems ......Page 88
3.5 Modal frames and formulas ......Page 92
3.6 Calculus К ......Page 98
3.7 Basic properties of К ......Page 102
3.8 A few more modal logics ......Page 106
3.9 Embeddings of Int into S4, Grz and GL ......Page 111
3.10 Other types of modal logics ......Page 114
3.11 Exercises ......Page 116
3.12 Notes ......Page 120
4.1 Superintuitionistic logics ......Page 124
4.2 Modal logics ......Page 128
4.3 "The roads we take" ......Page 130
4.4 Exercises and open problems ......Page 138
4.5 Notes ......Page 140
PART II. Kripke semantics ......Page 143
5.1 The Henkin construction ......Page 144
5.2 Completeness theorems ......Page 148
5.3 The filtration method ......Page 152
5.4 Diego's theorem ......Page 159
5.5 Selective filtration ......Page 162
5.6 Kripke semantics for quasi-normal logics ......Page 167
5.7 Exercises ......Page 170
5.8 Notes ......Page 172
6.1 Logics that are not finitely approximable ......Page 174
6.2 Logics that are not canonical and elementary ......Page 178
6.3 Logics that are not compact and complete ......Page 181
6.4 A calculus that is not Kripke complete ......Page 183
6.5 More Kripke incomplete calculi ......Page 187
6.6 Complete logics without countable characteristic frames ......Page 189
6.7 Exercises and open problems ......Page 196
6.8 Notes ......Page 198
PART III. Adequate semantics ......Page 203
7.1 Algebraic preliminaries ......Page 204
7.2 The Tarski-Lindenbaum construction ......Page 206
7.3 Pseudo-Boolean algebras ......Page 208
7.4 Filters in pseudo-Boolean algebras ......Page 217
7.5 Modal algebras and matrices ......Page 225
7.6 Varieties of algebras and matrices ......Page 227
7.7 Operations on algebras and matrices ......Page 230
7.8 Internal characterization of varieties ......Page 238
7.9 Exercises ......Page 240
7.10 Notes ......Page 243
8.1 General frames ......Page 246
8.2 The Stone and Jonsson-Tarski theorems ......Page 252
8.3 From modal to intuitionistic frames and back ......Page 256
8.4 Descriptive frames ......Page 261
8.5 Truth-preserving operations on general frames ......Page 269
8.6 Points of finite depth in refined finitely generated frames ......Page 278
8.7 Universal frames of finite rank ......Page 283
8.8 Exercises and open problems ......Page 290
8.9 Notes ......Page 293
9.1 Subreduction ......Page 297
9.2 Cofinal subreduction and closed domain condition ......Page 305
9.3 Characterizing transitive refutation frames ......Page 313
9.4 Canonical formulas for K4 and Int ......Page 321
9.5 Quasi-normal canonical formulas ......Page 330
9.6 Modal companions of superintuitionistic logics ......Page 333
9.7 Exercises and open problems ......Page 339
9.8 Notes ......Page 343
PART IV. Properties of logics ......Page 345
10.1 The method of canonical models revised ......Page 346
10.2 D-persistence and elementarity ......Page 350
10.3 Sahlqvist's theorem ......Page 356
10.4 Logics of finite width ......Page 363
10.5 The degree of Kripke incompleteness of logics NExtK ......Page 369
10.6 Exercises and open problems ......Page 378
10.7 Notes ......Page 380
11.1 Uniform logics ......Page 383
11.2 Si-logics with essentially negative axioms and modal logics with Box-Diamond-axioms ......Page 387
11.3 Subframe and cofinal subframe logics ......Page 389
11.4 Quasi-normal subframe and cofinal subframe logics ......Page 400
11.5 The method of inserting points ......Page 404
11.6 The method of removing points ......Page 413
11.7 Exercises and open problems ......Page 420
11.8 Notes ......Page 424
12.1 Finite axiomatizability of tabular logics ......Page 426
12.2 Immediate predecessors of tabular logics ......Page 427
12.3 Pretabular logics ......Page 430
12.4 Some remarks on local tabularity ......Page 435
12.5 Exercises and open problems ......Page 437
12.6 Notes ......Page 439
13.1 m-reducibility ......Page 441
13.2 0-reducibility, Post completeness and general Post completeness ......Page 445
13.3 Exercises and open problems ......Page 452
13.4 Notes ......Page 453
14.1 Interpolation theorems for certain modal systems ......Page 455
14.2 Semantic criteria of the interpolation property ......Page 460
14.3 Interpolation in logics above LC and S4.3 ......Page 464
14.4 Interpolation in Extlnt and NExtS4 ......Page 469
14.5 Interpolation in extensions of GL ......Page 472
14.6 Exercises and open problems ......Page 477
14.7 Notes ......Page 478
15.1 Semantic equivalents of the disjunction property ......Page 480
15.2 The disjunction property and the canonical formulas ......Page 483
15.3 Maximal si-logics with the disjunction property ......Page 486
15.4 Hallden completeness ......Page 491
15.5 Exercises and open problems ......Page 494
15.6 Notes ......Page 497
PART V. Algorithmic problems ......Page 498
16.1 Algorithmic preliminaries ......Page 499
16.2 Proving decidability ......Page 503
16.3 Logics containing K4.3 ......Page 507
16.4 Undecidable calculi and formulas above K4 ......Page 512
16.5 Undecidable calculus and formula in Extlnt ......Page 517
16.6 The undecidability of the semantical consequence problem on finite frames ......Page 521
16.7 Admissible and derivable rules ......Page 527
16.8 Exercises and open problems ......Page 538
16.9 Notes ......Page 539
17.1 A trivial solution ......Page 543
17.2 Decidable properties of calculi ......Page 544
17.3 Undecidable properties of modal calculi ......Page 546
17.4 Undecidable properties of si-calculi ......Page 550
17.5 Exercises and open problems ......Page 551
17.6 Notes ......Page 553
18.1 Complexity function. Kuznetsov's construction ......Page 555
18.2 Logics that are not polynomially approximable ......Page 557
18.3 Polynomially approximable logics ......Page 559
18.4 Extremely complex logics of finite width and depth ......Page 561
18.5 Algorithmic problems and complexity classes ......Page 565
18.6 Exercises and open problems ......Page 570
18.7 Notes ......Page 572
Bibliography ......Page 574
Index ......Page 603