Proof of `Gaifman's locality theorem with a rank bound`

groundedproofs/Lax185574Proofs/GaifmanLocality.lean · lax-185574

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

In the paper

  • page 63 of this submission's paper

Description

The formula is translated into the syntax of the normal form of lax-512892, over a vocabulary with one symbol for each relation symbol and a nullary symbol for falsum. Its normal form has radii at most 7q−17^q − 1 and at most q+kq + k witnesses in each basic local sentence. Every local formula in it has quantifier depth at most q⋅(k+q+2+6⋅7q+4α)q · (k + q + 2 + 6 · 7^q + 4α), a bound that depends on the arity αα of the vocabulary but not on its symbols. Back in mathlib's syntax, each ball-restricted quantifier gets a dist-formula guard of quantifier rank at most 7q+α7^q + α, which gives the rank bound p=q⋅(k+q+2+6⋅7q+4α)+q+k+2⋅7q+2αp = q · (k + q + 2 + 6 · 7^q + 4α) + q + k + 2 · 7^q + 2α.