数学的帰納法

数学的帰納法は、ある命題があらゆる自然数に対して真であること、つまり無限に多いケースがすべて成り立つことを証明する方法です  。これは、まず単純なケースを証明し、次に、あるケースに対して主張が真であると仮定すると、次のケースも真であることを示すことによって行われます。ドミノ倒しやはしご登りなどの非公式の比喩は、この手法を説明するのに役立ちます。 ${\displaystyle P(n)}$ ${\displaystyle n}$${\displaystyle P(0),P(1),P(2),P(3),\dots }$

数学的帰納法は、はしごの一番下の段（基底）に登ることができ、各段から次の段（ステップ）に登ることができることを証明することによって、はしごを好きなだけ高く登ることができることを証明します。

— 具体的な数学、3ページの余白。

帰納法による証明は、 2つのケースから成ります。最初の基本ケースでは、他のケースに関する知識を前提とせずにに対するステートメントを証明します。2 番目のケースである帰納法のステップでは、任意のケース に対してステートメントが成り立つ場合、次のケース に対しても必ず成り立つことを証明します。この 2 つのステップにより、すべての自然数 に対してステートメントが成り立つことが証明されます。基本ケースは必ずしも から始まるわけではなく、多くの場合 から始まり、場合によっては任意の固定された自然数 で始まり、すべての自然数 に対してステートメントが真実であることを確立します。 ${\displaystyle n=0}$${\displaystyle n=k}$${\displaystyle n=k+1}$${\displaystyle n}$${\displaystyle n=0}$${\displaystyle n=1}$${\displaystyle n=N}$${\displaystyle n\geq N}$

この方法は、木のようなより一般的なwell-founded構造についての記述を証明するために拡張することができる。この一般化は構造的帰納法として知られ、数理論理学やコンピュータサイエンスで使用されている。この拡張された意味での数学的帰納法は、再帰と密接に関連している。数学的帰納法は、形式的な証明で使用される推論規則であり、コンピュータプログラムの正当性証明のほとんどの基礎となっている。 ^[3]

その名前にもかかわらず、数学的帰納法は、多くの事例を検討して可能性のある結論を導く哲学で用いられる帰納的推論とは根本的に異なる。数学的手法では、一般命題を証明するために無限に多くの事例を検討するが、これは無限に多くの値を取ることができる変数を含む有限の演繹的推論の連鎖によって行われる。その結果は命題の厳密な証明であり、その確率の主張ではない。^[4] ${\displaystyle n}$

紀元前370年、プラトンの『パルメニデス』には暗黙の帰納的証明の初期の例の痕跡が含まれていた可能性があるが^[5]、数学的帰納法による最古の暗黙の証明は紀元1000年頃にアル・カラジによって書かれたもので、彼はそれを算術数列に適用して二項定理とパスカルの三角形の性質を証明した。原著は失われたが、後にアル・サマワル・アル・マグリビが紀元1150年頃に書いた論文『アル・バヒル・フィル・ジャブル（代数学の天才）』で言及された。 ^{[6] [7] [8]}

カッツは数学の歴史の中でこう述べている。

アル=カラジーが導入し、アル=サマワルらが継承したもう 1 つの重要なアイデアは、特定の等差数列を扱うための帰納的議論である。したがって、アル=カラジーは、そのような議論を使用して、アリヤバタがすでに知っていた立方整数の和に関する結果を証明した [...] しかし、アル=カラジーは、任意のnに対する一般的な結果を述べなかった。彼は、特定の整数 10 に対する定理を述べた [...] それでも、彼の証明は、他の任意の整数に拡張できるように設計されていたことは明らかである。 [...] アル=カラジーの議論には、本質的に、帰納的議論による現代の議論の 2 つの基本要素、つまりn = 1 (1 = 1 ³ )の場合の命題の真偽と、 n = k - 1の真偽からn = kの真偽を導くことが含まれています。もちろん、この 2 番目の要素は明示的ではありません。ある意味では、アル=カラジーの議論は逆であるためです。つまり、彼はn = 10から始めて、上に向かって進むのではなく、1まで下がっていく。それにもかかわらず、アル・ファクリにおける彼の議論は、立方整数の和の公式の現存する最古の証明である。^[9]

