いろいろな証明の方法2
前回の記事 「いろいろな証明の方法」の続きです.前回は3. 無限降下法まで説明したので, ここでは4. 数学的帰納法から後の 3 つを説明します.前回同様, 以下の説明の中で や はある命題を表します.
4.数学的帰納法
(i)と(ii)で の場合から, が成り立ち, さらに(ii)で の場合から が成り立ち, …というように, すべての場合が証明できたことになります.というのは, 例えば次のように, によって内容の変わる命題を表しています.
「」
例として, 上の がすべての自然数 で成り立つことを示してみます.
(i) を示す.
(左辺)
(右辺)
より は成り立つ.
(ii) が成り立つと仮定すると,
このとき,
となり, も成り立つ.
(i), (ii)より, すべての自然数 について は成り立つ.
数学的帰納法には次のようなパターンもあります.
(i) のとき, が成り立つことを示す.
(ii) 以下のすべての自然数 で が成り立つと仮定すると も成り立つことを示す.
5. 反例を挙げる
ある命題 が偽である(正しくない)ことを示すときには, その命題を満たさない例(反例)を一つ挙げればよい.
無理数と無理数の和が有理数になるような反例を一つ挙げればよく, 例えば と はともに無理数だが, その和は となり有理数なので, 命題が正しくないことを示せた.
反例に関して, 面白い例があるので紹介します.
一見正しいのでは, とも思えますが, 反例があります.
もしこの数が有理数なら, は無理数なのでこれが反例になっています.
一方, これがもし無理数であれば,
となることから, の 乗が反例になっています.
つまり, が有理数か無理数かは分からないけれども, どちらの場合にしても反例をつくることができる場合があるのです.
同値である(必要十分条件である)ことを示す場合
2つの命題とが与えられていて, と が同値である( が であるための必要十分条件である)ことを示す場合, 一般的には,(i) を示す
(ii) を示す
というように, 両方向の証明をしますが, (ii)については対偶を示すと考えると,
(i) を示す
(ii)' を示す
とすることもできます. この場合, が成り立つかどうかで場合分けしてそれぞれについて が成り立つかどうかを示すという構図になっています. (これを転換法と呼ぶことがあるらしいです).
3 つの命題が同値であることを示す場合
めったにないとは思いますが, 3つの命題 が互いに同値であることを示すこともあります. このとき, が同値かつ が同値と考えて証明しようとすると(i) を示す
(ii) を示す
(iii) を示す
(iv) を示す
と 4 回の証明が必要になり, 大変な作業となります.
しかし, 場合によっては次のように 3 回の証明で済みます.
(i)' を示す
(ii)' を示す
(iii)' を示す
すると, (i)' と (ii)'から も言えますし, 同様に (ii)' と (iii)' から が, (iii)' と(i)'から が言えていることが分かります.