 pc ( No.10 ) |
- 日時： 2009/07/16 14:11
- 名前： nn)/
ご参加どうもありがとうございました．
ここには，皆様のご解答をみて感じたこと，補足すべきことを書きます．
(i) 元にした問題
元の問題は，0/1 と 1/1 から始めるのではなく，0/1 と 1/0 = ∞ から開始です．
すると，整数（分母が１の分数）および 分母より大きな分子をもつものを含めた
全ての正の既約分数が出てきます．試してみてください，
ここでは，本質的でない説明を省くため，０ と 1 の間の分数に限定しました．
>>9 に掲げた解答は 0/1 と 1/0 で始めた場合についても，(3) で
(m'+n') + (m"+n") ≧ m'+n'+m+n+1 （2 を 1 に変更）
とする以外，そのまま通用するはずです．
(ii) 数学的帰納法，自然数 --- ボムボムさんの解答について
ボムボムさんの解答 (特に >>3) は，数学的帰納法を Wikipedia にもある通り，
1. 命題 P(0) は真である．
2. 任意の自然数 k に対し，P(k) が真であれば，P(k+1) も真である，
よって任意の自然数 n について P(n) は真である．
の形でそのまま使ったものです．大変きちっとされていて感心しました．ただ，
REEさん (>>1) やfyhさん (>>8 の１) の解答がやけにあっさりして見えるように，
この形に限定する必要はありません．そもそも 2. は
2'. 任意の自然数 k (k ≦ n) に対し，P(k) が真であれば，P(n+1) も真である，
でないとうまく行かない場合もあるので，Wiki も怪しいところが結構あります．
ここで「自然数」は 0 以上の整数を意味していることに注意して下さい．
その方が自然なので，だいぶ前から，多くの分野で黙っていれば 0 を含むこと
が普通になりつつあります．つまり，１以上の整数は「正の整数」「正整数」，
0 以上の整数は「非負整数」などと呼ぶ方が無難です．
帰納法とはもともと「対象を構成する個々の要素について命題 P が真であるから，
対象全体に関して P が真である」とするものです．ですから，あるルールに基づ
いて対象の全要素が作り出されるとき，
1. 生成する源 (ここでは 0/1 と 1/1) について命題 P は真である．
2. ある要素が作られる際，それ以前に作られている全ての要素について P が
真であれば，その要素についても P が真である，
ことが証明できれば，任意の要素について P は真であると言えます．これを特に
構成に関する帰納法 (induction on construction) と名付ける人もいます．
(iii) 背理法・構成的証明・拡張ユークリッドの互除法 --- fyhさんの解答について
fyhさんの解答 (>>8 の 2) に対し，「背理法にしない方がよりカッコいい」とコメ
ントしました．なぜそう思うのか，書いておく責任がありそうです．
背理法は強力な証明法で，簡潔に証明できる場合も多く，また，背理法でなければ
証明困難な命題もたくさんあります．実際，(3) の証明でも背理法を用いています．
また，その強力さは入試向けにもぴったりで，背理法を用いなくても証明可能な命
題も，背理法を使うように指導するのが，受験対策というものでしょう．
ただし，背理法には欠点があります．たとえば，「ある性質 A を持つ要素が少なく
とも１つは存在する」という命題を証明するには，「A なる要素が存在しないと仮
定すれば矛盾を生じる」ことを示せば十分です．しかし，存在が証明できても，ど
うやって A という性質を持った要素を１個あるいは全部得るか，という課題解決に
は，あまり役立たないことも多いのです．つまり，対象集団に関する具体性に欠け
る傾向があるのです．
一方，「こうすれば性質 A を持つ要素が作れる」として，作る際の手続きを示せば，
存在証明を行うと同時に，本来の課題も解決されます．このような方針に基づく証
明法を構成的 (constructive) といいます．そのような要素が作れる場合か作れな
い場合かの判定についても，背理法に基づく証明からは，判定方法の設計方針にあ
まり情報が得られません．
つまり，背理法を採用しなくても（そう大変にならず）証明可能ならば，採用し
ない方がカッコいいと思うのです．fyhさんの解答では，わざわざ「２以上の公約
数で割り切れる」と仮定し，矛盾を言っています．「分母・分子の最大公約数が１」
という既約の定義をそのまま使えるのに，そこから少し離れるのは背理法への過剰
な慣れのように感じました．
(3) の証明は，背理法とはいえ，構成的といえるような要因が含まれていますので，
a + b 段目より上には a/b が現れるという情報も，証明と同時に得られています．
なお，(2) の証明にある (*) の式 m'n - mn' = 1 のように，正整数 m, n を与えたと
き， r m + s n = gcd(m,n) を満たす整数 r, s が (無数に) 存在します．そのような
整数組 (r, s) の一つを与える方法は拡張ユークリッドの互除法と呼ばれ，そのよう
な整数組の存在に対する構成的証明にもなっています．
|
|
FAQ
RSS