インドでは、数学的帰納法による初期の暗黙の証明は、バースカラの「巡回法」に現れている。^[10]

しかしながら、これらの古代の数学者の誰も、帰納法の仮説を明示的に述べてはいませんでした。別の類似した事例（ヴァッカの記述とは反対に、フロイデンタールが注意深く示したように）^[11]は、フランチェスコ・マウロリコの著書『算術二部作』（1575年）で、彼はこの手法を使用して、最初のn 個の奇数 の和がn ²であることを証明しました。

帰納法を厳密に使用した最初の人物は、ゲルソニデス（1288-1344）です。 ^{[12] [13]}帰納法の原理を初めて明示的に定式化したのは、パスカルの著書「三角形の算術理論」（1665年）です。もう一人のフランス人、フェルマーは、関連する原理である無限降下法による間接証明を多用しました。

帰納法の仮説はスイスのヤコブ・ベルヌーイによっても採用され、それ以来よく知られるようになりました。この原理の現代的な正式な扱いは、19世紀になってジョージ・ブール^[14] 、オーガスタス・ド・モルガン、チャールズ・サンダース・パース^[15]、 [ ^16]、 ジュゼッペ・ペアノ、リチャード・デデキント^[10]によって初めて行われました。

数学的帰納法の最も単純かつ一般的な形式は、自然数 n (つまり、整数n ≥ 0または 1)を含むステートメントがnのすべての値に対して成り立つことを推論することです。証明は 2 つのステップで構成されます。

1. の基本ケース（または初期ケース）：ステートメントが 0 または 1 に対して成り立つことを証明します。
2. の帰納法ステップ(または帰納的ステップ、ステップケース): すべてのnnに対してステートメントが成り立つ場合は、 n + 1に対しても成り立つ。言い換えると、任意の自然数nに対してステートメントが成り立つと仮定し、 n + 1に対してステートメントが成り立つことを証明します。

帰納法のステップにおける、特定のnに対して文が成り立つという仮説は、帰納仮説または帰納的仮説と呼ばれます。帰納法のステップを証明するには、nに対して帰納仮説を仮定し、この仮定を使用してn + 1に対して文が成り立つことを証明します。

自然数を 0 から始まるように定義することを好む著者は、基本ケースでその値を使用します。自然数を 1 から始まるように定義する著者は、その値を使用します。

数学的帰納法は、すべての自然数nに対して次の命題P ( n ) を証明するために使用できます。 $${\displaystyle P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.}$$

これは、与えられた数以下の自然数の合計の一般的な公式を述べています。実際は、、、などの ステートメントの無限のシーケンスです。${\displaystyle 0={\tfrac {(0)(0+1)}{2}}}$${\displaystyle 0+1={\tfrac {(1)(1+1)}{2}}}$${\displaystyle 0+1+2={\tfrac {(2)(2+1)}{2}}}$

命題。すべての に対して、${\displaystyle n\in \mathbb {N} }$${\displaystyle 0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.}$

証明。P ( n )を次の文とします。nに関する帰納法によって証明します。 ${\displaystyle 0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.}$

基本ケース:最小の自然数n = 0に対してこのステートメントが成り立つことを示します。

P (0)は明らかに真である:${\displaystyle 0={\tfrac {0(0+1)}{2}}\,.}$

帰納法のステップ:すべてのk ≥ 0に対して、P ( k )が成り立つならP ( k + 1)も成り立つことを示します。

特定のkに対して、 n = kという唯一のケースが成り立つという帰納法の仮説を仮定すると、P ( k ) が真であることを意味します。つまり 、次のようになります。 $${\displaystyle 0+1+\cdots +k={\frac {k(k+1)}{2}}.}$$$${\displaystyle (0+1+2+\cdots +k)+(k+1)={\frac {k(k+1)}{2}}+(k+1).}$$

代数的には、右辺は次のように簡略化されます。 $${\displaystyle {\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}.\end{aligned}}}$$

左辺と右辺を等しくすると、次のことが推論されます。つまり、ステートメントP ( k + 1)も真であり、帰納法のステップが確立されます。 $${\displaystyle 0+1+2+\cdots +k+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.}$$

