いろいろな証明の方法2

この記事の所要時間: 536

いろいろな証明の方法2

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

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

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

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

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)

このとき,

(1) \begin{eqnarray*} 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{eqnarray*}

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

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

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

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

(ii) k以下のすべての自然数mP(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つの命題PQが与えられていて, PQが同値である(PQであるための必要十分条件である)ことを示す場合, 一般的には,

(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が言えていることが分かります.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加

コメントをどうぞ

メールアドレスが公開されることはありません。