コラム 数学的帰納法
自然数という概念を公理的集合論の中で再定式化したことにより、公理的集合論における命題に対して数学的帰納法を行うことが出来るようになります。
| 定理1（数学的帰納法） |
| \( \Phi(x) \)を量化の有界な論理式とし、以下の２条件を満たすとする。 |
| (1) \( \Phi(0) \)が成り立つ。 |
| (2) 任意の\( n \in \mathbb{N} \)に対し、\( \Phi(n) \)が成り立つならば\( \Phi(n \cup \{ n \}) \)が成り立つ。 |
| この時、任意の\( n \in \mathbb{N} \)に対し\( \Phi(n) \)が成り立つ。 |
証明
\( \mathbb{N} \)の部分集合\( \{n \in \mathbb{N} \mid \Phi(n) \} \)を\( N \)と置く。\( \Phi \)の仮定より、\( 0 \in N \)かつ任意の\( n \in N \)に対し\( n \cup \{ n \} \in N \)が成り立つ。\( \mathbb{N} \)はその定義から、\( 0 \in X \)かつ任意の\( n \in X \)に対し\( n \cup \{ n \} \in X \)を満たす任意の集合\( X \)の部分集合であるので、\( \mathbb{N} \subset N \)である。\( N \subset \mathbb{N} \)より、\( N = \mathbb{N} \)である。従って、任意の\( n \in \mathbb{N} \)に対し\( \Phi(n) \)が成り立つ。
ここで、量化の有界な論理式とは原子式に演算子\( \wedge \)、\( \vee \)、\( \neg \)、\( \to \)と有界な量化子\( \forall x \in A \)、\( \exists x \in A \)（ただし\( x \)は変項で\( A \)は項）を繰り返し適用することで得られるもののことでした。有界な量化子で束縛された変項はその定義から集合のみを値に取ることが出来、逆に集合のみを値に取る変項は集合全体のクラス\( V \)を用いて表される有界な量化子\( \forall x \in V \)や\( \exists x \in V \)で束縛されていることになるので、量化の有界な論理式とは単に量化された全ての変項が集合のみを値に取る論理式のことに他なりません。
特に、クラスを用いない流儀における公理的集合論の論理式、すなわち集合のみを項の値として許容した論理式は、自然な方法でクラスに関する論理式とみなすことで自動的に量化の有界な論理式として翻訳されます。従って、集合のみを項の値として許容した論理式に対しては常に数学的帰納法が適用可能であるということになります。
数学的帰納法は非常に強力な証明手法となります。何故ならば、ペアノ算術という自然数の理論において数学的帰納法が自然数というものを特徴付ける情報の１つに組み込まれていたように、公理的集合論においてもある意味自然数というものを特徴付ける性質だからです。自然数に特有の性質（つまり自然数より広い範囲の集合には必ずしも成り立たないような性質）を証明する際には当然自然数の定義なり特徴なりを使う必要がありますが、そういった局面では自然数の特徴が詰まった数学的帰納法は役に立つことが多いです。
数学的帰納法の１つの応用として、「漸化式」を公理的集合論の中で再定式化することが出来ます。漸化式の汎用性は説明するまでもないかもしれませんが、例えば自然数の足し算や掛け算を公理的集合論の中で厳密に定義する際にも漸化式は役に立ちます。ただし、漸化式の定式化は「写像」という概念を導入した後の方が簡便であるため、まだ扱わないことにします。