結論:基本ケースと帰納法の両方が真であることが証明されたので、数学的帰納法によって命題P ( n ) はすべての自然数nに対して成り立つ。QED

帰納法は不等式を証明するためによく使われます。例として、任意の実数と自然数に対して であることを証明します。 ${\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}$ ${\displaystyle x}$${\displaystyle n}$

一見すると、任意の実数に対するより一般的なバージョンは、帰納法なしで証明できるように見えるかもしれません。しかし、この事例は、の非整数値に対しては偽である可能性があることを示しています。これは、 の自然な値に対して特にステートメントを調べることを示唆しており、帰納法が最も簡単なツールです。 ${\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}$${\displaystyle n,x}$${\textstyle n={\frac {1}{2}},\,x=\pi }$${\displaystyle n}$${\displaystyle n}$

命題。任意のおよび、。 ${\displaystyle x\in \mathbb {R} }$${\displaystyle n\in \mathbb {N} }$${\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}$

証明。任意の実数 を固定し、 を文 とします。 について を誘導します。 ${\displaystyle x}$${\displaystyle P(n)}$${\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}$${\displaystyle n}$

基本ケース:計算により が検証されます。 ${\displaystyle \left|\sin 0x\right|=0\leq 0=0\left|\sin x\right|}$${\displaystyle P(0)}$

帰納法のステップ:任意の自然数 に対する含意 を示します。帰納法の仮説を仮定します。与えられた値 に対して、唯一のケースが真です。角度の加算公式と三角不等式を使用すると、次のことが推論されます。 ${\displaystyle P(k)\implies P(k+1)}$${\displaystyle k}$${\displaystyle n=k\geq 0}$${\displaystyle P(k)}$$${\displaystyle {\begin{aligned}\left|\sin(k+1)x\right|&=\left|\sin kx\cos x+\sin x\cos kx\right|&&{\text{(angle addition)}}\\&\leq \left|\sin kx\cos x\right|+\left|\sin x\,\cos kx\right|&&{\text{(triangle inequality)}}\\&=\left|\sin kx\right|\left|\cos x\right|+\left|\sin x\right|\left|\cos kx\right|\\&\leq \left|\sin kx\right|+\left|\sin x\right|&&(\left|\cos t\right|\leq 1)\\&\leq k\left|\sin x\right|+\left|\sin x\right|&&{\text{(induction hypothesis}})\\&=(k+1)\left|\sin x\right|.\end{aligned}}}$$

左端と右端の量の間の不等式は、が真であることを示しており、これにより帰納法のステップが完了します。 ${\displaystyle P(k+1)}$

結論：この命題はすべての自然数QED に対して成り立つ${\displaystyle P(n)}$${\displaystyle n.}$ 

実際には、帰納法による証明は、証明する性質の正確な性質に応じて、異なる構造になることがよくあります。帰納法のすべてのバリエーションは、超限帰納法の特殊なケースです。以下を参照してください。

すべての自然数に対してではなく、特定の数b以上のすべての数nに対してのみ、ある命題を証明したい場合、帰納法による証明は次のようになります。

1. n = bのときにステートメントが成立することを示します。
2. 任意の数n ≥ bに対してこの文が成り立つ場合、同じ文がn + 1に対しても成り立つことを示します。

これは、例えば、n ≥ 3の場合に2 ⁿ ≥ n + 5 であることを示すために使用できます。

このようにして、ある命題P ( n )がすべてのn≥1 、あるいはすべてのn≥ −5に対して成り立つことを証明することができる。この形式の数学的帰納法は、実際には前の形式の特殊なケースである。なぜなら、証明すべき命題がP ( n )である場合、これら2つの規則でそれを証明することは、帰納法の基本ケース0ですべての自然数nに対してP ( n + b )を証明することと同等であるからである。^[17]

4 ドルと 5 ドルのコインが無限にあると仮定します。12ドル以上の任意のドルの総額は、そのようなコインの組み合わせで形成できることは、帰納法で証明できます。S ( k )は、 「4 ドルと 5 ドルのコインの組み合わせでkドルを形成できる」というステートメントを表します。S ( k ) がすべてのk ≥ 12に対して真であることは、次のようにkに関する帰納法で証明できます。

