Introduction to Modal Logic

Autumn 2017

Institute for Logic, Language and Computation

Universiteit van Amsterdam


Exam 2016

Exam 2015

Exam 2014

Midterm 2017

Final exam 2017






Practicalities

  • Instructors: Nick Bezhanishvili and Yde Venema , emails: N.Bezhanishvili[at]uva.nl and Y.Venema[at]uva.nl

  • Teaching assistants: Frederik Lauridsen , email: F.M.Lauridsen[at]uva.nl; Gianluca Grilleti , email: grilletti.gianluca[at]gmail.com; Kaibo Xie , email: K.Xie[at]uva.nl

  • Time and Place: Blok 1, Lectures on Thursdays 9:00-11:00 (SP 904, C1. 112), Tutorials on Mondays 13:00-15:00 (SP 904, G5.29 and D1.116).

  • EC: 6

  • Assessment : There will be a midterm exam on 24 October and also a final exam on 21 December. 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. In order to pass the course one needs to score at least 50/100 on the final exam. The homework grade is split into 6 or 7 homework sheets weighing 100 points each. The homework with the lowest score will be disregarded.

  • Midterm exam: The midterm exam will be held on Tuesday, 24 October, 9-12 in Tentamenzaal USC Sporthal 1 SP.

  • Final exam: The final exam will be held on Thursday, 21 December, 9-12 in Tentamenzaal USC Sporthal 1 SP.

  • More specific information about homework and grading: Deadlines for submission are strict; this applies in particular to the condition that homework should be handed in at the beginning of class. Homework handed in after the deadline will not be taken into consideration. Unless explicitly specified otherwise, you are allowed to collaborate with your fellow students, on the following conditions:
  • you can only work in small groups of at most three people;
  • you can discuss the exercises together, but you have to write down the solution individually;
  • you must explicitly write on your homework with whom you have been working together.
    • When writing your solutions to exercises, be succinct. In particular:
  • never prove statements that are explicitly mentioned in the lecture notes (unless specifically asked otherwise); simply refer to these results if you use them;
  • in the case of a routine argument, you do not need to go into all the technical details;
  • in case of proofs by induction on the complexity of formulas, one or two cases will usually suffice.

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 on 21 September before class.

  • Homework 2, due on 5 October before class.

  • Homework 3, due on 19 October before class.

  • Homework 4, due on 14 November before class.

  • Homework 5, due on 28 November before class.

  • Homework 6, due on 12 December before class. See also Figure
    • for a different figure of the frame in Ex1.

    Lectures

    <
    4 Sep 2017
    Monday    		 Werkcollege
    13-15
    Goup A: SP 904 G5.29, Group B: SP 904 D1.116    		 The first tutorial sheet Tutorial 1
    7 Sep 2017
    Thursday    		 Hoorcollege
    9-11
    SP 904 C1.112    		 Introduction to modal logic, syntax and semantics of basic modal logic, bisimulations, bisimilarity, bisimulation invariance theorem, disjoint unions and bounded morphisms (Sections 1.1-1.3, 2.1-2.2)
    11 Sep 2017
    Monday    		 Werkcollege
    13-15
    Goup A: SP 904 G5.29, Group B: SP 904 D1.116    		 The second tutorial sheet Tutorial 2
    14 Sep 2017
    Thursday    		 Hoorcollege
    9-11
    SP 904 C1.112    		 Invariance results, Hennessy-Milner Theorem, Filtration Theorem (smallest filtration) (Sections 2.2-2.3)
    18 Sep 2017
    Monday    		 Werkcollege
    13-15
    Goup A: SP 904 G5.29, Group B: SP 904 D1.116    		 The third tutorial sheet Tutorial 3
    21 Sep 2016
    Thursday    		 Hoorcollege
    9-11
    SP 904 C1.112    		 Tree unravellings and tree model property, finite model property (via filtration and via selection), modal depth and $n$-bisimilarity, the standard translation, propositional dynamic logic (syntax and semantics) (Sections 2.3-2.4).
    25 Sep 2017
    Monday    		 Werkcollege
    13-15
    Goup A: SP 904 G5.29, Group B: SP 904 D1.116    		 The fourth tutorial sheet Tutorial 4
    28 Sep 2017
    Thursday    		 Hoorcollege
    9-11
    SP 904 C1.112    		 Characterization Theorem without proof, m-saturation, filters and ultrafilters, ultrafilter extension (Sections 2.5-2.6)
    2 Oct 2017
    Monday    		 Werkcollege
    13-15
    Goup A: SP 904 G5.29, Group B: SP 904 D1.116    		 The fifth tutorial sheet Tutorial 5
    5 Oct 2017
    Thursday    		 Hoorcollege
    9-11
    SP 904 C1.112    		 Frame definability (Secs 3.1-3.2 until 3.10, Prop 3.12, Thm 3.19 the Goldblatt-Thomason Theorem without proof). Automatic first-order correspondence (Sec 3.5 until uniform formulas).
    9 Oct 2017
    Monday    		 Werkcollege
    13-15
    Goup A: SP 904 G5.29, Group B: SP 904 D1.116    		 The sixth tutorial sheet Tutorial 6
    12 Oct 2017
    Thursday    		 Hoorcollege
    9-11
    SP 904 C1.112    		 Sahlqvist correspondence. The notes on Sahlqvist algorithm (Section 3.6 in the book).
    16 Oct 2017
    Monday    		 Werkcollege
    13-15
    Goup A: SP 904 G5.29, Group B: SP 904 D1.116    		 The seventh tutorial sheet Tutorial 7
    19 Oct 2017
    Thursday    		 Hoorcollege
    9-11
    SP 904 C1.112    		 Logics of classes of frames, normal modal logics. Hilbert style derivation systems, soundness and completeness, consistent sets (Sections 1.6 and 4.1 in the modal logic book, see also slides 1-30 in the Modal Logic Notes)
    Midterm exam: 24 October 2017, 9:00 - 12:00. Tentamenzaal USC Sporthal 1 SP.
    31 Oct 2017
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Completeness of the basic modal logic K via the canonical model construction (Section 4.2 in the modal logic book, slides 37-49 in the Modal Logic Notes)
    1 Nov 2017
    Wednesday    		 Wekcollege
    11-13
    Goup A: SP 904 D1.115, Group B: SP 904 G0.23-G0.25    		 The eighth tutorial sheet Tutorial 8
    7 Nov 2017
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Completeness of normal modal logics via the canonical model construction, canonical logics, Sahlqvist theorem without proof, the finite model property (Sections 4.2-4.3 in the modal logic book, slides 48-77 in the Modal Logic Notes)
    8 Nov 2017
    Wednesday    		 Wekcollege
    11-13
    Goup A: SP 904 D1.115, Group B: SP 904 G0.23-G0.25    		 The ninth tutorial sheet Tutorial 9
    14 Nov 2017
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 General frames (Sec 1.4), incomplete modal logics (Sec 4.4), completeness of normal modal logics with respect to general frames (Sec 5.5 until 5.65).
    15 Nov 2017
    Wednesday    		 Wekcollege
    11-13
    Goups A and B: SP 904 D1.115    		 The tenth tutorial sheet Tutorial 10
    21 Nov 2017
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Propositional Dynamic Logic, PDL. Regular frames, soundness of PDL, Fischer-Ladner closure, atoms. (Section 4.8 until 4.81).
    22 Nov 2017
    Wednesday    		 Wekcollege
    11-13
    Goups A and B: SP 904 D1.115    		 The eleventh tutorial sheet Tutorial 11
    28 Nov 2017
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Completeness of PDL with respect to regular frames (4.81-4.91).
    29 Nov 2017
    Wednesday    		 Wekcollege
    11-13
    Goups A and B: SP 904 D1.115    		 The twelfth tutorial sheet Tutorial 12
    5 Dec 2017
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Motivation for non-normal logics, the landscape of non-normal modal logics, neighbourhood frames and models, neighbourhood semantics (1.3, 2.3, 1.2.1 in Neighborhood Semantics for Modal Logic.)
    6 Dec 2017
    Wednesday    		 Wekcollege
    11-13
    Goups A and B: SP 904 D1.115    		 The thirteenth tutorial sheet Tutorial 13
    12 Dec 2017
    Tuesday    		 Hoorcollege
    13-15
    SP 904 C1.112    		 Two semantics of modal logic on monotone frames (page 40), expressive power and invariance (Section 2.1 until 2.9, we didn't prove Theorems 2.6 and 2.7), relational models (Section 2.2.1), completeness and canonical models (Sections 2.3.1).
    15 Dec 2017
    Friday    		 Wekcollege
    15-17
    Goups A and B: SP 904 G0.05    		 The fourteenth tutorial sheet Tutorial 14