ホーム >> 集合・論理 >> 背理法の使い方と例

証明法の中でも特に重要かつ頻繁に用いられる背理法について,具体例をあげながら紹介します.



背理法とは

ある命題を証明するために,その命題が成り立たないと仮定して矛盾を導き,それによって命題が成り立つと結論する証明法を,背理法(はいりほう)といいます.

非常に多くの命題や定理について,背理法による証明が知られています.その中には,直接的な証明が知られているものも,背理法による証明しか知られていないものもあります.

背理法の例

背理法の代表的な使い方を $2$ パターン紹介します.

命題 $P$ の示し方

 有理数と無理数の和は必ず無理数である.

結論を否定して,有理数と無理数の和が有理数になると仮定します.
$p$ を任意の有理数, $x$ を任意の無理数とします.このとき,仮定からある有理数 $q$ があって, $$p+x=q$$ とかけます.これより,$x=q-p$ となります.有理数は差について閉じているので,右辺は有理数です.これは $x$ が無理数であることに矛盾します.よって,主張が示せました.もう少し難しい例を解いてみましょう.

 合成数 $n$ は $\sqrt{n}$ 以下の素因数を必ずもつ.

合成数とは,$1$ より大きい素数でない自然数のことです.言い換えれば,$1$ より大きく $1$ と自分自身以外に少なくともひとつ約数をもつ自然数のことです.

さて,上の主張を背理法で示すためには,まず,合成数 $n$ が $\sqrt{n}$ 以下の素因数をもたないと仮定します.$n$ は合成数なので,ある自然数 $p,q (1< p \le q< n)$ があって, $$n=pq$$ とかけます.つまり,$p,q$ は $1$ より大きく,$n$ 自身でない $n$ の約数です.
このとき,$n=pq \ge p^2$ なので,$\sqrt{n} \ge p$ が成り立ちます.
もし,$p$ が素数ならば,$n$ が $\sqrt{n}$ 以下の素因数をもつことになり矛盾です.
一方,$p$ が素数でないならば,$p$ は素因数 $r (1< r< p)$ をもちます.$n=pq$ より,$r$ は $n$ の素因数でもあり,$\sqrt{n} \ge p >r$ なので,この場合も $n$ が $\sqrt{n}$ 以下の素因数をもつことになり矛盾です.よって,主張が示せました.

命題 $P \Rightarrow Q$ の示し方

背理法で示したい主張が,『$P \Rightarrow Q$』という形 ($P$ ならば $Q$) をしているときは,$P$ と $\bar{Q}$ (つまり $Q$ でない) が成り立つと仮定して矛盾を導きます.

 $a$ を整数とする.$a^2$ が偶数ならば $a$ も偶数である.

これを背理法で示すには,整数 $a$ について $a^2$ が偶数で,かつ $a$ が奇数であると仮定します.
$a$ が奇数なので,整数 $b$ を用いて $a=2b-1$ とおけます.すると, $$a^2=(2b-1)^2=4b^2-4b+1=2(2b^2-2b)+1$$ となります.ところが,$2b^2-2b$ は整数なので,上の等式は $a^2$ が奇数であることを意味します.これは $a^2$ が偶数という仮定に矛盾します.したがって,主張が示せました.

 $a,b$ を自然数とする.$a$ と $b$ が互いに素ならば,$a+b$ と $b$ も互いに素である.

$a$ と $b$ が互いに素で,$a+b$ と $b$ が互いに素でないと仮定します.$a+b$ と $b$ が互いに素でないので,$1$ より大きい自然数 $d$ があって, $$a+b=dm,b=dn$$ とかけます.($m,n$ は自然数) この $2$ 式より, $$a=dm-b=dm-dn=d(m-n)$$ となります.したがって,$d$ は $a$ の約数です.$d$ は $b$ の約数でもあったので,$d$ は $a$ と $b$ の公約数です.これは $a$ と $b$ が互いに素であることに矛盾します.したがって,主張が示せました.


この他にも下の記事などで,背理法を用いた証明が登場しているので参考にしてみてください.
→$\sqrt{2}$ が無理数であることの $3$ 通りの証明
→$e$ が無理数であることの証明
→素数が無限に存在することの証明

練習問題

 $a,b$ は有理数,$\sqrt{d}$ は無理数とする.このとき. $$a+b\sqrt{d}=0 \Rightarrow a=b=0$$ を示せ.

→solution

$a+b\sqrt{d}=0$ のもとで,$a\neq 0$ または $b\neq 0$ と仮定する.
$b=0$ のとき,仮定から $a\neq 0$ である.一方,もとの式より $a=0$ となるのでこれは矛盾.
また,$b\neq 0$ のとき,もとの式より,$\sqrt{d}=-\frac{a}{b}$ となる.右辺は有理数で,左辺は無理数なのでこれは矛盾.よって,主張が成り立つ.

 整数 $a,b,c$ は $a^2+b^2=c^2$ を満たすとする.このとき,$a,b$ のうち少なくとも一つは $3$ の倍数であることを示せ.

→solution

$a,b$ ともに $3$ の倍数でないと仮定する.このとき,$a,b$ を $3$ で割った余りは $1$ または $2$ である.
いずれにせよ,$a^2,b^2$ を $3$ で割った余りはともに $1$ となる.したがって,$a^2+b^2$ を $3$ で割った余りは $2$ となる.ところが,$c^2$ を $3$ で割った余りは $0$ または $1$ なので,これは矛盾.したがって,主張が成り立つ.

つぎの問題もぜひチャレンジしてみてください.
→有理数の平方和