基本ケース: k = 12の場合にS ( k )が成り立つことを示すのは簡単です。4 ドル硬貨を 3 枚用意します。

帰納法のステップ: S ( k ) がk ≥ 12の値に対して成り立つこと(帰納法の仮説)を前提として、 S ( k + 1)も成り立つことを証明してください。S ( k ) が任意のk ≥ 12に対して真であると仮定します。 kドルに対して少なくとも 1 枚の 4 ドル硬貨を含む解が存在する場合、それを 1 枚の 5 ドル硬貨に置き換えてk + 1ドルにします。そうでない場合、5 ドル硬貨のみが使用される場合、k は5 の倍数であるため少なくとも 15 になりますが、その場合、3 枚の 5 ドル硬貨を 4 枚の 4 ドル硬貨に置き換えてk + 1ドルにすることができます。いずれの場合も、S ( k + 1)は真です。

したがって、帰納法の原理により、S ( k )はすべてのk≥12に対して成立し、証明は完了です。

この例では、S ( k ) はにも当てはまりますが、上記の証明は、最小額の12ドルをそれより低い値mに置き換えるように変更することはできません。m = 11の場合、基本ケースは実際には偽です。m = 10の場合、誘導ステップの 2 番目のケース (5 ドル硬貨 3 枚と 4 ドル硬貨 4 枚を置き換える) は機能しません。さらに低いmの場合はなおさらです。 ${\textstyle k\in \{4,5,8,9,10\}}$

2 つの自然数nとm を含む命題を、帰納的過程を繰り返すことによって証明することが望ましい場合があります。つまり、 nの基本ケースと帰納的過程を証明し、そのそれぞれにおいてmの基本ケースと帰納的過程を証明します。たとえば、自然数の加算に伴う可換性の証明を参照してください。3 つ以上のカウンタを含むより複雑な議論も可能です。

無限降下法は、ピエール・ド・フェルマーが使用した数学的帰納法の一種です。この方法は、何らかの命題Q ( n ) がすべての自然数nに対して偽であることを示すために使用されます。従来の形式では、Q ( n )が何らかの自然数nに対して真である場合、それが厳密に小さい何らかの自然数mに対しても成り立つことを示します。自然数の無限減少列は存在しないため、この状況は不可能であり、したがって (背理法によって) Q ( n ) が任意のnに対して真になることはできないことが示されます。

この方法の妥当性は、通常の数学的帰納法の原理から検証できます。「Q ( m ) はn以下のすべての自然数mに対して偽である」と定義された命題P ( n )に数学的帰納法を使用すると、P ( n ) はすべてのnに対して成り立ち、これはQ ( n ) がすべての自然数nに対して偽であることを意味します。

もし、性質Pがn以下のすべての自然数に対して成り立つことを証明したい場合、Pが以下の条件を満たすことを証明すれば十分である: ^[18]

1. Pは0の場合に成立し、
2. n未満の任意の自然数xに対して、xに対してP が成り立つ場合、x + 1に対してP が成り立つ。

数学的帰納法による最も一般的な証明は、帰納法の段階で次のことを証明する必要がある。 $${\displaystyle \forall k\,(P(k)\to P(k+1))}$$

すると、帰納原理は、P (0)からP ( n )に到達するこのステップのn 回の適用を「自動化」します。各ステップは、その数の前の数に関する何かから、その数に関する何かを証明するため、これは「前の数の帰納」と呼ぶことができます。

計算複雑性における興味深い変種として「前置帰納法」があり、帰納法のステップで次の命題を証明する。 または同等の証明として $${\displaystyle \forall k\,(P(k)\to P(2k)\land P(2k+1))}$$$${\displaystyle \forall k\,\left(P\!\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)}$$

帰納原理は、P (0)からP ( n )に至るこの推論のlog ₂  n 回の適用を「自動化」します。実際、これは「プレフィックス帰納」と呼ばれます。これは、各ステップで、その数値の「プレフィックス」 (バイナリ表現の下位ビットを切り捨てて形成される) に関する何かから、数値に関する何かを証明するためです。これは、そのバイナリ表現の長さに対する従来の帰納法の適用と見ることもできます。

