[定义]
归纳假设
[定义] 归纳假设
归纳假设(induction hypothesis)是在一个归纳步骤中,对归纳原理许可的更小对象暂时假定的性质。它是用来证明“如果这些更小对象满足 ,那么当前对象也满足 ”的前提,不是把“所有对象都满足 ”或当前待证结论预先当真。
在 [定理] 结构归纳原理(structural induction) 的第 2 条中,归纳假设是 ;第 3 条中是 、、。这些对象恰好是 [定义] 直接子项与真子项 中列出的直接子项。常量没有子项,所以基础情形没有归纳假设,必须直接证明。
为什么这种暂时假定合法?我们首先证明的是一个条件命题;每个实际项都由有限次构造得到,从已经验证的叶子出发,逐层应用这个条件命题,就能把性质传到根。假设只沿着更小的结构使用,不会绕回当前待证结论。
Backlinks
Backlinks
[引理] 深度小于大小 [depth-is-less-than-size]
[引理] 值不可归约 [values-do-not-reduce]
[例] 合法的归纳假设与循环论证 [induction-hypotheses-and-circular-reasoning]
[附注] 归纳假设不只限于直接子项 [scope-of-induction-hypotheses]
[定理] 算法完备性 [type-checking-algorithm-completeness]
[定理] 算法可靠性 [type-checking-algorithm-soundness]
[约定] 归纳证明的写法 [writing-inductive-proofs]
[] 确定性:从推导归纳到求值器 [determinism]
[定理] 类型唯一 [uniqueness-of-types]
[附注] 为什么要“对 一般化” [generalizing-the-type-in-preservation-proofs]