「AならばB」証明の書き方、直接法、対偶法、背理法

どうも、木村（@kimu3_slime）です。

今回は、「AならばB」という形の命題の証明の書き方3種類、直接法、対偶法、背理法を紹介します。

「AならばB」を直接法で示す

「AならばB」を直接法で証明すること（direct proof）は、一番素直な方法です。すなわち、Aであることを仮定して、そこからBを導くことです。やってみましょう。

Aに該当するのは「\(x\)が偶数」で、Bに該当するのは「\(x^3\)が偶数」ですね。

「\(x\)が偶数ならば」という言い方をしているので、「\(x\)は整数である」と暗黙のうちに仮定されていることに注意しましょう。通常、整数\(x\)に対して偶数であるかどうかは議論されます。

さて、これを証明しましょう。

Aが正しいと仮定します。すなわち、\(x\)が偶数であることを仮定します。

偶数の定義より、\(x=2k\)となる整数\(k\)が存在します。

両辺を3乗しても等式は等しいので、\(x^3 = (2k)^3\)です。

右辺を計算すれば、\((2k)^3=8k^3 =2\cdot  (4k^3)\)が成り立ちます。

\(\ell= 4k^3\)と置くと、整数同士の積は整数なので\(\ell\)は整数であり、\(x^3 = 2 \ell\)と表せます。

よって、偶数の定義より、\(x^3\)であること、Bが正しいことが示せました。

直接法の証明は、およそ次の形を取ります。

出発点をAとして、そこから確かにわかる事実\(C_1,C_2,\dots,C_k\)を積み上げていき、そこからゴールBを導くのが証明です。

上の具体的な証明では、証明の中身\(C_1,C_2,\dots,C_k\)を示すために、偶数の定義、等式の性質、べき乗の定義、整数の性質などを用いました。こうした基本的でよく知られた事実を用いて、Bが正しいことを段階を踏んで述べましょう。

「AならばB」を対偶法で示す

「AならばB」を、直接法でなく示す方法があります。そのひとつが、対偶によって証明する方法（contrapositive proof）です。

「AならばB」の対偶とは、「Bでない ならば Aでない」という命題です。ある命題とその対偶の真偽は常に一致することが知られています。

そこで、対偶「Bでない ならば Aでない」が正しいことを示して、それによって「AならばB」が正しいことを示すという方針です。

具体的にやってみます。

Aは「\(x^2\)が奇数」、Bは「\(x\)は奇数」に対応します。

これを直接法で示そうとして、\(x^2 =2k+1\)と置いてみます。平方根を取れば\(x =\sqrt{2k+1}\)となるわけですが、これが奇数となるかはただちにわかりません。\(x^2 =2k+1\)と表される時には\(k\)に条件がつき、そこから\(\sqrt{2k+1}\)が奇数となることを示す必要があります。できないわけではありませんが、面倒です。

そこで、対偶が示せないか考えてみます。

Aでないとは「\(x^2\)は偶数」、Bでないとは「\(x\)は偶数」です（すべての整数は奇数または偶数に分かれます。偶数でない数は奇数であり、奇数でない数は偶数）。したがって、対偶は「\(x\)は偶数ならば、\(x^2\)が偶数」です。これを示しましょう。

\(x\)を偶数であると仮定します。

偶数の定義より、\(x=2k\)となる整数\(k\)が存在します。

両辺を2乗しても等式は等しいので、\(x^2=(2k)^2\)です。

計算により\((2k)^2 = 2 \cdot 2k^2\)が成り立ちます。

\(\ell = 2k^2\)と置くと、\(\ell\)は整数の積なので整数で、\(x^2 =2 \ell\)が成り立ちます。

よって、偶数の定義より、\(x^2\)は偶数です。

対偶が示せたので、「\(x^2\)が奇数ならば、\(x\)は奇数である。」ことが示せました。

対偶による証明は、次の形を取ります。

同じ真偽を表す命題でも、「AならばB」と「BでないならばAでない」は、場合によって示しやすさが違います。直接示そうとしてうまくいかないときは、対偶を使って言い換えてみると、簡単に示せることもあるでしょう。仮定Aが複雑な形、結論Bが単純な形のときは、対偶を使うと議論しやすいです。

対偶「BでないならばAでない」を、逆「BならばA」と混同しないように注意しましょう。「AならばB」とその逆には、真偽の対応関係は一般にありません。

