alchemist_380 のひとりごと

元・水の分析屋さんがブツブツ言います

徒然なるままに「数学的帰納法」

少しのことにも、先達はあらまほしきことなり (徒然草 第五十二段)

 

簡単そうなことでも教えてくれる先輩はいてほしいもの。「数える」という行為はとても簡単なことのようですが、「人間の精神構造と不可分である」と、どこかに書かれておりました・・・おりましたが、数えるのは人間だけなのでしょうか。

鳥は、巣の中に4つ卵があるとき、1つ取り除いて平気であっても、2つ持って行かれるとたいてい巣を放棄するそうです。鳥は2と3の区別はできるが、4はうまく認識できないのでしょうか。忘れっぽい人のことを、3歩歩くとすべてを忘れるトリ頭だとか言いますが、3あたりの数が何らかの境界になっているのかも知れません。
英語の "thrice(i)" には、「三たび」「3倍」のほかに「幾度も」「大いに」という意味があります。じゃあ、once, twice, thrice ってやると、「いち、に、たくさん」になるのですね(大笑)。ホントは、昔から3以上は数えられなかったんじゃないかな?

(i) 1回、2回、3回 → once, twice, "thrice" で間違いではないですが、"three times" がふつうなんだそうです。元・水の分析屋さんは英会話に難があるので、まあ、どっちでも構いません。

「十億」は分かりにくいから「億」にした話も紹介しました(2023/12/21)。もっとも「億」なら数えられるゾ、という訳でもないのですが。


結論です: 程度の差こそあれ、みんなトリ頭に違いない。

 

さて、「数える」の基本は自然数。今回は数学噺で「ペアノの公理」から始まりです。
※「数学ガール」シリーズの「ゲーデル不完全性定理」を参考にしています。

 

ペアノの公理(Peano axioms)とは

まずは書いてしまいましょう。そこからゆっくり考える・・・

==================================================
PA1 1 は自然数である
PA2 どんな自然数 n に対しても、後続数 n' は自然数である
PA3 どんな自然数 n に対しても、n'≠ 1 である
PA4 どんな自然数 n, m に対しても、n' = m' ならば n = m である 
PA5 自然数 n に関する述語 P(n) について、次の (a), (b) が成り立つとする:
   (a) P(1) である
   (b) どんな自然数 k に対しても、P(k) であれば P(k') である
   このとき、 どんな自然数 n に対しても P(n) である
==================================================

最後の5番目は違った書き方もあるはずですが、ここでは自然数の「集合」と言わない表現。


○ PA1 は、とにかく 1 という自然数があると言っています。この 1 が一つだけ存在するとは言っていないことに注意しましょう。
○ PA2 は、どんな自然数にも後続数があって、それも自然数であると言っています。加法が定義されてないので、n の後続数が(私たちが知っている)n+1 だなんて言っていないことに注意しましょう。
○ PA3 は、1 はどんな自然数の後続数でもない、と主張しています。ただし、ここまでの決まり事では「大小関係」も定まってないので、1 が最も小さい自然数であると解釈するのは早計だということになります。気をつけましょう。
○ PA4 は、後続数が等しくなる数は互いに等しいという意味で、n' が n の後続数であり、かつ、n と異なる a の後続数でもある、という可能性を消しています。これである自然数から後続数への道筋をただ一つに限っています。別のどこかから合流することはできませんし、PA3 により 1 はどんな自然数に対しても後続数になれないので、1 以外のどんな自然数からも始まらないようになっていることにも注意です。

・・・ここまでの話、大丈夫ですか。自然数全体の集合を構成しようとしていることが分かっているからこそ言えるのですが、とても巧妙な定め方ですね。

○ PA5 は、無数にある自然数について何らかの主張ができるように、「数学的帰納法」を用意していると言えそうです。

 

数学的帰納法でつまずきませんでしたか?

さて、PA5 は数学的帰納法をどのように定めているのか。述語 P(n) は「n が満たすある性質」に関する記述で、具体的な n を与えると真偽が定まるもの(命題 proposition)を言います。PA5 の主張は、「(a) まず 命題 P(1) を証明して、(b) 命題 P(k) が成立すれば P(k') も成立することを示せば、すべての自然数 n について命題 P(n) が成立することが証明されたことになる」です。ごちゃごちゃしてますね。同じことを繰り返しているみたいですから。

で、理解を助けるためによく引き合いに出されるのがドミノ倒しです。

ドミノ倒しはゲーム的だが、将棋倒しだと事件性が感じられるのはなぜ?

証明したいことは「一列に並んだすべてのドミノは倒れる」(ii) です。二つのステップを乗り越えましょう:

  (a) 最初のドミノは倒れる

  (b) k 番目のドミノが倒れるならば k' 番目のドミノも倒れる

※ このドミノ倒しは失敗がなくて、あるドミノが倒れたらその次のドミノも倒れる、ということです

ここまで証明できればすべてのドミノは倒れる。私はこれで「うんうん、なるほど」でした・・・

(ii) すべての、って簡単に言ってますが、このドミノの列はどこまでもどこまでも続きます。終わりがないことをお忘れなく。

でも、これで「すべての自然数について成り立つ」証明になっているのか、という疑問が沸いて、つまずいて、「数学的帰納法」はインチキ臭いと思う人が出てくるそうです。その疑問を解消する手助けができるかどうか、ちょっと説明してみます:

ここが一番引っかかるのだと思いますが・・・

(b) どんな自然数 k に対してもP(k) であれば P(k') である

赤字の下線部分に注意です。句点を打ってあるのだから、そのように読んでください。素直に読めば間違えようがないと私は思うのですが、下のどちらが正しいでしょう:

◇ どんな自然数 k に対しても「P(k) であれば P(k') である」

◇  「どんな自然数 k に対しても P(k) であれば」P(k') である

もちろん、上の区切り方が正解です。下のように読んでしまうから、前提にしたことを証明しようとしているような気分になるのではないでしょうか。

家庭教師やってた経験からしても、書いてあることが読み取れないために国語の成績が伸びない子はよくいました。問題文が読めないと、算数、数学も・・・推して知るべし。少しのことにも、先達はあらまほしきことなり、ですぅ。

 

受験生の皆さん、このブログを読んでもらえたらだけど、とにかく読み取れ。とにかく頑張れ。Good Luck.