From Quantifier Depth to Quantifier Number: Separating Structures with k Variables

Abstract

Given two $n$-element structures, $\mathcal{A}$ and $\mathcal{B}$, which can be distinguished by a sentence of $k$-variable first-order logic (${\mathcal{L}}^k$), what is the minimum $f(n)$ such that there is guaranteed to be a sentence $\varphi \in {\mathcal{L}}^k$ with at most $f(n)$ quantifiers, such that $\mathcal{A}\models \varphi$ but $\mathcal{B}/\models \varphi$? We present various results related to this question obtained by using the recently introduced QVT games. In particular, we show that when we limit the number of variables, there can be an exponential gap between the quantifier depth and the quantifier number needed to separate two structures. Through the lens of this question, we will highlight some difficulties that arise in analysing the QVT game and some techniques which can help to overcome them. As a consequence, we show that ${\mathcal{L}}^{k+1}$ is exponentially more succinct than ${\mathcal{L}}^k$. We also show, in the setting of the existential-positive fragment, how to lift quantifier depth lower bounds to quantifier number lower bounds. This leads to almost tight bounds.

53 pages, 8 figures; added new result on the relative succinctness of finite variable logic