结构归纳法

结构归纳法是应用在数理逻辑、计算机科学、图论和一些其他数学领域的证明方法（比如Łoś定理的证明），是一般化的数学归纳法 （数学归纳法仅仅定义在自然数上）。 其通常用来证明一些命题 P（x），x 是递归定义结构（例如树和表）的一种。良基偏序是定义在这种结构上的。结构归纳法的证明是由证明命题对于所有的极小结构成立，以及如果他在一个结构 S 的基础结构中成立，那么其一定也在整个 S 中成立这些组成。比如，如果一个结构是个这样一个表，含有偏序 '<'，只要表 L 在表 M 的尾部，那么 L < M。在这样的排序中，空的 list[ ] 是唯一的最小元素。结构归纳法中，一些命题 P（l） 的证明由两个部分组成： * 证明 P（[]）成立 * 如果 P（L） 在表 L 中成立， 如果 L 是表 M 的底部， 那么 P（M） 也成立。