The Scandinavian Logic Society

NOL Seminar with Lauri Hella

UPDATE 2024-02-26: This event has been postponed to 4 March 2024.

The Nordic Online Logic Seminar is organised monthly over Zoom, with expository talks on topics of interest for the broader logic community. The seminar is open for professional or aspiring logicians and logic aficionados worldwide. If you wish to receive the Zoom ID and password for it, as well as further announcements, please subscribe here:

Date: Monday, 26 February 4 March 2024 at 16:00 CET (UTC+1) on Zoom
Speaker: Lauri Hella, Professor at the Faculty of Information Technology and Communication Sciences, Tampere University
Title: Game characterizations for the number of quantifiers

A game that characterizes definability of classes of structures by first-order sentences containing a given number of quantifiers was introduced by Immerman in 1981. In this talk I describe two other games that are equivalent with the Immerman game in the sense that they characterize definability by a given number of quantifiers.

In the Immerman game, Duplicator has a canonical optimal strategy, and hence Duplicator can be completely removed from the game by replacing her moves with default moves given by this optimal strategy. On the other hand, in the other two games there is no such optimal strategy for Duplicator. Thus, the Immerman game can be regarded as a one-player game, but the other two games are genuine two-player games.

The talk is based on joint work with Kerkko Luosto.