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.
In the paper
- page 52 of this submission's paper
Description
Put . By the locality lemma, every node of 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 such colors and at most trees per rank and arity by part (i). So every root has atoms, every node has at most children, and the depth is . This gives the bound , where depends on and only.