202501300001

Tags : Finite Model Theory

Hanf-local Queries are Gaifman-local

---

Theorem

If $Q$ is a Hanf local non-boolean query, then $Q$ is Gaifman local, and $\text{lr}(Q)\le 3\cdot \text{hlr}(Q)+1$.

Using FO Queries are Hanf Local, Consider 2 copies of $\mathfrak{A}$ which have $\text{hlr}(Q)=d$ and ${\vec{a}}_1{\approx }_{3d+1}{\vec{a}}_2$. But since $\mathfrak{A}{\leftrightarrows }_d\mathfrak{A}$ we have $(\mathfrak{A},{\vec{a}}_1)\leftrightarrows (\mathfrak{A},{\vec{a}}_2)$ because of Local Equivalence Lemma.

So $a_1\in Q(\mathfrak{A})⟺a_2\in Q(\mathfrak{A})$ which shows that $\text{lr}(Q)\le 3d+1$.

Another corollary for this is, if $Q$ is defined by a $\text{FO}[k]$ formula then

$$\text{lr}(Q)\le \frac{3^{k+1}-1}{2}$$

---

References