次： 同型定理と演算 上： 自然数と数学的帰納法 前： ペアノの公理

数学的帰納法

ここで「昇列」を定義する．

$N$ の部分集合 $K$ で

$$x \in K \quad \Rightarrow \quad x+1\in K$$

が成り立つとき $K$ を「昇列」という． $N$ の要素 $a$ を含むすべての昇列の共通部分を $K(a)$ とする． これは $a$ からはじめて $+1$ の規則で作られた要素だけの集合である．

定理 1

自然数の集合$N$ は，次の性質をもつ．

1. $1$ を含む昇列はひとつしかなく $N=K(1)$ である．
2. 数学的帰納法の原理 自然数の集合$N$ の部分集合 $M$ において
   1. $1 \in M$
   2. $k \in M \Rightarrow k+1 \in M$
   が成り立てば $N=M$ である．
3. $1$ 以外のすべての要素 $x$ は$x=z+1$ となる要素 $z$ をただ一つもつ．
4. $N$ の任意の空でない部分集合 $M$ には， $m\in M$ で $M\subset K(m)$ となるものがただひとつある．

証明

1. 1を含む任意の昇列 $K$ に対し， $N$ において$x$に$x+1$を対応させる規則を$K$ に制限した規則を考える． 定義より，$k\in K$のとき$k+1 \in K$ であるから， これは $K$ の要素 $k$ に $k+1$ を対応させる規則となる． この対応の規則によって， $K$ は 自然数の公理(i)(ii)(iii)(iv)を満たす． $N$ の最小性から $N=K$ である．よってまた $1$ を含む昇列はすべて $N$ に一致する．
2. $M$ は $1$ を含む昇列である．ゆえに(1)から $N=M$．
3. $N$ において， $a$ にはじまり $+1$ の操作を繰り返して $b$ に至る系列はただひとつである． 二つあれば，そのいずれかの系列を定めその中にのみ存在する要素を $N$ から取り除いても， $N$ は $1$ を含む昇列となり $N$ の最小性に反するからである. $N$ の要素 $a$ で $1$ でなく， しかも $a=x+1$ となる要素 $x$ が存在しない要素の集合を $Q$ とする．
   
   $$N'=N-Q$$
   
   
   とする．$N'$の任意の要素 $x$ に対して $x+1\not\in Q$つまり $x+1 \in N'$ である． ゆえに $N'$ は $1$ を含む昇列であるから $N'=N$ ．つまり $Q$ は空集合であり， $1$ 以外で直前の要素の存在しない要素はない．

   次に $z\ne z'$ かつ $z+1=z'+1$ となるものがあるとする．二つの系列

   $$\begin{eqnarray*} l&:&1\to 1+1\to\cdots\to z \to z+1\\ l'&:&1\to 1+1\to\cdots\to z' \to z'+1=z+1 \end{eqnarray*}$$
   
   
   が存在し，系列の唯一性に反する．ゆえに直前の要素はただひとつである．
4. $1 \in M$ なら $M=K(1)$ なので$1 \not\in M$ とする．
   
   $$R=\{x\vert M \subset K(x)\}$$
   
   
   とおく．$1 \in R$ なので $R$ は空でない． $a\in R$ であるが $a+1 \not\in R$であるような要素$a$が$R$ に存在する． なぜなら，もしなければ $R$ が $N$ 自身になる． ところが $x\in N$ に対して $x\not\in K(x+1)$ だから $\cap _{x \in N}K(x)=\emptyset$である． つまり
   
   $$M \subset \cap_{x \in N}K(x) =\emptyset$$
   
   
   となって $M$ が空集合になるのである．

   $M\not\subset K(a+1)$ なので $m\in M ,\ m \not\in K(a+1)$ が存在する．つまり
   

   $$m\in K(a),\ m \not\in K(a+1)$$
   
   
   となり $a=m$ ，つまり $M\subset K(m)$ となる $m$ が存在した． $m$ と $m'$ と二つあれば $m\in K(m')$ かつ $m'\in K(m)$ となり， $m$ から $m'$ をへて $m$ にいたる系列ができる．$m$から$m$にいたる系列が2つでき， 系列がただ一つであることに反する．□

このように構成された集合 $N$ の要素は

$$1,\ 1+1,\ (1+1)+1,\ \cdots,\$$

という形をしている．これを表記の簡単のために

$$1,\ 2,\ 3,\ \cdots$$

と書くのである．

史織　 なぜ先の定理が数学的帰納法の原理 とよばれるのですか．

南海　 数学的帰納法とは次のような証明方法であった．

$p(n)$ を自然数 $n$に関する条件とする．

1. $p(1)$が成立する．
2. $p(k)$が成立するなら$p(k+1)$が成立する．
3. (1), (2)より, すべての自然数 $n$ に対して $p(n)$が成立する．

南海　 数学的帰納法を言いかえると，条件 $p(n)$ の真理集合，つまり$p(n)$が真となるような$n$の集合が， 自然数全体であることを示すということになる．

史織　 集合の記号を用いると条件 $p(n)$ の真理集合 $M$ は

$$M=\{n\ \vert\ p(n)が成立,\ n \in N (自然数の集合)\}$$

となります．

自然数の性質によって，$M$が$N$と一致するのですね．

数学的帰納法の(1)は $1 \in M$を示している．(2)は $k \in M$ なら $k+1 \in M$ を示している． つまり$M$は1を含む昇列なので $M=N\ (自然数の集合)$ である． 条件が成立する $n$ の集合 $M$ が自然数全体となり， すべての自然数 $n$ でなり立つ，つまり(3)の成立がわかる，

これが数学的帰納法です．

南海　 そのとおり．

自然数の集合というのは， 「1があって$k$が要素であれば$k+1$も要素である」ような集合でいちばん小さいもの， として特徴づけられる．

このように数学的帰納法が証明の方法として成立するのは，自然数の性質が土台にあるからである．

次： 同型定理と演算 上： 自然数と数学的帰納法 前： ペアノの公理