Lemma. 深度小于大小 Glomzzz 2026-10-10 About 对 词项的集合 中的所有有限项 𝑡， 采用 大小与深度 的函数定义， 有 depth( 𝑡 )<size( 𝑡 )．Proof.按 结构归纳原理 对 𝑡 作结构归纳． 若 𝑡 是常量，则 depth( 𝑡 )=0<1=size( 𝑡 )． 若 𝑡= succ 𝑡 1（pred、iszero 完全相同）， 归纳假设 是 depth( 𝑡 1 )<size( 𝑡 1 )，两边加一即得 depth( 𝑡 )<size( 𝑡 )． 若 𝑡= if 𝑡 1 then 𝑡 2 else 𝑡 3，设 𝑡 𝑖 是三个子项中深度最大的，由 归纳假设 得depth( 𝑡 )=depth( 𝑡 𝑖 )+1<size( 𝑡 𝑖 )+1≤size( 𝑡 1 )+size( 𝑡 2 )+size( 𝑡 3 )+1=size( 𝑡 )其中 ≤ 用到了每个子项的大小都至少为 1．∎
