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.
In the paper
- page 63 of this submission's paper
Description
Let and . Expand the colored graph by a relation for every relation symbol with some positions filled by parameters from , and by a unary relation for every . Formulas with parameters become formulas of the expansion without parameters and with the same quantifier rank. For a tuple far from , the ball of radius around it in the expansion avoids and its neighbors, so the new relations are trivial on , and the type of rank of the tuple in the expansion of is determined by its type in the colored graph induced on . By , that type determines the type of rank in the expansion, hence the type over in the colored graph. The types of rank of -tuples in colored graphs are bounded by the number of their finite codes, which depends on , and only.