従来の先行者帰納法が計算的にnステップのループとして解釈される場合、プレフィックス帰納法は log -nステップのループに対応します。そのため、プレフィックス帰納法を使用した証明は、先行者帰納法を使用した証明よりも「より実現可能に構築的」です。

先行子帰納法は、同じ文で前置子帰納法を簡単にシミュレートできます。前置子帰納法は先行子帰納法をシミュレートできますが、文の構文がより複雑になる（制限された 全称量指定子を追加する）という犠牲を払ってのみ実行できます。そのため、前置子帰納法と多項式時間計算を関連付ける興味深い結果は、制限のない量指定子を完全に排除し、文で許可される制限された全称量指定子と存在量指定子の交互使用を制限することに依存します。 ^[19]

この考えをさらに一歩進めることができます。 つまり、 P (0)からP ( n )に到達するまでのこの推論のlog log n回の適用 を、帰納原理が「自動化」することを証明する必要があります。この形式の帰納法は、同様に、対数時間並列計算の研究に使用されています。^[要出典]$${\displaystyle \forall k\,\left(P\!\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)}$$

完全帰納法、値の過程帰納法、または強い帰納法と呼ばれる別の変種（これに対して、帰納法の基本形式は弱い帰納法と呼ばれることもある）では、より強い仮説を使用して帰納法のステップの証明が容易になります。未満のすべての自然数に対して が成り立つという仮定の下でステートメントを証明します。対照的に、基本形式では のみが仮定されます。「強い帰納法」という名前は、この方法が「弱い帰納法」よりも多くのことを証明できることを意味するのではなく、帰納法のステップで使用されるより強い仮説を指しているだけです。 ${\displaystyle P(m+1)}$${\displaystyle P(n)}$${\displaystyle n}$${\displaystyle m+1}$${\displaystyle P(m)}$

実際、以下で説明するように、2 つの方法は実際には同等であることが示されます。この完全な帰納法の形式では、基本ケース を証明する必要があり、一般的な議論を適用する前に、フィボナッチ数の例のように、追加の基本ケース を証明する必要がある場合もあります。 ${\displaystyle P(0)}$${\displaystyle P(1)}$ ${\displaystyle F_{n}}$

今説明した形式では基本ケースを証明する必要がありますが、（より小さいすべての について を仮定して）すべての についてを証明できる場合、これは不要です。これは、後述するように超限帰納法の特殊なケースですが、通常の帰納法と同等ではなくなります。この形式では、基本ケースは の場合に包含され、 は他の仮定なしに証明されます。この場合は個別に処理する必要がある場合がありますが、同じ議論がおよびに適用され、証明がより単純でエレガントになる場合があります。ただし、この方法では、 の証明がを暗黙的に仮定しないようにすることが重要です。たとえば、「任意の を選択する」と言うことや、 m 個の要素の集合に個の要素があると仮定するなどです。 ${\displaystyle P(m)}$${\displaystyle P(n)}$${\displaystyle n}$${\displaystyle m\geq 0}$${\displaystyle m=0}$${\displaystyle P(0)}$${\displaystyle P(n)}$${\displaystyle m=0}$${\displaystyle m>0}$${\displaystyle P(m)}$${\displaystyle m>0}$${\displaystyle n<m}$

完全帰納法は、一方の方法による証明を他方の証明に変換できるという意味で、上で説明した通常の数学的帰納法と同等である。完全帰納法による の証明があるとしよう。次に、より強い帰納的仮説を仮定することで、この証明を通常の帰納的証明に変換できる。 を「となるすべての に対して成り立つ」という文とすると、これが通常の帰納法の帰納的仮説になる。次に、のみを仮定してに対しておよび を示すことができ、 がを意味することを示すことができる。^[20]${\displaystyle P(n)}$${\displaystyle Q(n)}$${\displaystyle P(m)}$${\displaystyle m}$${\displaystyle 0\leq m\leq n}$${\displaystyle Q(0)}$${\displaystyle Q(n+1)}$${\displaystyle n\in \mathbb {N} }$${\displaystyle Q(n)}$${\displaystyle Q(n)}$${\displaystyle P(n)}$

