[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる |
Copyright (C) virtual_high_school, 2022
§1. 数学的帰納法はおかしい
§2. 数学的帰納法とは
§3. いつまで待っても辿り着かない
§4. $\forall$ はどこを修飾するか
§∞. 文献
数学的帰納法はおかしいと言う人(数学教員)がいる。
「今から証明しようとしていることを仮定しているので、おかしい(間違っている)」というのだ。
私は、それは§3 で述べるような理由ではないのかと永らく思っていたのだが、ある本を読んで§4 に述べる誤解をしているのかもしれないと思うようになった。
数学的帰納法は自然数 $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$ に対して示す。
【注】 数学的帰納法を略して、帰納法と言うことがある。しかし、数学的帰納法は(ふつうの意味での)帰納法ではなく、演繹法である。
数学的帰納法をおかしいと言う人は、次のように考えている可能性がある。
$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$ は真」が理解できていないと私は考えたのである。
文献 [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年
[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる |