整列原理
全順序集合\(\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*}が成り立つこととして定義されます。
すべての自然数からなる集合\(\mathbb{N} \)上に大小関係\(\leq \)を定義すれば全順序集合\(\left( \mathbb{N} ,\leq \right) \)が得られますが、これは整列集合です。つまり、\(\mathbb{N} \)の任意の非空な部分集合は最小元を持ちます。これを整列原理（well-ordering principle）と呼びます。
整列原理にもとづく証明
整列原理は背理法を用いた証明において有用です。
\end{equation*}で表記します。\(X=\phi \)を示すことが目標であるため、\(X\not=\phi \)が成り立つものと仮定して矛盾を導きます。\(X\)は\(\mathbb{N} \)の非空な部分集合であるため、整列原理より、\begin{equation*}n=\min X
\end{equation*}が存在します。最小元の定義より\(\min X\in X\)すなわち\(n\in X\)であるため、\(X\)の定義より、\begin{eqnarray*}&&\left( a\right) \ n\in \mathbb{Z} \\
&&\left( b\right) \ 0<n<1
\end{eqnarray*}がともに成り立ちます。\(\left( b\right) \)より、\begin{equation*}n^{2}<n
\end{equation*}を得ます。整数集合\(\mathbb{Z} \)は乗法について閉じているため、\(\left( a\right) \)より、\begin{equation*}n^{2}\in \mathbb{Z} \end{equation*}を得ます。\(\left( b\right) \)より\(n>0\)ですが、正の整数の2乗は正であるため、\begin{equation*}0<n^{2}
\end{equation*}を得ます。以上より、\begin{equation*}
0<n^{2}<n<1
\end{equation*}が成り立つことが明らかになりました。したがって\(X\)の定義より、\begin{equation*}n^{2}\in X
\end{equation*}を得ます。つまり、\(n\)すなわち\(\min X\)より小さい要素が\(X\)の中に存在することが明らかになりましたが、以上の事実は\(\min X\)が\(X\)の最小元であることと矛盾です。したがって背理法より、\(X=\phi \)であることの証明が完了しました。
\end{equation*}すなわち、\begin{equation*}
1^{3}+2^{3}+\cdots +n^{3}=\frac{n^{2}\left( n+1\right) ^{2}}{4}
\end{equation*}が成り立つことを示します。そこで、この主張が成り立たないものと仮定して、すなわち、\begin{equation*}
\exists n\in \mathbb{N} :\sum_{i=1}^{n}i^{3}\not=\frac{n^{2}\left( n+1\right) ^{2}}{4}
\end{equation*}が成り立つものと仮定して矛盾を導きます。以下の集合\begin{equation*}
X=\left\{ n\in \mathbb{N} \ |\ \sum_{i=1}^{n}i^{3}\not=\frac{n^{2}\left( n+1\right) ^{2}}{4}\right\}
\end{equation*}を定義します。仮定より\(X\not=\phi \)です。\(X\)は\(\mathbb{N} \)の非空な部分集合であるため、整列原理より、\begin{equation*}m=\min X
\end{equation*}が存在します。最小元の定義より\(\min X\in X\)すなわち\(m\in X\)であるため、\(X\)の定義より、\begin{eqnarray*}&&\left( a\right) \ m\in \mathbb{N} \\
&&\left( b\right) \ \sum_{i=1}^{m}i^{3}\not=\frac{m^{2}\left( m+1\right) ^{2}}{4}
\end{eqnarray*}がともに成り立ちます。\(X\)の定義より\(1\not\in X\)であるため\(m>1\)です。また、最小限の定義より、\(m>i\geq 1\)を満たす任意の\(i\)について\(i\not\in X\)であるため、\(m-1\not\in X\)もまた成り立ちます。すると\(X\)の定義より、\begin{equation*}\left( c\right) \ \sum_{i=1}^{m-1}i^{3}=\frac{\left( m-1\right) ^{2}m^{2}}{4}
\end{equation*}が成り立ちます。すると、\begin{eqnarray*}
\sum_{i=1}^{m}i^{3} &=&\sum_{i=1}^{m-1}i^{3}+m^{3} \\
&=&\frac{\left( m-1\right) ^{2}m^{2}}{4}+m^{3}\quad \because \left( c\right)
\\
&=&\frac{m^{2}\left( m+1\right) ^{2}}{4}
\end{eqnarray*}を得ますが、これは\(\left( b\right) \)と矛盾です。したがって背理法より、\(X=\phi \)であることの証明が完了しました。
整列原理と数学的帰納法の原理の関係
数学的帰納法による証明とは、自然数\(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*}が成り立つことを示すというものです。
数学的帰納法が証明方法として有効であることの根拠は以下の命題であり、これを数学的帰納法の原理と呼びました。
&&\left( b\right) \ \forall k\in \mathbb{N} :\left( k\in A\Rightarrow k+1\in A\right)
\end{eqnarray*}を満たす場合には、\begin{equation*}
A=\mathbb{N} \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*}が成り立つことを示すというものです。
完全帰納法が証明方法として有効であることの根拠は以下の命題であり、これを完全帰納法の原理や強数学的帰納法の原理などと呼びました。
&&\left( b\right) \ \forall k\in \mathbb{N} :\left[ \left( \forall n\in \mathbb{N} :\left( n\leq k\Rightarrow n\in A\right) \right) \Rightarrow k+1\in A\right] \end{eqnarray*}を満たす場合には、\begin{equation*}
A=\mathbb{N} \end{equation*}が成り立つ。
完全帰納法の原理と数学的帰納法の原理は必要十分です。また、先に示したように整列原理と数学的帰納法の原理は必要十分です。したがって以下を得ます。
演習問題
\end{equation*}すなわち、\begin{equation*}
1+3+5+\cdots +2n-1=n^{2}
\end{equation*}が成り立つことを証明してください。ただし、証明では整列原理を利用してください。
\end{equation*}すなわち、\begin{equation*}
2+4+6+\cdots +2n=n\left( n+1\right)
\end{equation*}が成り立つことを証明してください。ただし、証明では整列原理を利用してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】