一方、が通常の帰納法で証明されていた場合、その証明は事実上完全な帰納法による証明になります。 は基本ケースで何の仮定も使わずに証明され、 は帰納法のステップで証明されます。このステップでは、それ以前のすべてのケースを仮定して、 ケースのみを使用する必要があります。 ${\displaystyle P(n)}$${\displaystyle P(0)}$${\displaystyle P(n+1)}$${\displaystyle P(n)}$

完全帰納法は、各帰納ステップで帰納的仮説の複数のインスタンスが必要な場合に最も便利です。たとえば、完全帰納法を使用して、 が n番目のフィボナッチ数であり 、(黄金比) および が多項式の根であることを示すことができます。各 に対して であるという事実を使用することで、と の両方に対して既に成り立っていると仮定すれば、 に対する直接計算によって上記の恒等式を検証できます。証明を完了するには、との 2 つの基本ケースで恒等式を検証する必要があります。 $${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}}$$${\displaystyle F_{n}}$${\textstyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}$${\textstyle \psi ={\frac {1}{2}}(1-{\sqrt {5}})}$ ${\displaystyle x^{2}-x-1}$${\displaystyle F_{n+2}=F_{n+1}+F_{n}}$${\displaystyle n\in \mathbb {N} }$${\textstyle F_{n+2}}$${\textstyle F_{n+1}}$${\textstyle F_{n}}$${\displaystyle n=0}$${\textstyle n=1}$

完全な帰納法による別の証明では、より小さいすべての場合にステートメントが成り立つという仮説をより徹底的に使用します。算術の基本定理の「存在」の部分である「 1 より大きいすべての自然数は (1 つ以上の)素数の積である」というステートメントを考えてみましょう。帰納法のステップを証明するための帰納法の仮説は、 が与えられた場合、より小さいすべての場合にステートメントが成り立つというものです。が素数の場合、それは確かに素数の積であり、そうでない場合は、定義によりそれは積です。 、ただし、どちらの因数も 1 に等しくないため、どちらも に等しくなく、したがって両方とも 1 より大きく より小さくなります。これで帰納法の仮説がとに適用され、それぞれが素数の積になります。したがって、 は素数の積の積であり、したがって拡張すると 自体も素数の積です。 ${\displaystyle n}$${\displaystyle n>1}$${\displaystyle n>1}$${\displaystyle m}$${\displaystyle m=n_{1}n_{2}}$${\displaystyle m}$${\displaystyle m}$${\displaystyle n_{1}}$${\displaystyle n_{2}}$${\displaystyle m}$

今回は強い帰納法を使って、上記と同じ例を証明してみます。主張は同じままです。 $${\displaystyle S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b}$$

ただし、拡張された基本ケースから始めて、証明の構造と仮定に若干の違いがあります。

証拠。

基本ケース:が成り立つことを示します。 ${\displaystyle S(k)}$${\displaystyle k=12,13,14,15}$$${\displaystyle {\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}}$$

基本ケースは成立します。

帰納法のステップ:ある が与えられたとき、のすべての に対して が成り立つと仮定します。が成り立つことを証明します。 ${\displaystyle j>15}$${\displaystyle S(m)}$${\displaystyle m}$${\displaystyle 12\leq m<j}$${\displaystyle S(j)}$

を選択し、 を観察すると、帰納的仮説により が成り立つことが示される。つまり、 の合計はと1 ドル硬貨の組み合わせで形成できる。次に、その組み合わせに 1 ドル硬貨を単純に追加すると、 の合計が得られる。つまり、が成り立つ^[21] QED ${\displaystyle m=j-4}$${\displaystyle 15<j\implies 12\leq j-4<j}$${\displaystyle S(j-4)}$${\displaystyle j-4}$${\displaystyle 4}$${\displaystyle 5}$${\displaystyle 4}$${\displaystyle j}$${\displaystyle S(j)}$

