Game comonads for existential and positive equivalence
Seminar, Laboratoire d'Informatique de Paris Nord, Villetaneuse, France
Model-comparison games such as pebble or Ehrenfeucht-Fraïssé games have long been central to model theory. A structural account for these games is given by the notion of game comonads, which allow to capture the preservation of some fragment of first order logics, with a finite resource, as the existence of some morphisms in a certain category of coalgebras. We illustrate the general ideas of game comonads and first results of preservation. A old restriction of the problem is the preservation of the existential positive fragment, which is known for a long time to be much easier that the full fragment. A question that arose next was the gap between this existential positive fragment and the full fragment. To study how negation on the one hand and universal quatifiers on the other hand behave, we study preservation of the existential and the positive fragment separetely, and we give characterisations of preservation of these fragments as existence of morphisms between coalgebras. Finally, if we have time, we expose shortly the notion of arboreal categories, that unify all our coalgebras categories and give an axiomatic account of the result.