帰納法

帰納法の例(自然数)

項の定義

V を可算無限個の変数の集合、F = {0, '}とします。 項 T(F, V) は以下の条件を満たす最小の集合とします。
  1. x∈V ⇒ x∈T(F, V)
  2. 0∈T(F, V)
  3. x∈T(F, V) ⇒ x'∈T(F, V)

+ の定義

+: T(F, V)×T(F, V)→T(F, V) を以下のように定義します。 (これは自然数の加法の意味になります。)
  1. x + 0 = x
  2. x + y' = (x + y)'

0 + x = x の証明

このとき 0 + x = x が任意の x∈T(F)={0, 0', 0'', …} に対して成り立っていることを証明します。 そのためには、
  1. 0 + 0 = 0
  2. 0 + x = x ⇒ 0 + x' = x'
が成り立っていることを証明すれば十分です。 これは以下のように示すことができます。
  1. [ 0 + 0 = 0 ] ← [ 0 = 0 ]
  2. [ 0 + x' = x' ] ← [ (0 + x)' = x' ] ← [ 0 + x = x ]

(x + y) + z = x + (y + z) の証明

次に (x + y) + z = x + (y + z) が任意の x∈T(F)={0, 0', 0'', …} に対して成り立っていることを証明します。 これは以下のように示すことができます。
  1. [ (x + y) + 0 = x + (y + 0) ] ← [ x + y = x + y ]
  2. [ (x + y) + z' = x + (y + z') ] ← [ ((x + y) + z)' = x + (y + z)' ] ← [ ((x + y) + z)' = (x + (y + z))' ] ← [ (x + y) + z = x + (y + z) ]

証明の別の方法

s: N×T(F, V)→T(F, V) を
  1. s(0, x) = x
  2. s(n + 1, x) = s(n, x)'
と定義すると、+ の定義より x + s(n, y) = s(n, x + y) が成り立つので
  1. x + s(n, y) = s(n, x + y) ⇒ 0 + s(n, 0) = s(n, 0 + 0) ⇒ 0 + s(n, 0) = s(n, 0) ⇒ 0 + x = x
  2. x + s(n, y) = s(n, x + y) ⇒ (x + y) + s(n, 0) = s(n, (x + y) + 0) ⇒ (x + y) + s(n, 0) = s(n, x + y) ⇒ (x + y) + s(n, 0) = x + s(n, y) ⇒ (x + y) + s(n, 0) = x + s(n, y + 0) ⇒ (x + y) + s(n, 0) = x + (y + s(n, 0)) ⇒ (x + y) + z = x + (y + z)
となって、0 + x = x, (x + y) + z = x + (y + z) を証明することができます。 (この方法で証明をやってみることができます)

帰納法の例(群1)

X を以下の条件をみたす写像 ': X→X, sol: N×X→Boolean, 0∈X と順序関係 ≦ がある集合とします。 (≦は群の部分群の間の包含関係の意味になります。)
  1. 0≦x
  2. x≦y ⇒ x'≦y'
  3. sol(0, x) ⇔ x≦0
  4. sol(n + 1, x) ⇔ sol(n, x')
このとき sol(n, x) ∧ y≦x ⇒ sol(n, y) が任意の n∈N に対して成り立っていることを証明します。 (これは可解群の部分群が可解であるという意味になります。) そのためには、
  1. x≦0 ∧ y≦x ⇒ y≦0
  2. [ sol(n, x) ∧ y≦x ⇒ sol(n, y) ] ⇒ [ sol(n + 1, x) ∧ y≦x ⇒ sol(n + 1, y) ]
が成り立っていることを証明すれば十分です。 これは以下のように示すことができます。
  1. [ x≦0 ∧ y≦x ⇒ y≦0 ]
  2. [ sol(n + 1, x) ∧ y≦x ⇒ sol(n + 1, y) ] ← [ sol(n, x') ∧ y≦x ⇒ sol(n, y') ] ← [ sol(n, x') ∧ y'≦x' ⇒ sol(n, y') ]
この結果は以下の方法で証明することもできます。 d: N×X→X を
  1. d(0, x) = 0
  2. d(n + 1, x) = d(n, x)'
と定義すると、', sol の定義より
  1. x≦y ⇒ d(n, x)≦d(n, y)
  2. sol(n, x) ⇔ sol(0, d(n, x))
が成り立つので
  1. sol(n, x) ∧ y≦x ⇒ sol(0, d(n, x)) ∧ d(n, x)≦d(n, y) ⇒ d(n, x)≦0 ∧ d(n, x)≦d(n, y) ⇒ d(n, y)≦0 ⇒ sol(0, d(n, y)) ⇒ sol(n, y)
が成り立ちます。

帰納法の例(群2)

X を以下の条件をみたす写像 -: X→X, +: X×X→X, inn: X×X→X, 0∈X と順序関係 ≦ がある集合とします。 (≦は群の部分集合の間の包含関係の意味になります。)
  1. inn(-x, y)≦-inn(x, y)
  2. inn(x + y, z)≦inn(x, z) + inn(y, z)
gr: N×X→X を
  1. gr(0, x) = x
  2. gr(n + 1, x) = gr(n, x) ∪ -gr(n, x) ∪ gr(n, x)+gr(n, x)
とすると
  1. inn(gr(0, x), y) ≦ gr(0, inn(x, y))
  2. inn(gr(n, x), y) ≦ gr(n, inn(x, y)) ⇒ inn(gr(n+1, x), y) ≦ gr(n+1, inn(x, y))
となるので inn(gr(n, x), y) ≦ gr(n, inn(x, y)) が成り立ちます。 (これは群 G の部分集合 H, K に対して <H>K⊆<HK>が成り立つという意味になります。 このことから HG⊆G ならば H は G の正規部分群になるということを 示すことができます。)

帰納法の例(リー代数)

X を以下の条件をみたす写像 +: X×X→X, [,]: X×X→X, 0∈X と順序関係 ≦ がある集合とします。 (≦はリー代数の部分ベクトル空間の間の包含関係の意味になります。)
  1. 0≦x
  2. [[x, y], z]≦[[x, z], y]+[x, [y, z]]
  3. x + y = y + x
  4. (x + y) + z = x + (y + z)
inn: X×N×X→X を
  1. inn(x, 0, y) = x
  2. inn(x, n + 1, y) = [inn(x, n, y), x]
とすると
  1. inn([inn(x, m, z), inn(x, n, z)], r+1, z) ≦inn([inn(x, m+1, z), inn(x, n, z)], r, z) +inn([inn(x, m, z), inn(x, n+1, z)], r, z)
となるので
  1. inn([inn(x, m, z), inn(x, n, z)], r+k, z) ≦Σi+j=kinn([inn(x, m+i, z), inn(x, n+j, z)], r, z)
が成り立ちます。 y=Σ{x∈X|n∈N, inn(x, n, z)≦0} とおくと [y, y]≦y となります。 (これはリー代数 L の部分ベクトル空間 H に対して K={x∈L|[…[x, H]…H]=0 (何回かで0になる)} が部分代数になるという意味になります。)