The exponential gap between the first-order quantifier rank and modal quantifier rank

37 Views Asked by At

In the proof of van Benthem/Rosen characterisation theorem that modal logic corresponds exactly to the fragment of first-order logic that is invariant under bisimulation, we can use Ehrenfeucht-Fraisse games. One of the consequences of that proof is that for FO-formula $\varphi$ of quantifier rank $q$, we can find logically equivalent modal formula of modal quantifier rank $2^q-1$ and, in general, that is the best solution for modal quantifier rank.

Why do we need the exponential gap between the first-order quantifier rank and modal quantifier rank (in general and in the proof of that theorem)?