数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

いろいろな証明の方法2

定義・定理・公式

スポンサードリンク

いろいろな証明の方法2

前回の記事「いろいろな証明の方法」の続きです.

対偶法
背理法
無限降下法
数学的帰納法
反例を挙げる
同値である(必要十分条件である)ことを示す場合

前回は3. 無限降下法まで説明したので, ここでは4. 数学的帰納法から後の 3 つを説明します.

前回同様, 以下の説明の中で $P$ や $Q$ はある命題を表します.

4.数学的帰納法

「すべての自然数 $n$ について $P(n)$ が成り立つ」ことを示すときに,

(i) $n=1$ のとき, $P(1)$ が成り立つことを示す.

(ii) $n=k$ のとき $P(k)$ が成り立つと仮定すると $P(k+1)$ も成り立つことを示す.

という手順で証明する.

(i)と(ii)で $k=1$ の場合から, $P(2)$ が成り立ち, さらに(ii)で $k=2$ の場合から $P(3)$ が成り立ち, …というように, すべての場合が証明できたことになります.

$P(n)$ というのは, 例えば次のように, $n$ によって内容の変わる命題を表しています.

$P(n)=$ 「 $\displaystyle 1+2+\cdots+n=\frac{1}{2}n(n+1)$ 」

例として, 上の $P(n)$ がすべての自然数 $n$ で成り立つことを示してみます.

(i) $P(1)$ を示す.

(左辺) $=1$

(右辺) $\displaystyle =\frac{1}{2}\cdot 1\cdot 2=1$

より $P(1)$ は成り立つ.

(ii) $P(k)$ が成り立つと仮定すると,

$\displaystyle 1+2+\cdots+k=\frac{1}{2}k(k+1)$

このとき,

$\begin{align*} 1+2+\cdots+(k+1) &= (1+2+\cdots+k)+(k+1)\\ &= \frac{1}{2}k(k+1) + (k+1)\\ &= \frac{1}{2}(k+1)(k+2) \end{align*}$

となり, $P(k+1)$ も成り立つ.

(i), (ii)より, すべての自然数 $n$ について $P(n)$ は成り立つ.

数学的帰納法には次のようなパターンもあります.

(i) $n=1$ のとき, $P(1)$ が成り立つことを示す.

(ii) $k$ 以下のすべての自然数 $m$ で $P(m)$ が成り立つと仮定すると $P(k+1)$ も成り立つことを示す.

この方法を使う問題は京大の2010年度にも出ています. (その問題と解答はこちら)

5. 反例を挙げる

ある命題 $P$ が偽である(正しくない)ことを示すときには, その命題を満たさない例(反例)を一つ挙げればよい.

例えば, 「無理数と無理数の和は無理数である」という命題が正しくないことを示すには,

無理数と無理数の和が有理数になるような反例を一つ挙げればよく, 例えば $\sqrt{2}$ と $-\sqrt{2}$ はともに無理数だが, その和は $0$ となり有理数なので, 命題が正しくないことを示せた.

反例に関して, 面白い例があるので紹介します.

命題 : 「無理数の無理数乗は無理数である」は正しいか.

一見正しいのでは, とも思えますが, 反例があります.

まず, $\displaystyle \sqrt{2}^\sqrt{2}$ という数は実数なので有理数または無理数です.

もしこの数が有理数なら, $\sqrt{2}$ は無理数なのでこれが反例になっています.

一方, これがもし無理数であれば,

$\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=\sqrt{2}^2=2$

となることから, $\sqrt{2}^\sqrt{2}$ の $\sqrt{2}$ 乗が反例になっています.

つまり, $\sqrt{2}^\sqrt{2}$ が有理数か無理数かは分からないけれども, どちらの場合にしても反例をつくることができる場合があるのです.

同値である(必要十分条件である)ことを示す場合

2つの命題 $P$ と $Q$ が与えられていて, $P$ と $Q$ が同値である( $P$ が $Q$ であるための必要十分条件である)ことを示す場合, 一般的には,

(i) $P\Rightarrow Q$ を示す

(ii) $Q\Rightarrow P$ を示す

というように, 両方向の証明をしますが, (ii)については対偶を示すと考えると,

(i) $P\Rightarrow Q$ を示す

(ii)' $\overline{P}\Rightarrow\overline{Q}$ を示す

とすることもできます. この場合, $P$ が成り立つかどうかで場合分けしてそれぞれについて $Q$ が成り立つかどうかを示すという構図になっています. (これを転換法と呼ぶことがあるらしいです).

3 つの命題が同値であることを示す場合

めったにないとは思いますが, 3つの命題 $P, Q, R$ が互いに同値であることを示すこともあります. このとき, $P, Q$ が同値かつ $Q, R$ が同値と考えて証明しようとすると

(i) $P\Rightarrow Q$ を示す

(ii) $Q\Rightarrow P$ を示す

(iii) $Q\Rightarrow R$ を示す

(iv) $R\Rightarrow Q$ を示す

と 4 回の証明が必要になり, 大変な作業となります.

しかし, 場合によっては次のように 3 回の証明で済みます.

(i)' $P\Rightarrow Q$ を示す

(ii)' $Q\Rightarrow R$ を示す

(iii)' $R\Rightarrow P$ を示す

すると, (i)' と (ii)'から $P\Rightarrow R$ も言えますし, 同様に (ii)' と (iii)' から $Q\Rightarrow P$ が, (iii)' と(i)'から $R\Rightarrow Q$ が言えていることが分かります.