超限帰納法の原理

超限帰納法の原理

全順序集合\(\left( A,\leq \right) \)が与えられているものとします。つまり、\(\leq \)は\(A\)上に定義された二項関係であり、反射律、反対称律、推移律、そして完備律を満たすということ、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq
x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq
z\right) \Rightarrow x\leq z\right] \\
&&\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{eqnarray*}が成り立つということです。

全順序集合\(A\)の非空な部分集合\(B\)が与えられたとき、その最小元\(\min B\)は以下の条件\begin{equation*}\forall x\in B:\min B\leq x
\end{equation*}を満たす\(B\)の要素として定義されます。

全順序集合\(A\)が整列集合であることとは、\(A\)の任意の非空な部分集合が最小元を持つこと、すなわち、\begin{equation*}\forall B\subset A:\left( B\not=\phi \Rightarrow \exists \min B\right)
\end{equation*}が成り立つこととして定義されます。

全順序集合の要素\(a\in A\)が与えられたとき、\(a\)より小さい\(A\)の要素をすべて集めることにより得られる集合を、\begin{equation*}L_{s}\left( a\right) =\left\{ x\in A\ |\ x<a\right\}
\end{equation*}で表記し、これを要素\(a\)に関する集合\(A\)の狭義の始切片と呼びます。

さて、整列集合\(A\)の部分集合\(B\)が以下の条件\begin{equation}\forall x\in A:\left[ L_{s}\left( x\right) \subset B\Rightarrow x\in B\right] \quad \cdots (1)
\end{equation}を満たす場合には、\begin{equation*}
B=A
\end{equation*}が成り立つことが保証されます。これを超限帰納法の原理（principle of transfinite induction）と呼びます。

狭義の始切片\(L_{s}\left( x\right) \)の定義を踏まえた上で\(\left( 1\right) \)を言い換えると、\begin{equation*}\forall x\in A:\left[ \left( \forall y\in A:\left( y<x\Rightarrow y\in
B\right) \right) \Rightarrow x\in B\right] \end{equation*}となります。つまり、整列集合\(A\)の部分集合\(B\)が与えられた状況において\(A\)の要素\(x\)を任意に選んだとき、\(x\)より小さい\(A\)の要素がいずれも\(B\)の要素である場合には、\(x\)もまた\(B\)の要素になるということです。このとき、\begin{equation*}A=B
\end{equation*}が成り立つというのが超限帰納法の原理の主張です。

超限帰納法による証明

先の命題は超限帰納法による証明（proof by transfinite induction）の根拠になります。超限帰納法による証明とは、整列集合\(A\)に属する要素\(x\)に関する主張\begin{equation*}P\left( x\right)
\end{equation*}が任意の要素\(x\in A\)に関して成り立つことを示すための手法であり、具体的には、要素\(x\in A\)を任意に選んだ上で、\begin{equation*}\left[ \forall y\in A:\left( y<x\Rightarrow P\left( y\right) \right) \right] \Rightarrow P\left( x\right)
\end{equation*}が成り立つことを示すというものです。なぜ、この手法が有効なのでしょうか。順番に解説します。

改めて整理すると、超限帰納法による証明とは、整列集合\(A\)に関して以下の全称命題\begin{equation}\forall x\in A:P\left( x\right) \quad \cdots (1)
\end{equation}が真であることを示すために、以下の命題\begin{equation}
\forall x\in A:\left[ \left( \forall y\in A:\left( y<x\Rightarrow P\left(
y\right) \right) \right) \Rightarrow P\left( x\right) \right] \quad \cdots (2)
\end{equation}が真であることを示す、というものです。これは、整列集合\(A\)の要素\(x\)を任意に選んだとき、\(x\)より小さい任意の\(A\)の要素\(y\)について主張\(P\left( y\right) \)が成り立つという仮定のもとで主張\(P\left( x\right) \)が成り立つことを示す作業に相当します。さて、\(\left( 2\right) \)が真であることを証明できたとします。集合\(B\subset A\)を、\begin{equation*}B=\left\{ x\in A\ |\ P\left( x\right) \right\}
\end{equation*}と定義したとき、\(\left(2\right) \)が真であることは、\begin{equation*}\forall x\in A:\left[ \left( \forall y\in A:\left( y<x\Rightarrow y\in
B\right) \right) \Rightarrow x\in B\right] \end{equation*}が真であることを意味します。すると、超限帰納法の原理より、\begin{equation*}
B=A
\end{equation*}を得ますが、これと\(B\)の定義より、\begin{equation*}A=\left\{ x\in A\ |\ P\left( x\right) \right\}
\end{equation*}すなわち、\begin{equation*}
\forall x\in A:P\left( x\right)
\end{equation*}を得ます。これは\(\left(1\right) \)に他なりません。以上の理由により、\(\left( 2\right) \)が真であることを示せば\(\left( 1\right) \)が真であることを示したことになることが明らかになりました。

超限帰納法の原理の一般性

数学的帰納法による証明とは、自然数\(n\)に関する主張\begin{equation*}P\left( n\right)
\end{equation*}が任意の自然数\(n\in \mathbb{N} \)に関して成り立つことを示すための手法であり、具体的には、まず、\(n=1\)の場合の主張\begin{equation*}P\left( 1\right)
\end{equation*}が真であることを示した上で、さらに自然数\(k\in \mathbb{N} \)を任意に選んだ上で、\begin{equation*}P\left( k\right) \Rightarrow P\left( k+1\right)
\end{equation*}が成り立つことを示すというものです。

数学的帰納法が証明方法として有効であることの根拠は以下の命題であり、これを数学的帰納法の原理と呼びました。

完全帰納法による証明とは、自然数\(n\)に関する主張\begin{equation*}P\left( n\right)
\end{equation*}が任意の自然数\(n\in \mathbb{N} \)に関して成り立つことを示すための手法であり、具体的には、まず、\(n=1\)の場合の主張\begin{equation*}P\left( 1\right)
\end{equation*}が真であることを示した上で、さらに自然数\(k\in \mathbb{N} \)を任意に選んだ上で、\begin{equation*}\left[ \forall n\in \mathbb{N} :\left( n\leq k\Rightarrow P\left( n\right) \right) \right] \Rightarrow
P\left( k+1\right)
\end{equation*}が成り立つことを示すというものです。

完全帰納法が証明方法として有効であることの根拠は以下の命題であり、これを完全帰納法の原理や強数学的帰納法の原理などと呼びました。

数学的帰納法の原理と完全帰納法の原理は必要十分です。加えて、超限帰納法の原理から完全帰納法の原理を導くことができるため、超限帰納法の原理は数学的帰納法の原理や完全帰納法の原理の一般化です。