1.8 背理法を使った証明

背理法 (proof by contradiction) とは、示したい命題を偽と仮定すると何らかの偽の命題が証明できることを示す証明技法を言う。偽の命題は定義により真でないので、それが証明できてしまうなら最初に偽と仮定した命題は真でなければならない。背理法は間接証明 (indirect proof) とも呼ばれる。

背理法は常に実行可能なアプローチである。しかし、間接証明という別名が示唆するように、背理法を使った証明は少し複雑になる傾向がある。そのため、可能な場合はこれまでに見てきたような直接的な証明を使う方が一般に望ましい。

命題 \(P\) を背理法で証明するには、次のようにする:

1. 「背理法で証明する」と書く。

2. 「\(P\) が偽だと仮定する」と書く。

3. 偽の命題を導く (論理的矛盾を示す)。

4. 「これは矛盾なので、\(P\) は真である」と書く。

例

背理法を使って \(\sqrt{2}\) が無理数だと示してみよう。復習しておくと、二整数の比に等しい実数を有理数 (rational) と呼ぶ ── 例えば \(3.5 = 7/2\) と \(0.111\ldots = 1/9\) はどちらも有理数である。有理数でない実数を無理数 (irrational) と呼ぶ。

証明 背理法で示す。示したい命題が偽だと仮定する。このとき \(\sqrt{2}\) は有理数なので、\(\sqrt{2} = n/d\) を満たす既約分数 \(n/d\) が存在する。

両辺を二乗すると \(2 = n^{2}/d^{2}\) であり、変形すると \(2d^{2} = n^{2}\) を得る。ここから \(n\) が \(2\) の倍数だと分かる (参照: 問題 1.14, 問題 1.15)。よって \(n^{2}\) は \(4\) の倍数である。一方で \(2d^{2} = n^{2}\) より \(2d^{2}\) は \(4\) の倍数であり、\(d^{2}\) は \(2\) の倍数だと分かる。

以上より \(n/d\) の分母と分子は公約数 \(2\) を持つ。しかし、これは \(n/d\) が既約分数である事実と矛盾する。よって \(\sqrt{2}\) は無理数である。 ■