背理法
数と式(教科書範囲) ★★★
背理法について扱います．
対偶証明法と並んで直接示しにくい命題に対する証明手段で，今後数学をする上で避けて通れません．
背理法
$p$ という命題を示したいが直接示すのが困難な場合，$\overline{p}$ と仮定して矛盾が言えれば，$p$ が正しいと言える若干強引とも思える手法があります．これを背理法といいます．
背理法の手順
$p$ という命題を示したいが難しい
↓
$\overline{p}$ と仮定して矛盾を言う
↓
$p$ が正しい
背理法は，世界が2分できる場合に強力ですがそうでない場合にはあまり有効ではありません．
例えば，実数の世界では必ず有理数と無理数に2分できますが，このような場合の証明に背理法は強力です．
$p \Longrightarrow q$ の証明
$p \Longrightarrow q$ の証明が難しいとき，$p \Longrightarrow q$ の否定である $p$ かつ $\overline{q}$ として矛盾が言えればこれも背理法により $p \Longrightarrow q$ が示せます．
対偶証明法と比較して示しやすい方を選択すればいいと思います．
例題と練習問題
例題
例題
(1) 素数が無限個存在することを示せ．
(2) $\sqrt{2}$ は無理数であることを証明せよ．
講義
どちらも背理法を扱うときは有名な題材です．
(1)素数が有限個存在すると仮定して矛盾を示します．
(2)定期試験で頻出です．$\sqrt{2}$ が有理数であることを仮定して矛盾を示します．
解答
(1)
素数が有限個，すなわち $n$ 個の素数 $p_{1}$，$p_{2}$，$p_{3}$，$\cdots$，$p_{n}$ が存在すると仮定する．
$P=p_{1}p_{1}p_{1} \cdots p_{n}+1$ とすると，$P$ は $p_{1}$，$p_{2}$，$p_{3}$，$\cdots$，$p_{n}$ のいずれでも割ることができないので素数となる．これは $n$ 個の素数が存在するとしたことに矛盾．
最初の仮定が誤りなので，素数は無限個存在する．
※ 文字を $p$ にしているのは素数(prime number)の頭文字に由来しています．
(2)
$\sqrt{2}$ が有理数であると仮定すると
$\sqrt{2}=\dfrac{q}{p}$ ( $p$，$q$ は互いに素な自然数)
とおける．分母払って $2$ 乗すると
$2p^{2}=q^{2}$
$q^{2}$ は偶数なので，$q$ も偶数．
$q=2k$ ( $k$ は自然数)とおけるので
$2p^{2}=4k^{2}$
$p^{2}=2k^{2}$
$p^{2}$ は偶数なので，$p$ も偶数．
以上より $p$，$q$ はどちらも偶数なので，互いに素であることに反するので矛盾．最初の仮定が誤りなので，$\sqrt{2}$ が無理数である．
※ 2回も使用している，$n^{2}$ が偶数ならば $n$ は偶数であることの証明は付けなくていいことが多いです．もし必要なら，命題の逆，裏，対偶の例題に同じ問題があります．
※ $\sqrt{3}$ や $\sqrt{5}$ などの場合も本質的に同じです．
別解
小数部分を既約分数で置いた別解
$\sqrt{2}$ が有理数であると仮定すると
$\sqrt{2}=1+\dfrac{q}{p}$ ( $p$，$q$ は互いに素な自然数)
とおける．
$\dfrac{p}{q}$
$=\dfrac{1}{\sqrt{2}-1}$
$=\sqrt{2}+1$
$=2+\dfrac{q}{p}$
$=\dfrac{2p+q}{p}$
$\dfrac{p}{q}$ は既約分数なので，分母に注目すると $q=pk$ ( $k$ は自然数)となり，$p$ と $q$ は互いに素であることに矛盾．
最初の仮定が誤りなので，$\sqrt{2}$ が無理数である．
練習問題
練習1
(1)次の命題(ア)〜(エ)について，真であるものを1つ選べ．
(ア) $a$，$b$ が無理数のとき，$a+b$ は無理数である．
(イ) $a$，$b$ が無理数のとき，$ab$ は無理数である．
(ウ) $a$ が有理数で，$b$ が無理数のとき，$a+b$ は無理数である．
(エ) $a$ が有理数で，$b$ が無理数のとき，$ab$ は無理数である．
(2)(1)で選んだ命題を証明せよ．
練習2
$a$，$b$ が有理数のとき $a+b\sqrt{2}=0$ ならば $a=b=0$ であることを証明せよ．
練習3
実数 $\alpha$ が $\alpha^{3}+\alpha+1=0$ をみたすとき，$\alpha$ が無理数であることを証明せよ．
練習1の解答
(1)
(ア)偽(反例：$a=\sqrt{2}$，$b=-\sqrt{2}$ )
(イ)偽(反例：$a=\sqrt{2}$，$b=\sqrt{2}$ )
(エ)偽(反例：$a=0$，$b=-\sqrt{2}$ )
(ウ)が真
(2)
$a+b$ が有理数であるとすると $r$ を有理数として，$a+b=r$ とおける．
$b=r-a$
とすると，左辺は無理数で，右辺は有理数となり矛盾．
よって，$a+b$ は無理数である．
練習2の解答
$a+b\sqrt{2}=0$ なら，$a=b=0$ もしくは $a\neq0$ かつ $b\neq0$ しかないので，$a\neq0$ かつ $b\neq0$ であると仮定する．
$a+b\sqrt{2}=0$ を
$\sqrt{2}=-\dfrac{a}{b}$
とすると，右辺が有理数となり矛盾する．
すなわち $a$，$b$ が有理数で $a+b\sqrt{2}=0$ ならば $a=b=0$．
※ この問題は対偶証明法だと難しいと思います．
練習3の解答
$\alpha$ が有理数であると仮定すると
$\alpha=\dfrac{q}{p}$ ( $p$，$q$ は互いに素な整数)
とおける．代入すると
$\dfrac{q^3}{p^3}+\dfrac{q}{p}+1=0$
$\Longleftrightarrow \ \dfrac{q^3}{p}=-p(q+p)$
右辺は整数なので，左辺も整数．つまり $p=1$．
$\alpha=q$ より
$q^{3}+q+1=0$
$\Longleftrightarrow \ 1=-q(q^{2}+1)$
(ⅰ) $q=0$ のとき $1=0$ となり不適．
(ⅱ) $q\geqq1$ のとき $-q(q^{2}+1)\leqq-2$ となり不適．
(ⅱ) $q\leqq-1$ のとき $-q(q^{2}+1)\geqq 2$ となり不適．
すべての場合で矛盾するので，最初の仮定が誤り．つまり $\alpha$ は無理数である．