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