Speaker: Gianluca Grilletti
Date and Time: Thursday, September 20th 2018, 16:30-18:00
Venue: ILLC Seminar Room F1.15, Science Park 107.
Title: An Ehrenfeucht-Fraïssé Game for InqBQ.
Abstract. InqBQ [1] is a first-order version of inquisitive logic, encompassing both questions and quantifiers. Questions like “What is an element with property P?’’ and “What is the extension of property P?” can be represented using the usual logical operators from first-order logic in addition to the inquisitive counterpart of classical disjunction and classical existential quantifier respectively. Several questions about InqBQ remain open: Is the entailment of the logic axiomatizable? Does the entailment between questions boil down to some dependency between the statements supporting the questions? Which questions are expressible and which are not expressible? Ehrenfeucht-Fraïssé games [2,4] proved to be a valuable tool to study the expressive power of several logics [3,5,8]. The main idea is to characterize logical equivalence between models, w.r.t. the whole logic or certain fragments of it, using game-theoretic tools; this in turn gives a strategy to prove that certain properties of models — e.g. the finiteness of the domain in first-order logic — are not expressible, namely by finding a winning strategy in a suitable game. In this talk I will present an EF-game for InqBQ and the corresponding characterization theorem. I will apply the result obtained to show that certain natural questions — e.g. “How many elements have property P?” — are not expressible by InqBQ formulas. (This is joint work with Ivano Ciardelli.)
References
[1] Ivano Ciardelli. Questions in logic. PhD thesis, Institute for Logic, Language and Computation, University of Amsterdam, 2016.
[2] Andrzej Ehrenfeucht. An application of games to the completeness problem for formalized theories. Journal of Symbolic Logic, 32(2):281–282, 1967.
[3] Ronald Fagin. Monadic Generalized Spectra. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 21:89–96, 1975.
[4] Roland Fraïssé. Sur quelques classifications des systèmes de relations. Publications Scientifiques de l’Université D’Alger, 1(1):35–182, June 1954.
[5] Neil Immerman. Upper and lower bounds for first order expressibility. Journal of Com-
puter and System Sciences, 25(1):76–98, 1982.
[6] Jouko Väänänen. Models and Games. Cambridge University Press, New York, NY, USA, 1st edition, 2011.