Proof of `Closure theorem`
groundedproofs/Lax185574Proofs/ClosureTheorem.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 21 of this submission's paper
Description
Induction on , as in the paper. At radius 0 take and no flip. For the step, enlarge to by the ball-types lemma for the current parameter bound , and apply the induction hypothesis to , giving . The -definable flips of graphs of the class form a monadically dependent class, so they have VC-dimension at most some . For every set of at most vertices and every -flip (at most of them), group the vertices whose radius- ball in avoids by the set of atomic types over that the ball meets. By the ball-types lemma these profiles have at most members, and by the Sauer–Shelah lemma there are at most atomic types over , so there are polynomially many groups. The ball flip lemma gives a -definable flip of that -separates each group from , which is an -definable flip of by transitivity. The new closure is together with the parameters of all these flips. Vertices of are isolated by the flip over themselves.
The argument is carried out for the graph classes of the archive and their monadic dependence, and transferred to the graph classes used here.