[附注]
归纳假设不只限于直接子项
[附注] 归纳假设不只限于直接子项
“只能对直接子项使用”是 [定理] 结构归纳原理(structural induction) 的直接表述,不是一切归纳法的限制。若改用强归纳,先证明某个自然数度量严格下降,就可以对度量更小的任意对象使用 归纳假设 ;对真子项的归纳也可以成立。一般的要求叫良基性(well-foundedness):不存在无限地向更小对象下降的链。
[定义] 直接子项与真子项 的直接子项关系在 [定义] 项的集合 的有限树上是良基的,但“归约后的项”并不因此自动是直接子项。例如按 [定义] 一步归约 , 一次计算变成 ,后者不是前者的直接子项。要在证明中对归约结果使用 归纳假设 ,必须另证合适的度量下降,或选择相应的归纳原理。用在一个不被当前归纳原理许可的对象上,证明就是缺了一步;若这个缺口依赖当前结论来填,就构成循环论证。