例えば、「\(x\)が4の倍数ならば\(x\)は2の倍数」は正しい命題です。しかし、その逆「\(x\)が2の倍数ならば\(x\)は4の倍数」は偽の命題です。\(x=2\)は2の倍数ですが、4の倍数ではありません（倍数とは整数倍を考える）。

対偶「\(x\)は2の倍数でないならば\(x\)が4の倍数でない」は、もとの命題と真偽が一致して正しいです。

「AならばB」を背理法で示す

「AならばB」を直接的でなく示すもうひとつの方法が、背理法（proof by contradiction）です。

Aであることを仮定し、さらに結論Bが偽であると仮定すると、ある矛盾（contradiction）を導いてしまうことを示します。結論Bは真または偽ですが、偽である可能性が否定されたので、Bは正しいと示せた、という仕組みです。

具体的にやってみましょう。

Aは「\(x^2\)が奇数」、Bは「\(x\)は奇数」に対応します。Bでないは「\(x\)は偶数」です。

「AならばB」を背理法によって示しましょう。

すなわち、\(x^2\)が奇数であり、かつ\(x\)が偶数であると仮定します。

奇数の定義から、\(x^2 =2k+1\)となる整数\(k\)が存在します。

偶数の定義から、\(x=2\ell\)となる整数\(\ell\)が存在します。

\(x=2\ell\)を2乗すると、\(x^2 =4 \ell ^2\)が成り立ちます。

これらの結果を合わせれば、\(4\ell ^2 = 2k+1\)が成り立ちます。

しかし、\(4\ell ^2\)は偶数であり、\(2k+1\)は奇数です。

偶数でありかつ奇数である数は存在しないので、\(4\ell ^2 \neq 2k+1\)が成り立ちます。

\(4\ell ^2 = 2k+1\)と\(4\ell ^2 \neq 2k+1\)が両方成り立つのは矛盾です。

よって、「\(x\)が偶数である」という仮定は偽で、「\(x\)が奇数である」ことが示せました。

背理法による証明は、次の形を取ります。

今回は「AならばB」でBの否定から矛盾を導くという方法を紹介しました。

単に「Aである」ことを示すために、「Aでない」と仮定して矛盾を導くことも背理法と呼ばれます。例えば、\(\sqrt{2}\)が無理数であることを証明するために、\(\sqrt{2}\)が有理数であると仮定して議論する方法は有名です。（背理法の他の例としては、素数が無限に存在すること、カントールの対角線論法など）

対偶による証明では、「AならばB」と「BでないならばAでない」が論理的に等価（同値）であることを利用しています。背理法による証明は、「AならばB」と結論の二重否定「Aならば「「Bでない」でない」」が等価であることを使っているわけです。

数学者のハーディは（ユークリッドによる）背理法を、「数学者の最高の武器の一つ」と形容しています。背理法は便利である一方で、直接法や対偶法に比べて、証明が単純でないように見えることがあります。

例えば、構成主義（constructivism）と呼ばれる立場からは、背理法により何かの存在を証明する議論は不十分であり、直接にその存在を構成する必要がある、とされます。

これは数学のひとつ捉え方（哲学）ではありますが、普通に数学の証明を書くにあたり、背理法自体を避ける必要はないと思います。証明が書けるならばその手段として背理法を使ってみて、その後に背理法を避けられるかどうか考えると良いでしょう。

以上、「AならばB」の示し方として、直接法、対偶法、背理法を紹介してきました。

同じ命題の示し方としても、文字通りにそのまま示すやり方と、対偶や二重否定を使って言い換えるやり方、どちらを取っても良いです。

事実にたどり着く道は唯ひとつではなく、簡単な道も難しい道もあります。ぜひ工夫しながら証明の方法に慣れてみてください。

木村すらいむ（@kimu3_slime）でした。ではでは。

Book of Proof

posted with AmaQuick at 2021.02.09

Hammack, Richard H(著)
Richard Hammack (2019-07-19T00:00:01Z)

￥3,378

Amazon.co.jpで詳細を見る

こちらもおすすめ

数学の証明とは何か、なぜ必要なのか？

「AならばB」のよくある誤解から学ぶ、論理学入門（対偶、逆、否定、真偽表）

素数の性質：無限にあること、素因数分解の一意性と応用

無限集合の濃度とは？ 写像の全単射、可算無限、カントールの対角線論法

偶数+奇数はいつでも奇数？ 読み解き方、よくある間違いと証明