Proof of `Types are determined by types in a neighborhood`

groundedproofs/Lax185574Proofs/LocalToGlobal.lean · lax-185574

What this proof establishes

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

Let q′=p(α,q,k)q' = p(α, q, k) be given by GaifmanLocalityGaifmanLocality. A formula of rank at most qq uses finitely many relation symbols. Over the sublanguage of these symbols it is equivalent, on finite structures, to a Boolean combination of basic 7q7^q-local sentences and 7q7^q-local formulas of rank at most q′q'. The sentences have the same truth value for both tuples. A local formula holds of a tuple in the structure if and only if it holds in the induced substructure, by LocalSubstructureLocalSubstructure, since the balls of the sublanguage are contained in those of LL. In the induced substructures, the two tuples satisfy the same formulas of rank at most q′q'.