Introduction to Modal Logic

Autumn 2015

Institute for Logic, Language and Computation

Universiteit van Amsterdam




Last years' final exam.


Practicalities

  • Instructor: Nick Bezhanishvili , email: N.Bezhanishvili[at]uva.nl

  • Teaching assistants: Paula Henk , email: paulahenk[at]gmail.com ; Julia Ilin , email: ilin.juli[at]gmail.com

  • Time and Place: Tuesday 15-17h (SP 904, F1.02) and Thursday 13-15 (SP 904, C1.112)

  • EC: 6

  • Assessment : There will be 7 Homework sheets. There will be a midterm exam and also a final exam on December 17. The final grade consists 50% of the homework grade, 10% of the grade of the midterm exam and 40% of the grade of the final exam. The homework grade is split into 7 homework sheets weighing 100 points each.

  • Midter exam: The midterm exam will be on Wednesday, 21 October, 16-18 in SP H0.08.


  • Final exam: The final exam will be on Thursday, 17 December, 9-12 in SP 904, C1.03.

Information about the course

  • Objectives:
  • The students should be able to point out when a modal formula is satisfied/valid on a given Kripke model/frame.
  • They should also be able to compute standard translations of modal formulas and first-order correspondents of Sahlqvist formulas.
  • They are expected to produce a completeness proof via the canonical model construction for some basic systems of modal logic.
  • They should also be able to derive finite model property of such systems via the method of filtration.
  • Students should be able to argue about decidability of simple systems of modal logic by combining finite axiomatization and the finite model property of these systems.
  • Students are also expected to solve basic problems involving more complex modal systems such as PDL.

  • Contents: The course covers the basic notions of modal logic:
  • syntax, relational semantics,
  • models and frames,
  • filtrations,
  • bisimulations, van Benthem's bisimulation characterisation theorem,
  • first-order correspondence, Sahlqvist algorithm,
  • model-theoretic and frame-theoretic constructions,
  • soundness and completeness, the finite model property,
  • propositional dynamic logic PDL.

  • Recommended prior knowledge: Knowledge of first order logic (syntax and semantics) and elementary mathematical knowledge and skills.

  • Format: Weekly lectures and tutorial sessions.

  • Study materials: Modal Logic, Blackburn, de Rijke, Venema, Cambridge University Press, 2001.

    • Additional literature

  • Alexander Chagrov and Michael Zakharyaschev: Modal Logic, Oxford University Press, 1997.
  • Johan van Benthem : Modal Logic for Open Minds, 2010.
  • Marcus Kracht: Tools and Techniques in Modal Logic, Elsevier, 1999.
  • Dov M. Gabbay, A. Kurucz, F. Wolter, M. Zakharyaschev: Many-Dimensional Modal Logics: Theory and Applications, Elsevier, 2003.

    • Homeworksheets

  • Homework 1, due: 15 September before class.

  • Homework 2 , due: 29 September before class.

  • Homework 3 , due: 13 October before class.

  • Homework 4 , due: 27 October before class.

  • Homework 5, due: 10 November before class.

  • Homework 6, due: 24 November before class.

  • Homework 7, due: 1 December before class.

    • Lectures

    1 Sep 2015
    Tuesday    		 Hoorcollege
    15-17
    SP 904 F1.02    		 Relational structures, Modal languages, Models and Frames; Sections 1.1 - 1.3.
    3 Sep 2015
    Thursday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Bisimulations, generated submodels; Sections 2.1 - 2.2 (until Theorem 2.24).
    8 Sep 2015
    Tuesday    		 Wekcollege
    15-17
    		 Cancelled! Due to Workshop on Correspondence and Canonicity in Non-Classical Logic
    10 Sep 2015
    Thursday    		 Wekcollege
    13-15
    SP C1.112    		 Exercises on validity and bisimulations .
    15 Sep 2015
    Tuesday    		 Hoorcollege
    15-17
    SP 904 F1.02    		 Hennessy-Milner Theorem, Filtrations (Section 2.2, Section 2.3 from Definition 2.35 to Thm 2.39).
    17 Sep 2015
    Thursday    		 Wekcollege
    13-15
    SP 904 C1.112, G3.05    		 Exercises on bisimulations and filtration.
    22 Sep 2015
    Tuesday    		 Hoorcollege
    15-17
    SP 904 F1.02    		 Least and greatest filtrations, standard translation.
    24 Sep 2015
    Thursday    		 Wekcollege
    13-15
    SP 904 C1.112    		 Exercises on filtration and standard translation.
    29 Sep 2014
    Tuesday    		 Hoorcollege
    15-17
    SP 904 F1.02    		 van Benthem's bisimulation characterisation theorem (without proof), frame definability and frame correspondence, frame definability via Second-Order logic, undefinable properties via bounded morphisms, generated subframes and disjoint unions (Section 2.6, Def 2.67, Thm 2.68, Sections 3.1 - 3.2 until Example 3.10, Section 3.3 until Cor 3.16).
    1 Oct 2015
    Thursday    		 Wekcollege
    13-15
    SP 904 C1.112, G2.02    		 Exercises on definability and undefinability.
    6 Oct 2015
    Tuesday    		 Hoorcollege
    15-17
    SP 904 F1.02l    		 Frame correspondence: local and global correspondents, closed formulas, uniform formulas (Prop. 3.12, Section 3.5).
    8 Oct 2015
    Thursday    		 Wekcollege
    13-15
    SP 904 C1.112    		 Exercises on positive (negative) formulas and first-order correspondents of uniform formulas .
    13 Oct 2015
    Tuesday    		 Hoorcollege
    15-17
    SP 904 F1.02    		 Sahlqvist correspondence. See the notes of the Sahlqvist algorithm discussed at the lecture.
    15 Oct 2015
    Thursday    		 Wekcollege
    13-15
    SP 904 C1.112, G3.05    		 Exercises on Sahlqvist correspondence .
    Mid term exam: October 21, 16:00 - 18:00. SP. H0. 08
    27 Oct 2015
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Normal modal logics, soundness, sections 1.6 and 4.2 in Blackburn at al. See also the notes which we followed in the lecture.
    29 Oct 2015
    Thursday    		 Wekcollege
    15-17
    SP D1.113, D1.114    		 Exercises on Hilbert systems. .
    3 Nov 2015
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Completeness of K via canonical models (Section 4.2 in the book, slides 36 - 48 in the notes).
    5 Nov 2015
    Thursday    		 Wekcollege
    15-17
    SP D1.113, G2.02    		 Exercises on soundness and canonical models
    10 Nov 2015
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Completeness of modal logics via canonical models, canonical logics, Sahlqvist theorem without proof, the finite model property, decidability of logics, (Sections 4.2 - 4.3 in the book, slides 48 - 70 in the notes).
    12 Nov 2015
    Thursday    		 Wekcollege
    15-17
    SP D1.113    		 Exercises on soundness and completeness
    17 Nov 2014
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 The finite model property (FMP), decidability (Sec 6.2, see also slides 56 -83), general frames (Sec 1.4), incomplete logics (Sec 4.4).
    19 Nov 2015
    Thursday    		 Wekcollege
    15-17
    SP D1.114, D1.115    		 Exercises on general frames, the FMP and decidability
    24 Nov 2015
    Tuesday    		 Hoorcollege
    15-17
    SP 904 C1.112    		 Propositional Dynamic Logic PDL, regular frames, Fischer-Ladner closure (Example 1.15, Example 1.26, Section 4.8 until Lemma 4.83.)
    26 Nov 2015
    Thursday    		 Wekcollege
    15-17
    SP D1.114, D1.115    		 Exercises on PDL
    1 Dec 2015
    Tuesday    		 Hoorcollege
    15-17
    SP 904 C1.112    		 Completeness of PDL with respect to regular frames. The rest of Section 4.8, but we didn't prove Lemmas 4.87 and 4.88.
    3 Dec 2015
    Thursday    		 Wekcollege
    15-17
    SP A1.14, C1.112    		 More exercises on PDL