Relating Structure to Power: An Invitation to Game Comonads

Summer course. Last update: 2022-08-12.

A week 1 course of ESSLLI 2022, sponsored by the European Association for Computer Science Logic (EACSL)

Taught jointly by Tomáš Jakl and Luca Reggio.

This course will introduce the emerging theory of game comonads, recently put forward by Abramsky, Dawar and their collaborators. Game comonads offer a novel approach to relating categorical semantics to finite model theory.

We will develop their basic theory and illustrate how they provide a structural and intrinsic account of several concrete notions that play a central role in finite model theory. These range from equivalence with respect to logic fragments (e.g., finite-variable, bounded quantifier rank, and modal fragments), to combinatorial parameters of structures (e.g., tree-width and tree-depth, or the height of a synchronization tree), and model comparison games (e.g., pebble, Ehrenfeucht-Fraïssé, and bisimulation games).

Course material

Course overview

Lecture 1: Syntax and semantics: a fruitful duality

Lecture 2: Games and game comonads

Lecture 3: Coalgebras and combinatorial parameters

Lecture 4: Game comonads and logical equivalences

Lecture 5: Advanced topics


Generally speaking, a certain degree of mathematical maturity is expected from the students. This includes familiarity with basic notions of discrete mathematics, such as sets, functions, relations, partial orders, and mathematical induction. Familiarity with more advanced topics in order theory, such as Galois connections between posets, would be useful but is not essential as the relevant notions will be recalled in the course. With regard to logic and category theory, the prerequisites are detailed below:

Logic: Basic familiarity with (classical) propositional and first-order logics is assumed, as well as with the concepts of syntax and semantics, as can be found in any textbook on the subject (a self-contained, albeit terse, account can be found in Section 2.1 of (Libkin, 2004). This includes, in particular, the ability to read a formula in first-order logic and interpret it in a model. A similar degree of acquaintance with modal logic (corresponding roughly to Sections 1.1–1.3 of (Blackburn–de Rijke–Venema, 2001) is desirable, although the relevant concepts will be reviewed.

Category theory: Familiarity with basic notions of category theory is a prerequisite for the course. These include the concepts of categories, functors, natural transformations, isomorphisms, monomorphisms, and epimorphisms. This material (and much more) can be found in the first two chapters of (Adámek–Herrlich–Strecker, 1990), or in Sections 1.1–1.5 of (Abramsky–Tzevelekos, 2011). Some familiarity with more advanced notions, such as adjunctions, limits, colimits, universal constructions, and comonads, is useful but not essential: these concepts will be motivated and introduced during the course through the examples of game comonads.

We provide a Review of Category Theory, for a quick reference of the basic topics that we will need throughout the course.

Guided Bibliography

Game comonads represent a recent advance in relating categorical semantics to finite model theory, and their study has gathered considerable momentum. As such, there is no single reference for their basic theory, which has been developed in a series of research articles. As a guide through the emerging theory of game comonads, we indicate some references relevant to the course, for those who might wish to explore some of the topics more fully.

For a gentle introduction to the fundamental ideas of game comonads, we warmly recommend the following survey:

The core of the course, focussing on game comonads, is based on the following research articles (in particular, we recommend (Abramsky–Shah, 2021) as the gateway to the basic results on game comonads):

The following more advanced articles on game comonads are also relevant, and at the end of the course the students will have the necessary background to undertake self-study:

The following monographs on category theory, finite model theory, and modal logic, are meant to guide the interested reader who may wish to learn more about these topics. Familiarity with these texts is not a prerequisite for the course (except for some basic concepts of logic and category theory, as detailed in the Prerequisites).

Web Analytics