2009-11-02 [長年日記]
■背理法はなぜ証明になるの? という話
数学ガール/フェルマーの最終定理 (数学ガールシリーズ 2)
- 作者: 結城 浩
- 出版社/メーカー: SBクリエイティブ
- 発売: 2008-07-30
- ASIN: 4797345268
- メディア: 単行本
の第4章は「背理法」でした。
背理法とはなんだったでしょう?
背理法とは《証明したい命題の否定を仮定して矛盾を導く証明法》のことである。
とあります(p98)。
「矛盾を導く」とはなんだったでしょう?
「矛盾を導くというのは、
《Pである》かつ《Pではない》
を示すこと。Pは、どんな命題でも構わない。
でした(p106)。
さて、では、なぜこれが証明になるのでしょう?
という話をしたいと思います。
なのですが……、これを学校で習った覚えがないのです。
を見ても……書いてありませんね。
なので、つらつらと考えていました。そう、ここから書くことは、自分で考えたことです。
なので単純に間違っているかもしれません。お気をつけを。
そのつらつらと考えていたことが、
数学ガール/ゲーデルの不完全性定理 (数学ガールシリーズ 3)
- 作者: 結城 浩
- 出版社/メーカー: SBクリエイティブ
- 発売: 2009-10-24
- ASIN: 4797352965
- メディア: 単行本
を読むことで(「読み返すことで」と書いた方が正確だけど、それはどうでもいい話)形になりました。
それでも間違っているかもしれません(ちょっとしつこいか)。
ある命題Aについて、証明ができるのかどうか? ということを考えます。
- Aだけが証明可能
- ¬A(Aの否定)だけが証明可能
- Aと¬Aの両方が証明可能
- Aも¬Aも証明できない
の4通りです*1。
背理法で命題を証明するには、Aの否定を仮定するのでした。
実は私は「Aの否定を仮定する」という意味を取り違えていたのではないか、と思ったのです。
「数学ガール/ゲーデルの不完全性定理」のp136、公理についてのテトラちゃんとミルカさんの会話から。
「では、数学者がa prioriに公理が真だと仮定したのですね」
「それは違う。真偽は出てこない」とミルカさんは言った。
(略)
「あの、あの、あのですね……
《真である》と《証明されている》は、違う概念
……なんですか?」
の部分です。
もしかして、
「命題Aの否定が真であると仮定する」
ではなくて、
「命題Aの否定が証明可能であると仮定する」
の方なのでは?*2
もう一度書いてみます。
- Aだけが証明可能
- ¬A(Aの否定)だけが証明可能
- Aと¬Aの両方が証明可能
- Aも¬Aも証明できない
元々の公理系で、「2.¬A(Aの否定)だけが証明可能」だったとすると、Aの否定を仮定しても矛盾がでてくるはずはありません。
「4.Aも¬Aも証明できない」でもそうです。
「3.Aと¬Aの両方が証明可能」であれば、もともと矛盾があるわけですから、Aの否定を仮定しても矛盾がでてくるのは当然ですね。しかし、しかしですね、Aの否定を仮定したら出てきた(=背理法の証明のために導き出す)矛盾はAの否定を仮定しなくても出てくるはずです。でもそうはならない。そうはならない《はず》ですね*3。
そうすると残るのは、「1.Aだけが証明可能」です。
はい。
こうやって考えてみれば、Aが証明可能な公理系に¬Aを公理として加えれば(これの意味するところが「命題Aの否定が証明可能であると仮定する」なわけですが)、矛盾が出るのは当たり前ですね。
背理法というのは、つまり、そういうことなのかなぁ、などと考えたわけです。
おしまい。(続きはありません)