Proof of `Few types far from a parameter set`

groundedproofs/Lax185574Proofs/SeparatingTypes.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 h=7qh = 7^q and r=h+1r = h + 1. Expand the colored graph by a relation for every relation symbol with some positions filled by parameters from UU, and by a unary relation PuP_u for every u∈Uu ∈ U. Formulas with parameters become formulas of the expansion without parameters and with the same quantifier rank. For a tuple far from UU, the ball BB of radius hh around it in the expansion avoids UU and its neighbors, so the new relations are trivial on BB, and the type of rank q′q' of the tuple in the expansion of BB is determined by its type in the colored graph induced on BB. By LocalToGlobalLocalToGlobal, that type determines the type of rank qq in the expansion, hence the type over UU in the colored graph. The types of rank q′q' of kk-tuples in colored graphs are bounded by the number of their finite codes, which depends on qq, kk and cc only.