[定义] 归纳假设

归纳假设(induction hypothesis)是在一个归纳步骤中,对归纳原理许可的更小对象暂时假定的性质。它是用来证明“如果这些更小对象满足 𝑃,那么当前对象也满足 𝑃”的前提,不是把“所有对象都满足 𝑃”或当前待证结论预先当真。

在 [定理] 结构归纳原理(structural induction) 的第 2 条中,归纳假设是 𝑃( 𝑡 1 );第 3 条中是 𝑃( 𝑡 1 )、𝑃( 𝑡 2 )、𝑃( 𝑡 3 )。这些对象恰好是 [定义] 直接子项与真子项 中列出的直接子项。常量没有子项,所以基础情形没有归纳假设,必须直接证明。

为什么这种暂时假定合法?我们首先证明的是一个条件命题;每个实际项都由有限次构造得到,从已经验证的叶子出发,逐层应用这个条件命题,就能把性质传到根。假设只沿着更小的结构使用,不会绕回当前待证结论。

References

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

[定义] 直接子项与真子项 [immediate-and-proper-subterms]

Backlinks

Based on Typsite