From Quantifier Depth to Quantifier Number: Separating Structures in Finite Variable Logic

Harry Vinall-Smeeth and Christoph Berkholz

11:40AM - 12:15PM, Sat, Jun 24.
Abstract (PDF)

Given two n-element structures, A and B, which can be distinguished by a sentence of k-variable first-order logic, what is the minimum f(n,k) such that there is guaranteed to be a sentence ϕ ∈ ℒk with at most f(n,k) quantifiers, such that A ⊨ ϕ but B ⊭ ϕ? We will present various results related to this question obtained by using the recently introduced QVT games. Through the lens of this question, we will highlight some difficulties that arise in analysing the QVT game and share some insights which can help to overcome them. A core theme is that of lifting quantifier depth lower bounds to quantifier number lower bounds.

[Back to Schedule]