コラム 超限帰納法
自然数に関する命題、すなわち自然数で添字付けられた命題の集まりを証明するために役立つ数学的帰納法の拡張として、順序数で添字付けられた命題の集まりを証明するために役立つ「超限帰納法」を紹介します。
| 定理1（超限帰納法） |
| \( N \subset \textrm{Ord} \)を部分クラスとし、\( \Phi(x) \)を量化の有界な論理式とし、以下の２条件を満たすとする。 |
| (1) 任意の\( n \in N \)と任意の\( m \in n \)に対し、\( m \in N \)が成り立つ。 |
| (2) 任意の\( n \in N \)に対し、任意の\( m \in n \)に対し\( \Phi(m) \)が成り立つならば\( \Phi(n) \)が成り立つ。 |
| この時、任意の\( n \in N \)に対し\( \Phi(n) \)が成り立つ。 |
証明
\( \{ n \in N \mid \Phi(n) \} \)を\( N' \)と置く。\( N = N' \)であることを背理法で示す。\( N' \subsetneq N \)と仮定する。この時\( N \setminus N' \neq \emptyset \)である。\( \textrm{Ord} \)の強整列性により\( \textrm{Ord} \)に対する強整列性の条件(5)が保証されることから、ある\( m \in N \setminus N' \)が存在して任意の\( n \in N \setminus N' \)に対し\( m = n \)または\( m \in n \)である。
任意の\( m' \in m \)に対し\( \Phi(m) \)が成り立つことを示す。\( m' \in m \)とする。三分律から、\( m \neq m' \)かつ\( m \notin m' \)である。従って、\( m \)の取り方から\( m' \notin N \setminus N' \)である。\( m' \in m \in N \setminus N' \subset N \)より、\( N \)の仮定から\( m' \in N \)である。従って、\( m' \in N' \)である。すなわち\( \Phi(m') \)が成り立つ。
\( \Phi \)についての仮定から、\( \Phi(m) \)が成り立つ。これは\( m \in N \setminus N' \)に反し、矛盾する。以上から、\( N = N' \)である。すなわち、任意の\( n \in N \)に対し\( \Phi(n) \)が成り立つ。
超限帰納法の条件(1)は強整列性の条件(1)に他なりません。従って任意の順序数は\( \textrm{Ord} \)の部分クラスとして超限帰納法の条件(1)を満たしますし、\( \textrm{Ord} \)の強整列性から\( \textrm{Ord} \)も自身の部分クラスとして超限帰納法の条件(1)を満たします。\( \mathbb{N} \)が順序数であることから、特に\( N \)として\( \mathbb{N} \)を取ることが出来ます。その場合の超限帰納法は、通常の数学的帰納法と見た目が違うだけでほぼ同じものとなります*1。\( 0{} \)も順序数ですが、\( N \)として\( 0{} \)を取った場合の超限帰納法は\( \forall n \in \emptyset, \Phi(n) \)という自明な論理式が成り立つということしか帰結しません。
数学的帰納法には漸化式の再定式化に応用があるということを予告しましたが、超限帰納法にも同様の応用があります。数学的帰納法では自然数しか扱えなかったので、\( \mathbb{N} \)で添字付けられた数列や点列や集合の列しか漸化式で扱えませんでしたが、超限帰納法においてはより広い順序数を扱えるため、例えば\( \textrm{Ord} \)で添字付けられた集合の列を漸化式で扱えるようになるという点で優れています。漸化式についてはやはり「写像」という概念を導入した後の方が簡便に説明できるため、まだ扱わないようにします。
- 自然数の定義へ戻る。