NOL Seminar with Lauri Hella
published: 2024-02-18
event date:
2024-03-04
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:
https://listserv.gu.se/sympa/subscribe/nordiclogic
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
Abstract
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.