構造的帰納法
より形式的な例を挙げる。次のようなリストの性質を考える。
ここで L と M はリストであり、演算子 ++ はリストの連結を表している。
これを証明するには、length と ++ の定義が必要である。
ここで (h:t) は、最初の要素が h で、残りの要素がリスト t で表されるようなリストを表す。[] は空のリストを表す。
いま示そうとしているリストの性質 P(L) は、「すべてのリスト M に対して、上述の等式 EQ が成り立つ」ことである。リストに関する構造的帰納法によって、∀L. P(L) を証明する。
まず P([]) が真であることを示そう。つまり、L = [] であるときに、すべてのリスト M に関して EQ が成り立つことだ。これは次の等式で証明される。
次に、すべての 空でない リスト I を考える。I は空でないから、先頭の要素を持つ。それを x とし、残りの要素からなるリストを xs とする。(これは I = x:xs と表せる。) ここでの帰納法の仮定は、すべてのリスト M に対して次の等式 (EQ の L = xs の場合) が成り立つことである。
このとき、P(I)、すなわちすべてのリスト M に対して EQ (の L = I の場合) が成り立つことを示したい。先ほどと同様に計算する。
したがって、構造的帰納法により、すべてのリスト L に対して P(L) が真であることが示された。すなわち、すべてのリスト L と M に対して EQ が真である。