数学的帰納法の論理構造 | 集合と論理

1 帰納法の原理

この記事では、自然数は $1, 2, 3, \dots$ を指すものとし、 $0$ を含めません。 $0$ を含める流儀もあり、その場合は以下の基底段階が $P(0)$ になります。

定理 1.1 (数学的帰納法). 自然数 $n$ についての述語 $P$ が、次の二つを満たすとする。

$P(1)$ が真である（基底段階）。
すべての自然数 $k$ について $P(k) \Rightarrow P(k+1)$ が真である（帰納段階）。

このとき、すべての自然数 $n$ について $P(n)$ が真である。

基底段階は $n=1$ という一つの場合について $P(1)$ が真であることを示します。帰納段階は、個々の $P(k)$ が真であることではなく、含意 $P(k)\Rightarrow P(k+1)$ がすべての自然数 $k$ について真であることを示します。したがって、帰納段階だけでは、真である $P(k)$ は一つも保証されません。

二つの段階を合わせると、 $P(1)$ に $P(1)\Rightarrow P(2)$ を適用して $P(2)$ を得ます。さらに $P(2)\Rightarrow P(3)$ を適用すると $P(3)$ を得ます。帰納法の原理は、この出発点と全称的な引継ぎの性質から、すべての自然数 $n$ に対する $P(n)$ を結論します。

例 1.2. $P(n)$ を「 $n=n+1$ 」とする。 $P(k)$ 、すなわち $k=k+1$ を仮定すると、両辺に $1$ を加えて $k+1=k+2$ を得る。したがって、すべての自然数 $k$ について $P(k)\Rightarrow P(k+1)$ は真である。一方、 $P(1)$ は $1=2$ という偽の命題である。実際、どの自然数 $n$ についても $P(n)$ は偽である。よって、帰納段階が真であっても、基底段階が無ければすべての $P(n)$ を結論することはできない。

問題 1.3. 自然数についての述語 $P$ が、 $P(1)$ と $P(2)$ が真であり、すべての自然数 $k$ について $P(k)\Rightarrow P(k+2)$ が真であるとする。すべての自然数 $n$ について $P(n)$ が真であることを示せ。また、 $P(2)$ が真であるという仮定を除くと結論が成り立たない例を挙げよ。

解答.

自然数 $j$ について、 $Q(j)$ を $P(2j-1)$ 、 $R(j)$ を $P(2j)$ と定める。 $Q(1)=P(1)$ と $R(1)=P(2)$ はともに真である。自然数 $j$ を任意に取る。仮定の含意を $k=2j-1$ に適用すると $Q(j)\Rightarrow Q(j+1)$ を得る。同じ含意を $k=2j$ に適用すると $R(j)\Rightarrow R(j+1)$ を得る。定理 1.1を $Q$ と $R$ にそれぞれ適用すれば、すべての自然数 $j$ について $Q(j)$ と $R(j)$ は真である。どの自然数も $2j-1$ または $2j$ の形に表すことができるので、すべての自然数 $n$ について $P(n)$ が真となる。

$P(2)$ の仮定を除いた場合は、 $P(n)$ を「 $n$ は奇数である」とする。 $P(1)$ は真であり、奇数に $2$ を加えても奇数なので、すべての自然数 $k$ について $P(k)\Rightarrow P(k+2)$ は真である。しかし $P(2)$ は偽である。▨

2 帰納法が成り立つ根拠は、自然数の性質にある

帰納法が正しいことは、論理の規則だけからは出てきません。根拠は、自然数が「 $1$ から始まり、 $1$ ずつ増え、すべての自然数がこの積み上げによって得られる」という構造をもつことにあります。この構造を公理として書き下したものがペアノの公理であり、帰納法の原理はその一つとして置かれます。

同じ性質を別の形で述べたものが、次の最小数原理です。

定理 2.1. 自然数について、 $1$ が最小であること、 $1$ より大きい自然数 $n$ がある自然数 $m$ を用いて $n=m+1$ と表されること、および任意の自然数 $k,n$ について $k\le n+1$ かつ $k\ne n+1$ ならば $k\le n$ であることを認める。このとき、数学的帰納法の原理と「自然数からなる空でない集合には最小元がある」という最小数原理は同値である。

証明 (最小数原理から帰納法を導く). 最小数原理を仮定する。自然数 $n$ についての述語 $P$ が定理 1.1 (1)と定理 1.1 (2)を満たすとし、

S=\{\,n\in\NN\mid P(n)\text{ は偽}\,\}

と置く。 $S\ne\varnothing$ と仮定すると、最小数原理により $S$ は最小元 $n_0$ をもつ。

$n_0=1$ ならば、 $n_0\in S$ により $P(1)$ は偽であるが、基底段階により $P(1)$ は真である。 $n_0>1$ ならば、 $n_0=m+1$ を満たす自然数 $m$ がある。 $m<n_0$ と $n_0$ の最小性から $m\notin S$ 、すなわち $P(m)$ は真である。帰納段階を $k=m$ に適用すると $P(m+1)=P(n_0)$ は真となり、 $n_0\in S$ によって $P(n_0)$ が偽であることと両立しない。どちらの場合も仮定 $S\ne\varnothing$ に反するので、 $S=\varnothing$ である。よって、すべての自然数 $n$ について $P(n)$ は真である。▨

