第2章集合と命題｜第24節

背理法と証明の選び方

示したい命題の否定を仮定し、矛盾を導くのが背理法です。直接証明・対偶・背理法の使い分けも確認します。

25〜35分｜背理法・証明法の選択

前の節から

対偶に続いて、結論の否定を仮定して矛盾を導く背理法を学びます。命題に応じて証明法を選びます。

まず考えてみよう

「

\sqrt{2}

は無理数である」を直接示しにくいとき、反対の「有理数である」を仮定すると、どのような矛盾を目指せるでしょうか。

直接証明

仮定から結論へ、そのまま式を進められる

対偶

結論の否定から仮定の否定へ進む方が具体的

背理法

結論の否定を仮定すると、既知の事実と両立しない

背理法

否定を仮定して矛盾を導く

命題 $P$ を証明したいとき、 $P$ が成り立たないと仮定します。その仮定から既知の事実と両立しない結論が出れば、仮定が誤りなので $P$ が真だと分かります。

背理法
1. 結論の否定を仮定する。
2. 仮定から論理的に式を進める。
3. 矛盾を導く。
4. 最初の仮定が誤りと結論する。

代表例

$\sqrt{2}$ は無理数である

証明 $\sqrt{2}$ が有理数だと仮定する。

$\sqrt{2}$ が有理数なら、互いに素な正の整数 $p, q$ を用いて、

\sqrt{2} = \frac{p}{q}

と書けます。2乗して、

2 q^{2} = p^{2}

したがって $p^{2}$ は偶数であり、第23節の結果から $p$ も偶数です。 $p = 2 k$ と置くと、

2 q^{2} = 4 k^{2} \Rightarrow q^{2} = 2 k^{2}

よって $q$ も偶数です。

すると $p, q$ はともに2の倍数となり、互いに素という仮定に反します。したがって $\sqrt{2}$ は無理数です。

矛盾を明確にする

何と何が両立しないのかを書く

上の証明では、

「

p, q

は互いに素」　と　「

p, q

はともに偶数」

が矛盾しています。背理法では、最後にこの点を明確にします。

証明法の選び方

式にしやすい方向を選ぶ

方法

使いやすい場合

直接証明

仮定からそのまま結論へ式変形できる。

対偶

結論の否定を仮定すると具体的な形に書ける。

背理法

「〜でない」ことや不存在を直接示しにくい。

「偶数 $n$ なら $n^{2}$ は偶数」は $n = 2 k$ と置けばすぐ示せるので直接証明が簡単です。「 $n^{2}$ が偶数なら $n$ は偶数」は対偶が使いやすく、「 $\sqrt{2}$ は無理数」は背理法が自然です。

もう一つの背理法

有理数と無理数の和

例題有理数 $r$ と無理数 $α$ に対して $r + α$ は無理数である。

$r + α$ が有理数だと仮定します。 $r$ も有理数なので、二つの有理数の差

(r + α) - r = α

も有理数になります。しかし $α$ は無理数としたので矛盾です。したがって $r + α$ は無理数です。

証明で注意すること

仮定と結論を混同しない

対偶を使うなら対偶の仮定から対偶の結論へ、背理法なら否定した仮定から矛盾へ進みます。途中で元の結論を使うと、証明したいことを前提にしてしまう場合があります。

また、背理法では最後に「何と何が矛盾したのか」を書くと論理が明確になります。

練習問題

1. 背理法では最初に何を仮定するか。

問1の答えを見る

考え方：示したい結論が成り立たないと仮定し、そこから矛盾を導きます。

示したい命題の否定。

2. 「偶数 $n$ なら $n^{2}$ は偶数」はどの証明法が簡単か。

問2の答えを見る

考え方： $n = 2 k$ とおけば $n^{2} = 2 (2 k^{2})$ とそのまま示せるため、直接証明が簡単です。

直接証明。

3. 「 $n^{2}$ が偶数なら $n$ は偶数」はどの証明法が使いやすいか。

問3の答えを見る

考え方：対偶「 $n$ が奇数なら $n^{2}$ も奇数」を式で示しやすいため、対偶を使います。

対偶による証明。

4. $\sqrt{2}$ の証明で得られる矛盾を答える。

問4の答えを見る

考え方：既約分数としたのに分子と分母がともに偶数となり、互いに素という仮定と矛盾します。

$p, q$ を互いに素としたのに、 $p, q$ がともに偶数になること。

5. 背理法で矛盾が出たあと、何が結論できるか。

問5の答えを見る

考え方：矛盾の原因は最初に置いた否定の仮定なので、その仮定が誤りだと結論します。

最初に置いた否定の仮定が誤りであり、元の命題が真である。

6. 有理数 $r$ 、無理数 $α$ について $r - α$ は有理数か無理数か。

問6の答えを見る

考え方：有理数だと仮定すると、無理数 $α$ が有理数どうしの差になってしまいます。

無理数。有理数だと仮定すると $α = r - (r - α)$ が有理数になり矛盾。

7. 「 $\sqrt{3}$ は無理数」を証明するなら、直接・対偶・背理法のどれが自然か。

問7の答えを見る

考え方：有理数だと仮定して既約分数で表すと矛盾を導けるため、背理法が自然です。

背理法。

第2章のまとめ

集合は条件を満たすものの集まりとして扱う。
命題の真偽は反例や包含関係から判断できる。
必要条件・十分条件は二方向の「ならば」で調べる。
証明では直接・対偶・背理法を使い分ける。

前後の節