Modal Logic

by Chagrov, Alexander; Zakharyaschev, Michael

• ISBN13: 9780198537793
• ISBN10: 0198537794
• Format: Hardcover
• Copyright: 1997-06-19
• Publisher: Clarendon Press

Summary

For a novice this book is a mathematically-oriented introduction to modal logic, the discipline within mathematical logic studying mathematical models of reasoning which involve various kinds of modal operators. It starts with very fundamental concepts and gradually proceeds to the front line of current research, introducing in full details the modern semantic and algebraic apparatus and covering practically all classical results in the field. It contains both numerous exercises and open problems, and presupposes only minimal knowledge in mathematics. A specialist can use the book as a source of references. Results and methods of many directions in propositional modal logic, from completeness and duality to algorithmic problems, are collected and systematically presented in one volume.

Table of Contents

I INTRODUCTION	3	(128)
1 Classical logic	3	(20)
1.1 Syntax and semantics	3	(3)
1.2 Semantic tableaux	6	(3)
1.3 Classical calculus	9	(6)
1.4 Basic properties of CI	15	(4)
1.5 Exercises	19	(2)
1.6 Notes	21	(2)
2 Intuitionistic logic	23	(38)
2.1 Motivation	23	(2)
2.2 Kripke frames and models	25	(3)
2.3 Truth-preserving operations	28	(7)
2.4 Hintikka systems	35	(5)
2.5 Intuitionistic frames and formulas	40	(5)
2.6 Intuitionistic calculus	45	(1)
2.7 Embeddings of CI into Int	46	(3)
2.8 Basic properties of Int	49	(3)
2.9 Realizability logic and Medvedev's logic	52	(2)
2.10 Exercises	54	(2)
2.11 Notes	56	(5)
3 Modal logics	61	(48)
3.1 Possible world semantics	61	(3)
3.2 Modal frames and models	64	(5)
3.3 Truth-preserving operations	69	(4)
3.4 Hintikka systems	73	(4)
3.5 Modal frames and formulas	77	(6)
3.6 Calculus K	83	(4)
3.7 Basic properties of K	87	(4)
3.8 A few more modal logics	91	(5)
3.9 Embeddings of Int into S4, Grz and GL	96	(3)
3.10 Other types of modal logics	99	(2)
3.11 Exercises	101	(4)
3.12 Notes	105	(4)
4 From logics to classes of logics	109	(22)
4.1 Superintuitionistic logics	109	(4)
4.2 Modal logics	113	(2)
4.3 "The roads we take"	115	(8)
4.4 Exercises and open problems	123	(2)
4.5 Notes	125	(6)
II KRIPKE SEMANTICS	131	(62)
5 Canonical models and filtration	131	(30)
5.1 The Henkin construction	131	(4)
5.2 Completeness theorems	135	(4)
5.3 The filtration method	139	(7)
5.4 Diego's theorem	146	(3)
5.5 Selective filtration	149	(5)
5.6 Kripke semantics for quasi-normal logics	154	(3)
5.7 Exercises	157	(2)
5.8 Notes	159	(2)
6 Incompleteness	161	(32)
6.1 Logics that are not finitely approximable	161	(4)
6.2 Logics that are not canonical and elementary	165	(3)
6.3 Logics that are not compact and complete	168	(2)
6.4 A calculus that is not Kripke complete	170	(4)
6.5 More Kripke incomplete calculi	174	(2)
6.6 Complete logics without countable characteristic frames	176	(7)
6.7 Exercises and open problems	183	(2)
6.8 Notes	185	(8)
III ADEQUATE SEMANTICS	193	(144)
7 Algebraic semantics	193	(42)
7.1 Algebraic preliminaries	193	(2)
7.2 The Tarski-Lindenbaum construction	195	(2)
7.3 Pseudo-Boolean algebras	197	(9)
7.4 Filters in pseudo-Boolean algebras	206	(8)
7.5 Modal algebras and matrices	214	(2)
7.6 Variaties of algebras and matrices	216	(3)
7.7 Operations on algebras and matrices	219	(8)
7.8 Internal characterization of varieties	227	(2)
7.9 Exercises	229	(3)
7.10 Notes	232	(3)
8 Relational semantics	235	(51)
8.1 General frames	235	(6)
8.2 The Stone and Jonsson-Tarski theorems	241	(4)
8.3 From modal to intuitionistic frames and back	245	(5)
8.4 Descriptive frames	250	(8)
8.5 Truth-preserving operations on general frames	258	(9)
8.6 Points of finite depth in refined finitely generated frames	267	(5)
8.7 Universal frames of finite rank	272	(7)
8.8 Exercises and open problems	279	(3)
8.9 Notes	282	(4)
9 Canonical formulas	286	(51)
9.1 Subreduction	286	(8)
9.2 Cofinal subreduction and closed domain condition	294	(8)
9.3 Characterizing transitive refutation frames	302	(8)
9.4 Canonical formulas for K4 and Int	310	(9)
9.5 Quasi-normal canonical formulas	319	(3)
9.6 Modal companions of superintuitionistic logics	322	(6)
9.7 Exercises and open problems	328	(4)
9.8 Notes	332	(5)
IV PROPERTIES OF LOGICS	337	(154)
10 Kripke completeness	337	(37)
10.1 The method of canonical models revised	337	(4)
10.2 D-persistence and elementarity	341	(6)
10.3 Sahlqvist's theorem	347	(7)
10.4 Logics of finite width	354	(6)
10.5 The degree of Kripke incompleteness of logics NExtK	360	(9)
10.6 Exercises and open problems	369	(2)
10.7 Notes	371	(3)
11 Finite approximability	374	(43)
11.1 Uniform logics	374	(4)
11.2 Si-logics with essentially negative axioms and modal logics with XXX-axioms	378	(2)
11.3 Subframe and cofinal subframe logics	380	(11)
11.4 Quasi-normal subframe and cofinal subframe logics	391	(4)
11.5 The method of inserting points	395	(9)
11.6 The method of removing points	404	(7)
11.7 Exercises and open problems	411	(4)
11.8 Notes	415	(2)
12 Tabularity	417	(15)
12.1 Finite axiomatizability of tabular logics	417	(1)
12.2 Immediate predecessors of tabular logics	418	(3)
12.3 Pretabular logics	421	(5)
12.4 Some remarks on local tabularity	426	(2)
12.5 Exercises and open problems	428	(2)
12.6 Notes	430	(2)
13 Post completeness	432	(14)
13.1 m-reducibility	432	(4)
13.2 o-reducibility, Post completeness and general Post completeness	436	(7)
13.3 Exercises and open problems	443	(1)
13.4 Notes	444	(2)
14 Interpolation	446	(25)
14.1 Interpolation theorems for certain modal systems	446	(5)
14.2 Semantic criteria of the interpolation property	451	(4)
14.3 Interpolation in logics above LC and S4.3	455	(5)
14.4 Interpolation in ExtInt and NExtS4	460	(3)
14.5 Interpolation in extensions of GL	463	(5)
14.6 Exercises and open problems	468	(1)
14.7 Notes	469	(2)
15 The disjunction property and Hallden completeness	471	(20)
15.1 Semantic equivalents of the disjunction property	471	(3)
15.2 The disjunction property and the canonical formulas	474	(3)
15.3 Maximal si-logics with the disjunction property	477	(5)
15.4 Hallden completeness	482	(3)
15.5 Exercises and open problems	485	(3)
15.6 Notes	488	(3)
V ALGORITHMIC PROBLEMS	491	(76)
16 The decidability of logics	491	(44)
16.1 Algorithmic preliminaries	491	(4)
16.2 Proving decidability	495	(4)
16.3 Logics containing K4.3	499	(5)
16.4 Undecidable calculi and formulas above K4	504	(5)
16.5 Undecidable calculus and formula in ExtInt	509	(4)
16.6 The undecidability of the semantical consequence problem on finite frames	513	(6)
16.7 Admissible and derivable rules	519	(11)
16.8 Exercises and open problems	530	(1)
16.9 Notes	531	(4)
17 The decidability of logics' properties	535	(12)
17.1 A trivial solution	535	(1)
17.2 Decidable properties of calculi	536	(2)
17.3 Undecidable properties of modal calculi	538	(4)
17.4 Undecidable properties of si-calculi	542	(1)
17.5 Exercises and open problems	543	(2)
17.6 Notes	545	(2)
18 Complexity problems	547	(20)
18.1 Complexity function. Kuznetsov's construction	547	(2)
18.2 Logics that are not polynomially approximable	549	(2)
18.3 Polynomially approximable logics	551	(2)
18.4 Extremely complex logics of finite width and depth	553	(4)
18.5 Algorithmic problems and complexity classes	557	(5)
18.6 Exercises and open problems	562	(2)
18.7 Notes	564	(3)
Bibliography	567	(30)
Index