時には、 に対する命題が に対して有効であることを前提として、 に対する命題を証明し、逆方向に演繹する方が便利なこともあります。しかし、 の命題が単一の数に対して有効であることを証明するだけでは、基本ケースを確立するのに十分ではありません。その代わりに、自然数の無限の部分集合に対して命題を証明する必要があります。たとえば、オーギュスタン＝ルイ・コーシーは、最初に順方向（通常の）帰納法を使用して、 2 のすべての累乗に対する算術平均と幾何平均の不等式を証明し 、次に逆方向帰納法を使用して、すべての自然数に対してそれを示しました。^{[22] [23]}${\displaystyle n-1}$${\displaystyle n}$

帰納法のステップはnのすべての値に対して証明されなければならない。これを説明するために、ジョエル・E・コーエンは、すべての馬が同じ色であることを数学的帰納法で証明することを目的とする次の議論を提案した。^[24]

基本ケース:馬が1 頭のみのセットでは、色は 1 つだけです。

帰納法のステップ:帰納法の仮説として、どの馬の集合にも 1 つの色しかないと仮定します。次に、任意の馬の集合を見てみましょう。番号を付けます。集合とを考えます。それぞれは馬の集合だけなので、それぞれには 1 つの色しかありません。しかし、2 つの集合は重なり合っているため、すべての馬に共通する色は 1 つだけです。 ${\displaystyle n}$${\displaystyle n+1}$${\displaystyle 1,2,3,\dotsc ,n,n+1}$${\textstyle \left\{1,2,3,\dotsc ,n\right\}}$${\textstyle \left\{2,3,4,\dotsc ,n+1\right\}}$${\displaystyle n}$${\displaystyle n+1}$

基本ケースは自明であり、すべてのケース で帰納法のステップは正しいです。ただし、帰納法のステップで使用される議論は については正しくありません。これは、 「2 つのセットが重なり合っている」というステートメントが および については偽であるためです。 ${\displaystyle n=1}$${\displaystyle n>1}$${\displaystyle n+1=2}$${\textstyle \left\{1\right\}}$${\textstyle \left\{2\right\}}$

第二階述語論理では、「帰納法の公理」を次のように記述することができます。 ここで、P (·) は1 つの自然数を含む述語の変数であり、kとn は自然数の変数です。 $${\displaystyle \forall P\,{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n\,{\bigl (}P(n){\bigr )}{\Bigr )},}$$

言葉で言えば、基本ケースP (0)と帰納法のステップ (つまり、帰納法の仮説P ( k ) はP ( k + 1)を意味する) を組み合わせると、任意の自然数nに対してP ( n )が成り立つことを意味します。帰納法の公理は、基本ケースと帰納法のステップから任意の自然数nに対してP ( n ) が成り立つと推論することの妥当性を主張します。

公理の最初の量指定子は、個々の数値ではなく述語の範囲をとっています。これは二階の量指定子であり、つまりこの公理は二階論理で述べられているということです。一階論理で算術帰納法を公理化するには、可能な述語ごとに別々の公理を含む公理スキーマが必要です。この問題については、 記事「ペアノ公理」にさらに詳しく記載されています。

自然数の構造帰納法の公理はペアノによって初めて定式化され、彼はそれを次の 4 つの他の公理とともに自然数を指定するために使用しました。

1. 0は自然数です。
2. あらゆる自然数の後継関数s は自然数( s ( x ) = x + 1)を生成します。
3. 後続関数は単射です。
4. 0 はsの範囲内ではありません。

1 階の ZFC 集合論では、述語の量化は許可されていませんが、集合の量化によって帰納法を表現することはできます。A は、命題を表し、その命題が成り立つ自然数を含む集合として読むことができます。これは公理ではなく定理であり、ZFC 集合論の言語では自然数はペアノと同様に公理によって定義されます。無限公理と仕様公理スキーマを使用した自然数の構築を参照してください。 $${\displaystyle \forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}}$$

完全帰納法の原理の 1 つのバリエーションは、任意の整集合、つまり無限下降チェーンを含まない非反射関係< を持つ集合 の要素に関するステートメントに対して一般化できます。順序数を表すすべての集合は整集合であり、自然数の集合もその 1 つです。

整集合に適用すると、超限帰納法は1つのステップとして定式化できます。命題P ( n )が各順序数に対して成り立つことを証明するには、次のようになります。

