Proof of `Type tree sizes` (1st statement)

groundedproofs/Lax185574Proofs/TypeTreeSizes.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 52 of this submission's paper

Description

Put K=∣Typesd,d(Ballr(v))∣K = |Types_{d,d}(Ball_r(v))|. By the locality lemma, every node of treek,q(v)tree_{k,q}(v) is the tree of a tuple from the ball, and every color in a true atom of its root meets the ball. There are at most KK such colors and at most KK trees per rank and arity by part (i). So every root has Ok,q(K)O_{k,q}(K) atoms, every node has at most (q+1)K(q+1) K children, and the depth is qq. This gives the bound (3+D)(K+1)(q+1)(3 + D) (K+1)^(q+1), where DD depends on kk and qq only.