前回の記事で説明したように,「『$X$が成り立たない』と仮定して矛盾を導くことができれば,この仮定は誤りで『$X$が成り立つ』ことが分かる」という論法が背理法なのでした.
簡単に言えば,もしあなたが誰かの嘘を暴きたければ,相手の発言から矛盾を引き出せばいいわけで,背理法はこの考え方で「嘘であること」を証明しているわけですね.
前回の記事では具体的に背理法によって
- 整数$a$に対し,$a^2$が偶数なら$a$も偶数であることを示せ.
- $\sqrt{2}$は無理数であることを示せ.
の2つを証明しましたが,実際の試験でこの2問が出題されて「背理法を使おう!」と思えないと困ります.
そこで,この記事では
- 背理法が有効な証明問題の特徴
- 背理法を用いる他の証明問題の具体例
を説明します.
一連の記事はこちら
【論理と集合1|「集合」は数学の共通語!集合の基礎知識】
【論理と集合2|補集合の計算は「ド・モルガンの法則」】
【論理と集合3|「必要条件」「十分条件」は論理のド基本】
【論理と集合4|命題を集合を使って考える超便利な方法】
【論理と集合5|対偶はどういう時に使う?対偶の性質】
【背理法1|背理法はこう考える!仕組みを具体例から理解する】
【背理法2|背理法が使える証明問題のたった1つの特徴】←今の記事
背理法が有効な証明の特徴
背理法が有効な証明問題の特徴はただ一つで「証明したいことを否定するとシンプルになる証明」です.
その具体例としてよくあるのは
- 否定の証明
- 「少なくとも〜」の証明
- 対偶が簡単に示せる証明
です.
もちろんこれら以外でも背理法が有効な証明問題もありますが,とくに1つ目の「否定の証明」と2つ目「『少なくとも〜』の証明」の2つタイプの証明で背理法は鉄板なので,しっかり意識しておくとよいでしょう.
また,3つ目は対偶と背理法が実は本質的に同じ論法であることに基づくのですが,少しややこしいのとこの記事の趣旨に沿わないでここでは説明しません.
前回の記事で扱った以下の2問をみてみましょう.
次の問いに答えよ.
- 整数$a$に対し,$a^2$が偶数なら$a$も偶数であることを示せ.
- $\sqrt{2}$は無理数であることを示せ.
(1)の対偶は「$a$が奇数なら$a^2$も奇数である」で,これは簡単に証明できますから,背理法を用いても証明することができます.
なお,もちろん対偶が証明して証明終了としても何も構いません.
(2)は一見否定の証明に見えないかもしれませんが,そもそも無理数の定義が「有理数でない実数」でしたから,(2)は「$\sqrt{2}$は有理数でないことを示せ」ですから,否定の証明となっていますね.
とくに「否定の証明」と「『少なくとも〜』の証明」では背理法が有効にはたらくことは非常に多い.
背理法が有効な他の証明問題
もう少し背理法が有効な証明問題の例を考えましょう.
次の問いに答えよ.
- 実数$x$, $y$が$x+y>0$を満たすとき,$x>0$または$y>0$が成り立つことを示せ.
- 実数$x$, $y$, $z$が$xyz=0$を満たすとき,$x$, $y$, $z$の少なくとも1つは0であることを示せ.
- 整数$a$, $b$は等式$a^2+2=4b$を満たし得ないことを示せ.
- $a$, $b$が無理数なら,$a+b$と$a-b$の少なくとも一方は無理数であることを示せ.
- 素数が無限に存在することを示せ.
- $\tan{1^\circ}$は無理数か(2006 京大).
例1
実数$x$, $y$が$x+y>0$を満たすとき,$x>0$または$y>0$が成り立つことを示せ.
対偶を簡単に示すことができるので,背理法でも証明できますね.
この問題の対偶による証明は以下の記事を参照してください.
対偶について「命題$P\Ra Q$の真偽と,この対偶$\overline{Q}\Ra\overline{P}$の真偽が一致する」という便利な性質があります.この性質を使って具体的に証明問題を解きます.
背理法により示す.
すなわち,「$x>0$または$y>0$」の否定「$x\le0$かつ$y\le0$」が成り立つと仮定して矛盾を導く.
この仮定より$x+y\le0+0=0$だから,$x+y>0$に矛盾する.
よって,仮定「$x\le0$かつ$y\le0$」が誤りなので,「$x>0$または$y>0$」が成り立つ.
例2
実数$x$, $y$, $z$が$xyz=0$を満たすとき,$x$, $y$, $z$の少なくとも1つは0であることを示せ.
「『少なくとも〜』の証明」なので背理法をまず試したいところです.
背理法により示す.
すなわち,「$x$, $y$, $z$の少なくとも1つは0」の否定「$x$, $y$, $z$はいずれも0でない」が成り立つと仮定して矛盾を導く.
この仮定より$xyz\neq0$だから,$xyz=0$に矛盾する.
よって,仮定が誤りなので「$x$, $y$, $z$の少なくとも1つは0」が成り立つ.
例3
整数$a$, $b$は等式$a^2+2=4b$を満たし得ないことを示せ.
「否定の証明」なので背理法でまず試したいところです.
背理法により示す.
すなわち,「整数$a$, $b$が等式$a^2+2=4b$を満たす」と仮定して矛盾を導く.
この仮定より$a^2=2(1+2b)$なので$a^2$は偶数だから,$a$も偶数となる.
よって,$a=2k$ ($k$は整数)とおけるから,$a^2=2(1+2b)$に代入して
となる.しかし,左辺$2k^2$は偶数,右辺$1+2b$は奇数だから矛盾する.
よって,仮定が誤りなので整数$a$, $b$は等式$a^2+2=4b$を満たし得ない.
例4
$a$, $b$が無理数なら,$a+b$と$a-b$の少なくとも一方は無理数であることを示せ.
「『少なくとも〜』の証明」であり「否定の証明」でもあるので,背理法がかなり効果的ですね.
$a+b$と$a-b$がいずれも有理数であると仮定して矛盾を導く.
この仮定から$a+b=\dfrac{q}{p}$ ($p$, $q$は整数,$p\neq0$),$a+b=\dfrac{s}{r}$ ($r$, $s$は整数,$r\neq0$)とおける.
2式の辺々を加えたものと引いたものはそれぞれ
である.$2pr$, $qr+ps$, $qr-ps$はいずれも整数だから$a$, $b$はともに有理数である.
よって矛盾するから,$a+b$と$a-b$の少なくとも一方は無理数である.
例5
素数が無限に存在することを示せ.
実は「無限」の定義が「有限でない」なので,「否定の証明」と考えられます.「無理数」の定義が「有理数でない」と似た感覚ですね.
とはいえ,初見でこれを証明するのは難しいでしょう.
素数が有限個しかないと仮定して矛盾を導く.
このとき,素数を全て並べて$a_1,\dots,a_n$とし,$x=a_1\dots a_n+1$とすると,任意の$i=1,\dots,n$に対して
である.$a_i\ge2$だから$\dfrac{1}{a_i}$は整数でないので,$\dfrac{x}{a_i}$も整数でない.
$x$は$a_i$で割り切れないから,$x$は自身と1でしか割り切れないことになり素数である.
一方,$x>a_1$だから$a_1,\dots,a_n$のいずれとも異なり,$a_1,\dots,a_n$が全ての素数としたことに矛盾する.
よって,素数は無限に存在する.
例6
$\tan{1^\circ}$は無理数か(2006 京大).
(6)は少し三角関数に慣れていれば$\tan{1^\circ}$が無理数になりそうだという直感がはたらくかと思います.
とするなら,「無理数」は「有理数でない」でしたから「否定の証明」となりますね.
$\tan{1^\circ}$が有理数であると仮定して矛盾を導く.
このとき,加法定理より$\tan{(1^\circ+n^\circ)}=\dfrac{\tan{1^\circ}+\tan{n\circ}}{1-\tan{1^\circ}\tan{n^\circ}}$が成り立つ.
$\tan{n^\circ}$が有理数なら,右辺は有理数だから$\tan{(1^\circ+n^\circ)}$も有理数である.
また,仮定より$\tan{1^\circ}$は有理数だから,数学的帰納法により任意の自然数$n$に対して$\tan{n^\circ}$は有理数である.
一方,$\tan{30^\circ}=\frac{1}{\sqrt{3}}$は無理数なので,矛盾する.
よって,$\tan{1^\circ}$は無理数である.
なお,「$\sqrt{3}$が無理数であること」の証明は「$\sqrt{2}$が無理数であること」の証明と同様に示すことができるので,前回の記事を参照してください.
なお,実際の入試では$\sqrt{3}$が無理数であることは証明しておくのが無難です.
また,三角関数の加法定理については以下の記事を参照してください.
三角関数の加法定理は三角関数の諸々の公式の中心的な存在といえます.この記事では,三角関数の加法定理と加法定理から導かれる公式をまとめています.
まとめ
以上のように,背理法が有効な証明問題の特徴はただ一つで「証明したいことを否定するとシンプルになる証明」で背理法を用います.
具体的には
- 否定の証明
- 『少なくとも〜』の証明
- 対偶が簡単に示せる証明
がこれにあたります.
- 「無理数である(有理数でない)ことの証明」のような「否定の証明」で背理法を使おうとすると,「否定の否定(有理数でないことはない)」として「肯定(有理数である)」になり,条件が書き直しやすい
- 「少なくとも」を否定すると「全て」となるので,「『少なくとも〜』の証明」は背理法を使うことでシンプルになる
ということでそれぞれ背理法が効果的なのですね.