数学的帰納法の落とし穴

Copyright (C) virtual_high_school, 2022

§1. 数学的帰納法はおかしい

§2. 数学的帰納法とは

§3. いつまで待っても辿り着かない

§4. $\forall$ はどこを修飾するか

§∞. 文献

§1. 数学的帰納法はおかしい

数学的帰納法はおかしいと言う人（数学教員）がいる。
「今から証明しようとしていることを仮定しているので、おかしい（間違っている）」というのだ。

私は、それは§3 で述べるような理由ではないのかと永らく思っていたのだが、ある本を読んで§4 に述べる誤解をしているのかもしれないと思うようになった。

§2. 数学的帰納法とは

数学的帰納法は自然数 $n$ に関する命題 $P(n)$ を証明するテクニックの一つである。その証明の形式は次のようになる。

(第�T段落) $n=1$ のとき $P(n)$ が正しいこと、すなわち $P(1)$ が真であることを示す。

(第�U段落) $n=k$ のとき $P(n)$ が成り立てば、$n=k+1$ のときにも $P(n)$ が成り立つこと、すなわち

「$P(n) \Rightarrow P(n+1)$」が任意の $n$ に対して真である

$\forall n: P(n) \Rightarrow P(n+1)$

を示す。

こうすると、任意の自然数 $n$ について $P(n)$ が真である、すなわち

$\forall n: P(n)$

が証明されたことになる。

この推論方式は、よく将棋倒し（ドミノ倒し）にたとえられる。

また、高校ではあまり出てこないが、次の形の数学的帰納法もある。

(�T) $P(1)$ を示す。
(�U) $(\forall n\leq k: P(n)) \Rightarrow P(k+1)$ を示す。

利点は(�U)で前提条件が $n\leq k$ と範囲が緩められる（使える条件が増える）ので、証明がしやすくなることである。

また、3項間の漸化式の証明等には、次のような変形バージョンが使われることもある。

(�T) $P(1), P(2)$ を示す。
(�U) 「$P(n),P(n+1) \Rightarrow P(n+2)$」を任意の $n$ に対して示す。

【注】 数学的帰納法を略して、帰納法と言うことがある。しかし、数学的帰納法は（ふつうの意味での）帰納法ではなく、演繹法である。

§3. いつまで待っても辿り着かない

数学的帰納法をおかしいと言う人は、次のように考えている可能性がある。

$P(n) \Rightarrow P(n+1)$ というのはどういうことかというと、例えば $n=100$ なら、

$P(100) \Rightarrow P(101)$

だが、$P(100) $ が真でないと $P(101)$ が成り立つことが分からない。そのために

$P(99) \Rightarrow P(100)$

を示さねばならず、さらに遡って

$P(98) \Rightarrow P(99)$

を示さねばならず、さらに遡って……となってしまい、なかなか証明できない。でも $n=100$ なら遡っていってやがて $P(1)$ に辿り着くが、任意の $n$ だったらどうする？ 自然数は無限にあるのだから、遡っても遡っても $P(1)$ に辿り着かないのではないかという心配である。(実際は、自然数は無限個あるけど、どの自然数も有限値だから有限回で $P(1)$ に辿り着く。)

実は、この心配は個別の $n$ ではなく、一般の（任意の） $n$ について

$P(n) \Rightarrow P(n+1)$

を示せば氷解する。

ここで $P(n) $ が真か偽か分らん、とクレームがあるかもしれない。$P(n) $ は不定元を含むから、命題でなく真でも偽でもないのである。変数 $n$ を含む命題関数なのである。$n$ に具体的数値を代入してみて初めて真偽が決まる。

では $P(n) \Rightarrow P(n+1)$ は証明できないのかと言うと、そんなことはない。仮定の $P(n) $ が偽であるときは $P(n) \Rightarrow P(n+1)$ は真になるから、$P(n) $ が真のときだけを証明すればよいからだ。

つまり、私は数学的帰納法が分からないと言う人は、「仮定 $P$ が偽のときは $P \Rightarrow Q$ は真」が理解できていないと私は考えたのである。

§4. $\forall$ はどこを修飾するか

文献 [1] によると、数学的帰納法についての誤解の原因は $\forall n: P(n) \Rightarrow P(n+1)$ はホントは

$\forall n: (P(n) \Rightarrow P(n+1))$

のことなのだが、これを

$(\forall n: P(n)) \Rightarrow P(n+1)$

のことだと解釈していることだという。確かにこれでは「今から証明しようとしていることを仮定している」ことになる。（でも、そんな単純な誤解ってあるのかなとも思ってしまう。）

前者の論理式は

$\forall n: (\overline{P(n)} \vee P(n+1))$

に同値で、後者は

$\overline{(\forall n: (P(n))} \vee P(n+1)$
$\Leftrightarrow (\exists n:\overline{P(n)}) \vee P(n+1)$

に同値だから、両者は $\forall$ と $\exists$ が交替しているだけのようだが、実はまったく似て非なるものである。

後者はありえない構文なのである。$\vee$ の左側の $\exists n:\overline{P(n)}$ は意味のある命題だが、右側の $P(n+1)$ は自由変数 $n$ を束縛する限定子がないから命題ですらない。だから、真偽を問う意味もないし、証明することもできないのである。

§∞. 文献

[1] 長岡亮介「数学再入門」日本評論社、2014年

　この本のp.197 に数学的帰納法についての記述がある。