[定理] 结构归纳原理(structural induction) Glomzzz 2026-10-10 About 设 𝑃 是关于 [定义] 项的集合 中有限项的一个性质。如果下面三条都成立:𝑃( true )、𝑃( false )、𝑃( 0 );对任意项 𝑡 1,由 𝑃( 𝑡 1 ) 能推出 𝑃( succ 𝑡 1 )、𝑃( pred 𝑡 1 )、𝑃( iszero 𝑡 1 );对任意项 𝑡 1,𝑡 2,𝑡 3,由 𝑃( 𝑡 1 )、𝑃( 𝑡 2 )、𝑃( 𝑡 3 ) 能推出 𝑃( if 𝑡 1 then 𝑡 2 else 𝑡 3 ),那么对所有项 𝑡,𝑃( 𝑡 ) 成立。证明令 ,即满足 𝑃 的项组成的集合。三条假设恰好说明 𝑆 满足 [定义] 项的集合 的三条封闭条件。由于 是满足封闭条件的最小集合,。也就是说每个项都在 𝑆 里,都满足 𝑃。∎ References [定义] 项的集合 [set-of-terms] Backlinks [约定] 归纳证明的写法 [writing-inductive-proofs] [附注] 什么是归纳 [meaning-of-induction] [定义] 归纳假设 [induction-hypothesis] [注记] 潜无穷与实无穷 [potential-and-actual-infinity] [] 回头看与延伸阅读 [summary] [引理] 深度小于大小 [depth-is-less-than-size] [] 语法:BNF、最小集合与结构归纳 [syntax] [] 确定性:从推导归纳到求值器 [determinism] [例] 合法的归纳假设与循环论证 [induction-hypotheses-and-circular-reasoning] [附注] 归纳假设不只限于直接子项 [scope-of-induction-hypotheses] Based on Typsite