Universal coalgebra is a unifying mathematical framework, rooted in category theory, for modelling state-based evolving systems such as automata, Markov chains and Kripke models. It provides, in a uniform way, tools like final coalgebras (canonical models formalising the notion of behaviour), coinduction (a definition and proof principle dual to induction) to reason about behaviour, and bisimulations as a means for capturing the notion of behavioural equivalence.

Modal languages are simple yet expressive and flexible tools for describing all kinds of structures. Thus modal logic finds applications in many disciplines such as computer science, mathematics, linguistics or economics. Notwithstanding this enormous diversity in appearance and application area, modal logics have a great number of properties in common.

The course starts with an introduction to universal coalgebra as a general theory for state-based evolving systems. We then continue with showing how to use coalgebra to unify many different branches of modal logic under the umbrella of coalgebraic modal logic. Examples include standard, monotone, graded and probabilistic modal logics.

Prerequisites: We also assume familiarity with the basic concepts from the theory of modal logic, such as the syntax and semantics of propositional modal formulas, the notion of bisimulation and the technique of filtration and its use to prove the finite model property of basic modal logic.

The main goal of the course is for students to become familiar with the basic notions of universal coalgebra and its use in unifying various branches of modal logic.

The following is a tentative schedule, which can be modified on the basis of the dynamics of the class and feedback from the students.
Lecture 1: examples of coalgebras
Lecture 2: coalgebras and their morphism, final coalgebras and behavioural equivalence
Lecture 3: versions of modal logic
Lecture 4: final coalgebras
Lecture 5: coinduction
Lecture 6: bisimulation
Lecture 7: bisimilarity and behavioural equivalence
Lecture 8: some constructions from category theory
Lecture 9: operations on coalgebras
Lecture 10: modalities from predicate liftings
Lecture 11: examples of coalgebraic modal logics
Lecture 12: invariance
Lecture 13: expressiveness
Lecture 14: filtration and the finite model property
Lecture 15: further perspectives.

Students will be given homework exercises on a daily basis.

Your final grade will be determined by the following two components:
Daily Homework (80%): Four problem sets will be assigned, each worth 20%. Assignments are due at the start of the next day's lecture.
Contribution to Class (20%): Evaluated based on active engagement, including asking questions and presenting solutions on the whiteboard.

At the beginning of the course a pdf containing Lecture Notes will be made available.

C. Cîrstea, A. Kurz, D. Pattinson, L. Schröder and Y. Venema, Modal logics are coalgebraic, The Computer Journal, 54 (2011) 31-41.
The Method of Coalgebra: exercises in coinduction Jan Rutten CWI 2019
Introduction to Coalgebra: towards mathematics of states and observation Bart Jacobs Cambridge University Press, 2016

この科目は出願の際に成績証明書の提出が必要です。

The main instructor of the course is Prof. Yde Venema (Institute for Logic, Language and Computation, University of Amsterdam, https://staff.science.uva.nl/y.venema/)