[定理] 结构归纳原理(structural induction)

设 𝑃 是关于 [定义] 项的集合 中有限项的一个性质。如果下面三条都成立:

  1. 𝑃( true )、𝑃( false )、𝑃( 0 );
  2. 对任意项 𝑡 1,由 𝑃( 𝑡 1 ) 能推出 𝑃( succ 𝑡 1 )、𝑃( pred 𝑡 1 )、𝑃( iszero 𝑡 1 );
  3. 对任意项 𝑡 1,𝑡 2,𝑡 3,由 𝑃( 𝑡 1 )、𝑃( 𝑡 2 )、𝑃( 𝑡 3 ) 能推出 𝑃( if 𝑡 1 then 𝑡 2 else 𝑡 3 ),

那么对所有项 𝑡,𝑃( 𝑡 ) 成立。

证明
令 ,即满足 𝑃 的项组成的集合。三条假设恰好说明 𝑆 满足 [定义] 项的集合 的三条封闭条件。由于 是满足封闭条件的最小集合,。也就是说每个项都在 𝑆 里,都满足 𝑃。
∎

References

[定义] 项的集合 [set-of-terms]

Backlinks

Based on Typsite