1. 各順序数nについて、すべてのm < nに対してP ( m )が成り立つ場合、P ( n )も成り立つことを示します。

この形式の帰納法は、順序数集合（順序が整っており、したがって整基礎クラスを形成する）に適用される場合、超限帰納法と呼ばれます。これは、集合論、位相幾何学、およびその他の分野 における重要な証明手法です。

超限帰納法による証明では、通常、次の 3 つのケースが区別されます。

1. n が最小の要素である場合、つまりnより小さい要素が存在しないとき。
2. n に直接の先行要素がある場合、つまりnより小さい要素の集合に最大の要素がある場合。
3. n に直接の先行順序がない場合、つまりnはいわゆる極限順序数です。

厳密に言えば、超限帰納法では基本ケースを証明する必要はありません。なぜなら、それは「 P がすべてのn < mで真であれば、P はmで真である」という命題の空虚な特殊ケースだからです。反例となり得るn < mの値が存在しないために、まさに空虚に真なのです。したがって、特殊ケースは一般ケースの特殊ケースです。

数学的帰納法の原理は、通常、自然数の公理として述べられます。ペアノの公理を参照してください。これは、他のペアノの公理の文脈では、 整列原理よりも厳密に強力です。次のことを想定します。

• 三分法公理: 任意の自然数nとmに対して、m がn未満でない場合に限り、 n はm以下である。
• 任意の自然数nに対して、n + 1はnより大きい。
• 任意の自然数nについて、 nとn + 1の間には自然数は存在しません。
• いかなる自然数もゼロより小さいものではありません。

上記の公理が与えられた場合、帰納法は整列原理を意味することが証明できます。次の証明では、完全帰納法と 1 番目と 4 番目の公理を使用します。

証明。最小元を持たない、空でない自然数の集合Sが存在するとします。 nがSに含まれないという主張をP ( n )とします。するとP (0) は真になります。なぜなら、これが偽であれば、 0 はSの最小元だからです。さらに、nを自然数とし、n + 1未満のすべての自然数mに対してP ( m )が真であるとします。すると、P ( n + 1)が偽であれば、 n + 1 はSに含まれるため、 Sの最小元であるため、矛盾が生じます。したがって、P ( n + 1)は真です。したがって、完全帰納原理により、P ( n ) はすべての自然数nに対して成り立ち、S は空であり、矛盾が生じます。 QED

一方、図に示す集合 は、辞書式順序によって整列しています^{[25] : 35lf}。さらに、帰納法公理を除いて、これはすべてのペアノ公理を満たします。ここで、ペアノ定数 0 はペア (0, 0) として解釈され、ペアノの後継関数は、すべてのおよびに対して、 succ( x、n ) = ( x、n + 1)によってペア上で定義されます。帰納法公理に違反する例として、述語P ( x、n ) を、ある および に対して、 ( x、n ) = (0, 0)または( x、n ) = succ( y、m )と定義します。すると、基本ケースP (0, 0)は自明に真となり、帰納法ステップも自明になります。つまり、 P ( x、n )であれば、P (succ( x、n ))となります。しかし、P (1,0)は偽であるため、セット内のすべてのペアに対してPは真ではありません。 ${\displaystyle \{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}}$${\displaystyle x\in \{0,1\}}$${\displaystyle n\in \mathbb {N} }$${\displaystyle y\in \{0,1\}}$${\displaystyle m\in \mathbb {N} }$

ペアノの公理と帰納原理は自然数を一意にモデル化する。帰納原理を整列原理に置き換えることで、すべての公理を満たすよりエキゾチックなモデルが可能になる。^[25]

いくつかの書籍^[25]や文献では、整列原理は帰納公理と同等であると誤って記載されている。他のペアノ公理の文脈ではそうではないが、他の公理の文脈ではそれらは同等である。^[25]具体的には、整列原理は、上記の最初の2つの公理の文脈では帰納公理を意味し、

• すべての自然数は、何らかの自然数nに対して0 またはn + 1 のいずれかです。

多くの誤った証明に共通する間違いは、n − 1が一意かつ明確に定義された自然数であると仮定することであるが、これは他のペアノ公理では示されていない性質である。^[25]

• 誘導パズル
• 徹底的な検証