背理法と対偶証明法(MT)の関係とは？
なんかいきなり数学関連カテゴリ書くのもなんだけど、気になり過ぎているのでここに書く。
発端は、田崎晴明氏の日記↓
http://www.gakushuin.ac.jp/~881791/d/1104.html#01
ここに、下のような記述がある。（以下引用）
「……たとえば「ルート 2 が無理数であること」の証明に背理法（というか排中律）は本質的ではないと教わって……」
ルート２の無理数性の証明法は、偶奇による有名なものにせよ素因数分解によるものにせよ、何らかの形で背理法を背景とするものしか知らなかったので、公開されている田崎氏の「数学―物理を学び楽しむために―」の該当部分を読んでみることにした。
すると、（詳しい転載はあえて避けるが）
「(n/m)=4^(p-q)×(奇数)なので、有理数の2乗は整数ならば４の倍数または奇数である。よって、有理数の2乗は2とはなりえず、ルート２は無理数である。」
とあった。
とりあえず、今までに見たことのない証明法で、かなりすっきりとした証明のように思われる。
ただ、これを読んだとき俺は
『結局これは「有理数の二乗は４の倍数または奇数である。」かつ「２は４の倍数でも奇数でもない。」という二つの命題から、MT(Modus tollens)によって「ルート２は有理数でない＝（ルート２は無理数である）」を推論したということであり、つまり対偶証明法によっている。と、いうことは、最終的に背理法を元に証明されたということになってしまっているのでは……』
と考えてしまったのである。
しかし、そこに思い当ってふと疑問に思ったのは、「俺は対偶論法と背理法を論理的には同値だと思い込んでいるが、それは正しいのだろうか？」ということ。
そこでまあ調べてみると、質問サイトでこのことについての議論があったり、田崎氏の件のテキストにも背理法に関する記述を見つけたりしたので、ここにまとめておく。
[1]
まず、対偶証明法と背理法の抽象的・形式的な記述はどうなるのかということについて。
対偶証明法とは、ある命題とその対偶が論理的に同値*1であることを用いた、以下のような論証形式です。
(F0)
ただし、このままでは対偶証明法は「PならばQ」という形式の命題しか示せない。そこで、次のように一般の命題Pの証明に適用できる「モーダス・トレンス(MT)」*2という形式に書き換える。（参考：Wikipedia「モーダストレンス」http://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%BC%E3%83%80%E3%82%B9%E3%83%88%E3%83%AC%E3%83%B3%E3%82%B9）
(F1)
一方背理法とは、「Pが真であることを仮定して矛盾が示されれば、Pは偽である」と一般的に表現されますが、これを形式的に表現すれば
(F2)
となります。*3
[2]二つの証明法の関係について
上の形式的に表現された二つの証明法(F1)(F2)を見比べると、どうやら「対偶証明法」とは「背理法」の特殊化といえるのではないかと思われる。ともかく、明らかに「論理的に同値」ではない。対偶証明法では（Pの真偽にかかわらず）「Qでない」という命題が必要なのに対し、背理法ではこれの代わりに「PならばQでない」を示せばよいということになる。
[3]この二つを混同してしまう要因とは？
まず、普段「背理法による証明」とされている証明の、かなり多くが「対偶証明法による」に書き換えられてしまうからだと思われる。
背理法で導く「矛盾」とは「QでありQでない」ということであるが、例えば次の有名な証明を例にみてみる。
・ルート２を有理数だと仮定すると、p,qを互いに素な整数として「2=p^2/q^2」すなわち「2×q^2=p^2」が成り立ち、pが偶数ということになるが、そうすると「p=2×r」と置くことにより「q^2=2×r^2」となり、qも偶数となる。これは、p,qが互いに素であることと矛盾する
この証明に用いられている「矛盾」は、すべて背理法の「仮定」に関係なく成立する。二つの偶数は絶対に互いに素でない。
したがって、例えばこの証明は次のようにモーダス・トレンスの形式の証明に書き換えられる。
あるいは、もっと対偶証明らしく
と書き換えてもよいだろう。（「対偶」の前提は常に真である。）
つまり、背理法で示す「矛盾」を成している「Q」と「¬Q」のうち、もし片方が無条件で成り立つなら、それは本質的には対偶証明法と全く同じであるというわけだ。そして、実際「片方が仮定に依存しない」背理法の証明は実に多いように思われる。
[4]では、「背理法での証明のうち、対偶証明法に書き換えられない証明」はあるのか？*4
要は、「PならばQ」「Pならば¬Q」の「Q」「¬Q」がどちらも普遍的に成り立つような命題でなければよいのである。例えば次の有名な証明を考える。
・素数が有限個しかないとする。
N=「素数すべてをかけ合わせた数＋１」を考えると、
素数が有限個と仮定したことによりNは合成数であるが、
仮定よりNはどんな素数で割っても1余るのでNは1とN自身以外の自然数で割り切れない。よって、Nは素数である。
これは矛盾である。
一応断っておくが、件の田崎氏のテキストでも言及されているように、この「素数が無限に存在することの証明」自体は、背理法によらない証明法が存在する。
そうではなくてここで言いたいのは、この証明は『「PならばQ」かつ「Pならば¬Q」よって¬P』という形になっているが、さっきと同じように対偶証明法（あるいはMT）の形式にそのまま書きかえることはできないということである。なぜなら、「Nが素数である」というためにも、「Nが合成数である」というためにも仮定を用いているからである。
そんなこんなで、結局二つの証明法は似て非なるもの、もっと正確に言えば背理法の特殊な場合を対偶証明法というのだろうという結論に至った。
俺が高校で習った、また解いた問題に現れた「背理法」も、思い返せば結局「本質的には対偶証明法と変わらない」背理法がほとんどだった気がする。
背理法を教えるときに、もっと「矛盾とは何か」を詳しくやるべきなのではないかと思ったけど、結局この二つの証明法が比較され、その違いとは実はこういうところに存在していたなんてことを習っても、実際的な役には立たないのだからこれでいいのだろう。（結局、本質云々よりも「どちらの方が証明としてより明快な記述か」という問題の方が、高校受験でも重要視されて然るべきだとは思うし）
久しぶりに真面目なことを書いたので疲れた……
（ ;-ω-）ﾉｼ
*1:ここでは論理体系として古典論理の体系を採用した議論をしていきますが、例えば直観主義論理の体系など、元の命題とその対偶との真偽が必ずしも一致するものではないとしている（すなわち排中律を仮定しない）論理体系も存在します。
*2:似た名称かつ有名なものに「モーダス・ポネンス(MP)」があるが、別物である。
*3:「矛盾を導く」とは「Qであり、かつQでないことを示す」ことであるから、このような形式的記述でよいだろう
*4:ググると「対偶証明法では『pならばq』の形式しか証明できない」とかいてある資料が見つかったが、上で見たようにモーダストレンスの形式を用いれば（つまり、前提として普遍的なものを選べば）その形式には限らない。第一、「ルート２は無理数である」はこの形式ではない。