証明 (帰納法から最小数原理を導く). 帰納法の原理を仮定する。 $S$ を自然数からなる集合とし、 $S$ は最小元をもたないと仮定する。 $P(n)$ を「 $1$ から $n$ までのどの自然数も $S$ に属さない」と定める。

$1\in S$ ならば、 $1$ が最小の自然数であることから $1$ は $S$ の最小元となる。これは $S$ が最小元をもたないという仮定に反するので、 $1\notin S$ であり $P(1)$ は真である。

自然数 $k$ を任意にとり、 $P(k)$ を仮定する。 $k+1\in S$ と仮定する。 $k+1$ より小さい元 $s\in S$ があるならば、 $s\le k+1$ かつ $s\ne k+1$ であるから $s\le k$ となり、 $P(k)$ に反する。したがって $S$ に $k+1$ より小さい元は存在せず、 $k+1$ は $S$ の最小元となる。これは $S$ が最小元をもたないという仮定に反するので、 $k+1\notin S$ であり $P(k+1)$ は真である。

定理 1.1により、すべての自然数 $n$ について $P(n)$ は真である。したがって $S=\varnothing$ である。「 $S$ が最小元をもたないならば $S$ は空集合である」という含意の対偶は、「 $S$ が空でないならば $S$ は最小元をもつ」である。§A3.6 定理 1.2により、空でない自然数の集合は最小元をもつ。▨

この同値関係から、帰納法と、最小の反例を取る背理法とが同じ内容であることが分かります。「すべての $n$ で $P(n)$ 」を示すために、 $P$ が偽になる最小の自然数を取って矛盾を導く議論は、帰納法の別の書き方です。

3 強い帰納法

帰納段階で $P(k)$ だけを仮定するのではなく、 $P(1)$ から $P(k)$ までのすべてを仮定してよい形があります。

定理 3.1 (強い帰納法). 自然数 $n$ についての述語 $P$ が、 $P(1)$ が真であり、かつすべての自然数 $k$ について、 $P(1),P(2),\ldots,P(k)$ がすべて真であることから $P(k+1)$ が従うとする。このとき、すべての自然数 $n$ について $P(n)$ が真である。

証明. $Q(k)$ を「 $1\le j\le k$ を満たすすべての自然数 $j$ について $P(j)$ が真である」と定める。 $Q(1)$ は $P(1)$ と同値であり、仮定により真である。自然数 $k$ を任意にとり、 $Q(k)$ を仮定する。 $Q(k)$ から $P(1),P(2),\ldots,P(k)$ はすべて真であるので、強い帰納法の帰納段階から $P(k+1)$ が従う。よって、 $1\le j\le k+1$ を満たすすべての自然数 $j$ について $P(j)$ が真であり、 $Q(k+1)$ が成り立つ。定理 1.1を $Q$ に適用すると、すべての自然数 $k$ について $Q(k)$ が真である。したがって、すべての自然数 $n$ について $P(n)$ が真である。▨

強い帰納法は通常の帰納法から導かれるので、証明することができる主張の範囲は両者で変わりません。

例 3.2. 和の公式

1+2+\cdots+n=\frac{n(n+1)}2

は通常の帰納法で示される。 $n=1$ のときは両辺が $1$ である。 $n=k$ で公式が成り立つと仮定すると、

1+2+\cdots+k+(k+1) =\frac{k(k+1)}2+(k+1) =\frac{(k+1)(k+2)}2

となる。 $P(k+1)$ を示すために $P(k)$ だけを用いるので、通常の帰納法で足りる。

$R(j)$ を「自然数 $j+1$ は素数の積として表される」とする。 $R(1)$ は $2$ が素数であることから真である。 $R(1),R(2),\ldots,R(k)$ がすべて真であると仮定する。 $k+2$ が素数ならば $R(k+1)$ は真である。 $k+2$ が合成数ならば $k+2=ab$ 、 $2\le a,b\le k+1$ を満たす自然数 $a,b$ がある。 $1\le a-1,b-1\le k$ であるから、帰納法の仮定により $a$ と $b$ はそれぞれ素数の積として表され、 $k+2$ も素数の積として表される。よって $R(k+1)$ は真であり、強い帰納法によりすべての自然数 $j$ について $R(j)$ が真である。したがって、 $2$ 以上のすべての自然数は素数の積として表される。因数 $a,b$ は事前に決まらないため、 $R(k)$ だけでなくすべての既知の場合を用いる。

$a_{k+1}$ が $a_k$ と $a_{k-1}$ の両方から定まる漸化式について、 $a_{k+1}$ の性質を示すときに $a_k$ と $a_{k-1}$ の性質をともに用いる場合がある。この場合には $P(k)$ と $P(k-1)$ が必要なので、それまでのすべての場合を仮定する強い帰納法を用いることができる。

§A3.10数学的帰納法の論理構造

1 帰納法の原理

2 帰納法が成り立つ根拠は、自然数の性質にある

3 強い帰納法

例題

演習

前提記事