結構歸納法是應用在數理邏輯、計算機科學、圖論和一些其他數學領域中的一種證明方法(比如Los's 定理的證明)。它是一種特殊化的數學歸納法。
簡單敘述
通常，它用來證明一些命題P(x)，x是一些遞歸定義的結構（例如樹和表）中的一種。一個良基偏序是定義在這種結構上的。結構歸納法的證明是由證明命題對于所有的極小結構成立，以及如果他在一個結構S的基礎結構中成立，那么它一定也在整個S中成立這些組成。比如，如果一個結構是個這樣一個表，含有偏序 '<'，只要表L 在表M的尾部，那么。在這樣的排序中，空的list[ ]是唯一的最小元素。結構歸納法中，一些命題P(l) 的證明由兩個部分組成：
證明P([])成立 如果P(L) 在表L中成立，如果L 是代表M的底部，那么P(M) 也成立。
實際事例
考慮一下下面表的性質:
[EQ的定義]這里的++ 表示表的加法運算
為了證明這個結論，我們需要定義一下length和加法運算：
[長度定則1][長度定則2] [加法定則1] ([加法定則2]這里的(h:t)代表頭部是h和尾部是t的表。我們定義命題P(l)指在當L是l 時，在整個表M中EQ成立。因此，我們應該證明在表l中P(l)成立。下面，我們將用結構歸納法證明。
首先我們應該證明P([])成立；也就是，L時空空表(list []使時EQ在整個表M中成立。想一想EQ：
(根據 加法定則1) (根據 長度定則1)因此這個定理的第一部分也就證明了，即當L是[]時，EQ在整個M中成立，因為等式的兩邊相等。
現在我們需要證明，當l 是一個非空的標時，P(l)成立。因為l非空，所以他一定會有首部元素，設為x，和尾部元素，設為xs，因此我們可以將非空的表表示為 (x:xs)。歸納假設為當L是xs時，EQ對于所有M的值都成立:
(假設)我們想要說明如果這樣成立，那么當L是尾部是xs的表x:xs時，EQ對于所有M的值都成立。接著進行演算:
(根據 加法定則2) (根據 長度定則2) (根據 長度定則2) 結果正是我們的歸納假設，我們成功了。
優良次序
和標準的數學歸納法等價于良序原理一樣，結構歸納法也等價于良序原理。如果某種整個結構的集容納一個良基偏序，那么每個非空子集一定都含有最小元素。(其實這也是良基的定義) 這個輔助定理用這種形式定義的意義在于他能夠讓我們推論出，如果這里有某個我們需要證明的定理的反例，那么就一定存在一個極小的反例。如果我們能夠指出他的存在，也就意味著有一個更小的反例，我們得到一個矛盾了(因為最小的反例不是最小的)，因此反例的集一定是空集。
這種論證的一個實例：考慮一下所有二叉樹的集合。我們將證明在完全二叉樹中葉子的數目比內部節點的數目多一個。假設這里有一個反例；那么就一定存在含有極小可能數目的內部節點的一個樹。這個反例C 有n 個內部節點和l 個葉子，這里有。而且C要是非平凡的，因為平凡的樹 而且因此不具有反例的條件。因此C 至少含有其親交點的點是一個內部節點的一個葉子。從樹上刪掉這個葉子和他的父輩，將被刪葉子的節點的兄弟節點提升到被刪葉子從前父輩節點所占有的位置。這樣做將n 和l 減少了 1，因此新的樹也有，這樣就得到了一個更小的反例。但是在歸納假設中，C已經是最范例反例了；因此，開始的或許有些反例的猜想被證明了是錯誤的。 '更小'的偏序意味著只要S 比T 的節點少那么。
結構遞歸
結構遞歸和結構歸納法的關系就像普通的遞歸和普通的數學歸納法一樣。
結構歸納法 是應用在數學邏輯、計算機科學、圖論和一些其他數學領域中的一種證明方法 (比如， Los's 定理的證明). 他是一種特殊化的數學歸納法。
通常，他用來證明一些命題P(x)， x是一些遞歸定義的結構（例如樹和表）中的一種.比如，如果一個結構是個這樣一個表，含有偏序 '<'，只要表 L 在表M的尾部，那么.
證明P([])成立
如果P(L) 在表L中成立，如果L 是表 M的底部，那么P(M) 也成立。
參考資料 >