Proof of `Type tree sizes` (2nd 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

A tuple vˉ∈Xℓv̄ ∈ X^ℓ is padded to a dd-tuple by repeating its last entry. The type of quantifier rank dd of the padded tuple determines the type of vˉv̄ of quantifier rank dd, which determines treek+i,q−i(vˉ)tree_{k+i,q−i}(v̄) by treeeqoftpeqtree_eq_of_tp_eq, since ρ+(k+i,q−i)+q−i≤dρ⁺(k+i, q−i) + q − i ≤ d. So the type trees are the image of a function on Typesd,d(X)Types_{d,d}(X).