結構歸納法

結構歸納法是一種特殊化的數學歸納法，套用在數學邏輯、計算機科學、圖論和一些其他數學領域。

簡介

結構歸納法 是套用在數學邏輯、計算機科學、圖論和一些其他數學領域中的一種證明方法 (比如,Los's 定理的證明). 他是一種特殊化的數學歸納法.
通常, 他用來證明一些命題P(x), x是一些遞歸定義的結構（例如樹和表）中的一種. 一個良基 偏序 是定義在這種結構上的.結構歸納法的證明是由證明命題對於所有的極小結構成立,以及如果他在一個結構S的基礎結構中成立, 那么他一定也在整個S中成立這些組成. 比如, 如果一個結構是個這樣一個表,含有偏序 '<',只要表 L 在表M的尾部,那么L < M. 在這樣的排序中, 空的list【 】是唯一的最小元素.結構歸納法中,一些命題P(l) 的證明由兩個部分組成:

證明過程

證明P(【】)成立
如果P(L) 在表L中成立, 如果L 是表 M的底部, 那么P(M) 也成立.