どんな命題でも証明できてしまうインチキ背理法について

わたくし わっと（id:watto）はミレニアム懸賞問題の一つにして最難関未解決問題として名高い「P≠NP予想」の証明に成功したことを、ここに宣言する（￣^￣）

ウィキペによると「P≠NP予想」とは次のようなものである。

計算複雑性理論（計算量理論）におけるクラスPとクラスNPは等しくない

この命題が何を意味しているかは、さしあたって詳述しない。今は、この命題の否定をとって命題Aと置く。

命題A：計算複雑性理論（計算量理論）におけるクラスPとクラスNPは等しい

さらに、次の命題Bを置く。

命題B：命題Aと命題Bのうち、どちらか一つだけが真である

はいもうネタがわかっちゃった人がいますね。一応おしまいまで付き合ってください。

スポンサーリンク

命題Aが真であると仮定する。そうすると命題Bは偽でなければならない。なぜなら命題B自身により、命題Aと命題Bのうち真となるのは一つだけだからだ。

だが命題Bを偽とすると、もともと命題Aは真であると仮定したのだから命題Aが真、命題Bが偽であるので、命題Bの内容は真となる。つまり命題A、Bとも真になってしまう。

これは矛盾である。

だから命題Aを真と仮定したことが間違いで、命題Aは偽でなければならない。

そうすれば、命題Bが真であっても偽であっても矛盾は発生しない。命題Bが真であれば、命題Aが偽、命題Bが真ということで、矛盾は発生しない。命題Bが偽であっても、命題A、命題Bとも偽ということで、やはり矛盾は発生しないからだ。

かくして背理法により、元の命題「クラスPとクラスNPは等しくない」が真であることが証明された（証明終わり）

 もちろんこれは

これが証明になるなら、命題Aにどんな命題を入れても証明できることになる。ゴールドバッハ予想だってリーマン予想だって、何だっていいのだ。それどころか命題Aに、否定形にする前のP≠NP予想「計算複雑性理論（計算量理論）におけるクラスPとクラスNPは等しくない」を代入すると、P≠NP予想の否定が証明できてしまうことになる。

要するにこれは、命題Aではなく命題Bが間違っているのだ。より正確には、命題Bに矛盾のタネが仕込まれているのだ。

矛盾のタネというのは、自己言及のことである。「クレタ人のパラドックス」という名称で古くから知られた、次のような命題Cがある。

命題C：命題Cは偽である。

検証するまでもないが念のため。もし命題Cを真と仮定すると、命題C自身の内容により命題Cは偽でなければならない。しかしもし命題Cを偽とすると、命題Cの否定が成立するので命題Cは真でなければならない。だから、どちらにしても矛盾が発生する。

ただこのような命題C単独の場合は「命題Cは決定不能または無意味」ということでうっちゃっておけばいいが、今回の命題Aのように別の命題を巻き込んだ命題を作り、命題Aの真偽により矛盾が発生するかしないかが分れるようにすると（より正確には、もともと矛盾が発生する命題を評価するか評価しないか分れるようにすると）、一瞬でも「あれっ？」と思うような文章が作れないかなと思ったのだ。

プログラム言語（もどき）で書くとしたら、こんな感じかな。

if（"（任意の）命題A" == true）{

　 矛盾が発生する命題Bを評価する ;

} else {

　 矛盾が発生する命題Bを評価しない ;

}

さらにもっとネタバラすると、元ネタは3月29日のエントリーに「問題70.」として引用した問題です。この問題を引用するに際し、改めて読み返してみて「興味深い味わいだな」と感じたので、たぶん改悪にしかならないだろうなと思いながらも、いじってみたくなったんですすみません。

どこに興味深さを感じたかというと、「矛盾が発生する」という言い回しである。

人間は偽である命題をいくらでも作ることができる。早い話がウソをつこうと思えばいくらでもウソをつくことができる。それと同様に、人間はもともと矛盾する命題を作ることだってできるのだ。

しかし我々は、偽である命題に慣れているほどには、矛盾する命題には慣れていないんじゃないかな？

ぶっちゃけ政治家が選挙前に公約でどんなことを言おうと、言葉を額面通りに受け取る有権者は稀だろう。しかし数学の背理法は学校で習うとはいえ、一般の人にとって政治家の公約ほどには日常生活でなじみがあるわけじゃないと思う。つまりその分ナイーブなのだ。

だから実はうそでも「矛盾が発生する」という文言には、ダイレクトに「うそです」と言われるより重みを感じさせるちょっとした魔力があるんじゃないだろうか？ そんなふうに感じるのは私だけかな？

もしそういう心理作用が一般的なら、もっと巧妙なインチキ証明を作れるんじゃないかなとも思ったが、今のところは無理でした。

もう一つ思ったことは、例としては今回のインチキ背理法より元の3月29日エントリー中「問70.」の方が適切だとは思うのだが、命題の真偽が現実の担保とならないように、命題の矛盾・無矛盾もまた現実の担保とならないのだな、ということである。

3月29日のエントリーに引いた問題の例では、「この小箱の中に肖像画はない」というラベルを貼った小箱の中に肖像画を入れることがいくらでもできるように、「この小箱の中に肖像画があるとすると ≪略≫ のような理由で矛盾が発生する」と推定できる小箱の中に肖像画を入れることだって、いくらでもできてしまうのだ。

当然と言えば当然なのだが、どこか変な気分が残る。背理法と現実の関係まで議論を広げると、収集がつかなくなっちゃうかな。

オチ代わりに、昔考えたくだらない小話を貼ってみよう。ネットのそこかしこに貼ったのだが、全然うけなかった。

天竺を目指す玄奘三蔵法師一行の目の前に、妖怪が現れた。

「お前たちが天竺にたどり着くことができないことを、背理法を用いて証明してやろう。

お前たちが天竺に着いたと仮定する。だがそれで飢えや病に苦しむ人たちがいなくなるかな？ そうではあるまい。貧富の差も相変わらず存在するだろう。権力者や役人たちの暴虐もなくなるまい。これらは矛盾だ。矛盾が存在するということは、仮定が間違っているということだ。しかるによって、お前たちが天竺に行くことは不可能であると証明された」 

悟空、妖怪をぶん殴る。

長々と伸び伏した妖怪を尻目に何事もなかったかのように旅路を急ぐ玄奘と悟空の背中に向かって、かろうじて半身を立てなおした妖怪が叫ぶ…

「待て！ 今度は数学的帰納法で証明してやる」

この本の名は?: 嘘つきと正直者をめぐる不思議な論理パズル