2015/06/09

背理法のいろいろな例

分野: 集合,命題,論証  レベル: 入試対策

$A$ であることを証明するために,$A$ でないことを仮定して矛盾を導き出す方法を背理法と言う。

前半:背理法の意味,いろいろな例について解説
後半:背理法のよくある間違い,背理法のデメリットについて考察

無理数であることの証明

例題1

$\sqrt{2}$ が無理数であることを証明せよ。

背理法を用いて証明できる一番有名な命題です。

証明

$\sqrt{2}$ が有理数だと仮定する。
つまり,$\sqrt{2}=\dfrac{q}{p}$($p$ と $q$ は互いに素な自然数)と書けるとする。
このとき,$2p^2=q^2$
左辺は偶数なので右辺も偶数。よって,$q$ は偶数。すると,右辺は $4$ の倍数になるので $p$ も偶数。
これは $p$ と $q$ が互いに素であることに矛盾。
よって,背理法により題意は示された。

注:背理法の導入のために,わざわざ背理法を使いましたが,ルート2の無理数性の証明には他にもいろいろな方法があります。→ルート2が無理数であることの4通りの証明

異なることの証明

例題2

$a$ と $b$ は互いに素な正の整数とする。 $0,a,2a,\cdots, (b-1)a$ を $b$ で割った余りは全て異なることを証明せよ。

証明

$0,a,2a,\cdots, (b-1)a$ の中に $b$ で割った余りが同じであるような二つの数が存在したと仮定する。これを $ia$ と $ja$ とおく $(0\leq i <j\leq b-1)$ 。

このとき $ja-ia=(j-i)a$ は $b$ の倍数。

一方,

  • $a$ は $b$ と互いに素
  • $1 \leq j-i \leq b-1$

より,$(j-i)a$ は $b$ の倍数にはなり得ない。矛盾。背理法により題意は示された。

注:これは一次不定方程式の背景にある有名な定理です。→一次不定方程式ax+by=cの整数解

いろいろな例

背理法を使って証明できる命題を集めました。上の二つの例題よりもかなり難しいものが多いです。詳細はリンク先をどうぞ。

・ $\tan 1^{\circ}$ は無理数である。
 →tan1°が無理数であることの証明

・ネイピア数 $e$ は無理数である。
 →ネイピア数eが無理数であることの証明

・フロベニウスの硬貨交換問題(主張1の部分)
 →フロベニウスの硬貨交換問題

・レイリーの定理(整数問題のややマニアックな定理)
 →レイリーの定理とその自然な証明

・素数は無限にある
 →素数が無限にあることの美しい証明

2016/7/24 追記:
「背理法のよくある間違いと批判」という節を設けていましたが,細かい議論に間違いがあったため削除しましたm(_ _)m

僕はそんなに背理法嫌いじゃないです。

Tag: 数学1の教科書に載っている公式の解説一覧

分野: 集合,命題,論証  レベル: 入試対策