今月は精神的にも肉体的にも、ものすごく疲れました。この疲労困憊した状態はまだ続きそうです。
そこで今日は、ごく初等的なことについて、ほとんど単なるメモを記すだけにさせてもらいます。そして最後に一言、感想を添えて終わりにします。
目次
はじめに
今、次の本を読んでいます。
・ 瀬山士郎 『数学にとって証明とはなにか』、ブルーバックス 、講談社、2019年 *1 。
この本に数学的帰納法の簡潔でとても気持ちのいい証明が書いてありましたので、本日はそれを記します。よく知られている証明なのかもしれませんが、私は知りませんでしたので、ここにメモしておきます。
(なお、私は数学的帰納法について、ほんの初歩しか知りませんので、間違ったことを書いていましたらすみません。謝ります。ごめんなさい。)
記すのは、数学的帰納法による証明ではなく、数学的帰納法の正しさを立証している証明です。
数学的帰納法を高校で習う時、その証明法がうまくいくことを、将棋倒しやドミノが倒れる例を使って説明されることがあると思いますが、その方法の正しさを証明することはないと思います。その方法の正しさは、将棋やドミノの例から、ほとんど初めから自明のこととされている、と見なすことができると思います。
また、数学的帰納法は、自然数を公理的に展開する際に、普通、公理として立てられる、ということもよく知られていると思います (Peano の公理)。ここでも数学的帰納法は、初めから当然成り立つものと見なされています。
その一方で、数学的帰納法に対しては証明もされるようです。私は数学的帰納法の歴史について、まったく無知ですので 、この方法の正しさを最初に証明したのは誰なのか、全然知りません *2 。誰が最初なのか、私は知りませんが、数学の big name では、Dedekind と Frege がその方法の正しさを証明していることが知られています。この二人の証明では、(素朴) 集合論が前提されている、つまり集合論を用意して、それでもって証明している、または何らかの特定の公理系のなかで証明が行われている、と解せられます *3 。
以下では、数学的帰納法の正しさを、集合論も特定の公理系も前提せず、informal に証明したものを記します。上に掲げた瀬山先生の本の、ブルーバックス版88-89ページ *4 に書かれている簡潔で要を得た証明を参考にします *5 。先生の証明ほとんどそのままです。
数学的帰納法を素朴に証明する
まず、数学的帰納法とは、自然数 1, 2, 3, … について *6 、次の二つの文が成り立つことを証明することにより (n は任意の自然数),
(Basis) P(1),
(Induction Step) P(n) ならば P(n+1),
以下の文を結論する証明方法でした。
(帰結) すべての自然数 n について、P(n).
この証明法が正しいことを、背理法を使って証明します。
最初に、(Basis) と (Induction Step) が正しいのに、(帰結) が正しくない、と仮定します。
すると、P が当てはまらない自然数が少なくとも一つはある、ということです。
それらの自然数は一つだけかもしれませんし、そうではなくて複数あるかもしれませんが、いずれにしても、そのような自然数のうち、最小のものを m とします。この時、m については P が成り立たない、ということです。すなわち、P(m) ではない、ということです。このことを [事実] と記すことにします。
そうすると m−1 ついては P が成り立ちます。つまり、P(m−1) です。
なお m は、(Basis) により、1 ではありません。m は 1 より大きい自然数です。そのため m−1 は 0 でもなければ負数でもありません。
さて、P(m−1) でした。そして (Induction Step) により、P(m−1) ならば P(m−1+1) です。
よって、P(m−1+1) です。これはつまり P(m) が成り立つということです。しかしこのことは、先ほどの [事実] と矛盾します。
故に、最初の仮定は否定されねばなりません。すなわち「(Basis) と (Induction Step) が正しいのに、(帰結) が正しくない」ということはありません。事実は、(Basis) と (Induction Step) が正しいならば、(帰結) も正しい、ということになります。これが証明すべきことでした。
私は瀬山先生のこの証明を読んで、「なるほどね、小気味がいいなぁ〜」と感じました。
最後に一言
上の証明で踏まえておく必要があると思われるのは、大雑把に言うと、自然数と数学的帰納法とを別々のものと見なした上で、その証明を読まなければならないだろう、ということです。
私も含め、たぶん多くの人は、何となく次のような感じのことを思っているのではなかろうかと推測します。つまり「何かが自然数ならば、それについては数学的帰納法が成り立ち、かつ逆に、数学的帰納法が成り立つならば、それは自然数である」と *7 。
要するに、大まかに言うと、自然数と数学的帰納法とは、同じもののことである、ということです。これは、いわゆる Peano の公理系の立場と見なせるだろうと思います。
上の証明を見ると、そのなかで、自然数の大小関係や加法、減法などに触れられているのがわかると思います。つまりこれらの自然数についての馴染みある特徴や性質を前提にした上で、上記の証明では数学的帰納法が正しいものとして証明されているわけです。
したがって、初めから「自然数 = 数学的帰納法」だと考えてしまうと、上の証明は論点先取の虚偽を犯しているということになります。なぜならこの時、自然数の性質を前提して数学的帰納法の正しさを証明することは、数学的帰納法を前提して数学的帰納法の正しさを証明することになるからです。よって、「自然数 ≠ 数学的帰納法」と考えて、上の証明を読む必要があるだろうと思います。
(なお、瀬山先生は今述べた虚偽を犯している、と言っているのではありません。先生は、まったくの初心者向けに証明を提示する必要性から、素朴な直観に基づいた証明をされているだけです。念のため、書き添えておきます。)
以上は私の感想です。私は数学にも論理学にも無知ですので、ひどい勘違いをしているかもしれません。大切なことを見落としているかもしれません。ですので、私の感想は決して鵜呑みにせず、このブログで言及した文献などで裏を取ってください。お手数おかけしますが、よろしくお願い致します。
ちなみに、今回のブログのタイトルにある naive の意味は、「集合論や何らかの公理系を前提せずに、素朴に直観的になされている」というぐらいのものです。決して否定的な意味合いを込めているのではありません。
ここまでに見られる私の誤解、無理解、誤字、脱字、その他の不備や、追究不足に対し、お詫び申し上げます。
*1:本書は、瀬山士郎、『なっとくする数学の証明』、なっとくシリーズ、講談社サイエンティフィク、2013年をわずかに改訂して新書化したものです。
*2:この方法を最初に考え出したのは誰か、使い出したのは誰か、という話をしているのではありません。現在では一応それは Pascal だということに落ち着いているのではないでしょうか？ たぶんですけど。
*3:このことに関し、簡単のために、たまたま目についた邦語文献のみを上げると、Dedekind については、「数とは何か、何であるべきか」、『数について』、河野伊三郎訳、岩波文庫、岩波書店、1961年、77-79, 87-88ページ、 『数とは何かそして何であるべきか』、渕野昌訳、ちくま学芸文庫、筑摩書房、2013年、78-79, 88-89ページ、Dedekind の数論についての解説は、足立恒雄、『フレーゲ・デデキント・ペアノを読む』、日本評論社、2013年、100-101ページ、Frege については、『概念記法』、藤村龍雄編訳、勁草書房、1999年、97ページ、および Frege による数学的帰納法の証明に対する解説は、田畑博敏、『フレーゲの論理哲学』、九州大学出版会、2002年、100-101ページを参照ください。また、公理的集合論の公理から、ただちに数学的帰納法が出てくることについては、足立恒雄、『数 体系と歴史』、朝倉書店、2002年、51ページをご覧ください。なお、これらの文献で言及した個所について、私はまだよくわかっていませんので、今後勉強して理解していきたいと思っております。
*4:なっとくシリーズ版でしたら56-57ページです。
*5:ちなみに念のため、題名そのものが「数学的帰納法」となっている次の本を開いてみましたら、その始めあたりに、数学的帰納法がなぜ正しいのかが説明されています。廣瀬健、『数学的帰納法』、教育出版、1975年。しかし以下に記す類いの証明は載っていないように見えます。私が見落としていましたらすみません。
*6:自然数に 0 を含めていないことについては、瀬山先生の本でそうなっているので、それを踏襲したためです。
*7:村田全、『数学史散策』、ダイヤモンド社、1974年、158-159ページ。このページで村田先生は、今本文で述べたのとまったく同じセリフを記しておられるわけではありません。ただ先生はそのページで、次のような主旨のことを述べられていると解せられます。すなわち、歴史上、まず自然数があり、そしてこの自然数の特徴を見ることで数学的帰納法が取り出されたが (Pascal)、やはり歴史上、この関係が逆転し、数学的帰納法がまずあると考え、そしてこの論法から自然数が出てくるのだ、という発想の転換があった (Peano)、と。
