- ベストアンサー
数学的帰納法の証明と整列集合
- 数学的帰納法を用いた証明において、整列集合の性質は使用されていない。
- 数学的帰納法は自然数が整列集合であることと同値であるが、これを示すために整列集合の性質が使われる。
- 数学的帰納法の証明において、条件（ⅱ）は (∀ｎ∈N（P(n)⇒P(n+1)) と表される。
- みんなの回答 （8）
- 専門家の回答
質問者が選んだベストアンサー
NO2です。 いえいえ、わかっているつもりです。 自然数の性質のうち、通常公理として与えられる、帰納法の原理を証明したいと考えているのですから、この原理を証明に使ってはいけないわけです。 帰納法の原理を前提としないとき、 ある自然数mについて、m,m-1,m-2,,,,（簡単のため略記していますが、後継関数ｓの逆元の列です） が、１（０をNに含めるかどうかは流儀の問題で些細なことです）に到達しない可能性がある（というか、要するに証明できないでしょ）ということです。 なぜならこのことの証明には、「帰納法の原理」を用いるからです。 そしてそのことを明示するために、「帰納法の原理を前提にしないときの自然数モドキ」という反例を紹介しました。 質問者さんの質問にずばりで回答すると 「論法が間違っています。（証明内で未証明の事実を利用しています）」 「以下続けると、とありますが、この部分が証明できていません」 となります。 *） 帰納法の原理を前提にしないで、整列集合の性質を付加するには順序を上手に定義しないといけないですね。１以外にも、逆元の存在しない元があるかもしれませんから。 帰納法の原理って、言い換えると「自然数は１から始まる列に全ての元が現れ、他の元はありませんよ」っていう原理ですね。
その他の回答 (7)
- funoe
- ベストアンサー率46% (222/475)
No2,6です。 >普通の自然数の中の帰納法の原理だけが保証されていない”自然数”において >任意の”自然数”ｍに対して列{m,m-1,m-2,・・・}が０（または１）に到達する >を公理として追加すれば大丈夫ということでしょうか 大丈夫ですね。普通の帰納法の原理と同値と思われます。 －－－－ 「自然数は１から始まる列に全ての元が現れ、他の元はありませんよ」のこと。 ペアノの公理だと、 1)Ｎは１を含む。 2)Ｎ上で定義された単射ｓがある。 3)任意の元ｘについて、ｓ（ｘ）≠１ に加えて 4)帰納法の原理があるわけですよね。 帰納法の原理って、 自然数Ｎの部分集合Mについて、 （１∈Ｍ 、n∈M ⇒ n+1∈M）ならば、Ｍ＝Ｎ と表現できますよね。 また、「Ｍの要素である」ってのを、「ある性質をもつ」って表現することもありますよね。 日本語で表現すると、 「ある部分集合Mに１が含まれ、ｎが含まれているならｎ＋１も含まれる。このときＭはＮと一致する」 や 「１がある性質を満たし、ｎがその性質を満たす時ｎ＋１もその性質を満たす。このとき全ての自然数はその性質を満たす」 となりますね。 と、ここまでは、念のための確認でした。 さて、帰納法の原理がなくても、1)～3)だけで、 ・Ｎに１が含まれること、 ・ｓ（１）＝２が含まれること、以下、３，４，５、、、が含まれること、 ・そしてそれらが循環しないでことごとく異なるものとなること は、示されます。 では、帰納法の原理でなにを保証したいかっていうと、この１）～３）だけだと、「他のものが混ざる可能性」があるので、 「他のものは紛れ込んでいませんよ」ってことを保証するんです。 いま、ｗ１っていう、普通の自然数でない元を想定して、これも１と同じく、任意の元ｘについて、ｓ（ｘ）≠ｗ１という 性質を満たすとしたとき、ｗ１から始まるｗ１、ｗ２＝ｓ（ｗ１）、ｗ３＝ｓ（ｗ２）、ｗ４、ｗ５、ｗ６、、、、なんていう無限個の元の列が こっそり紛れ込んでいるかもしれないんです。 あるいは、先に紹介したような、ｓ（ｘ１）＝ｘ２、ｓ（ｘ２）＝ｘ３、ｓ（ｘ３）＝ｘ１ なんていう、有限個でのループが紛れ込んでいるかもしれません。 １）～３）だけだと、これらの元の混入を排除できないことがおわかりでしょう。 帰納法の原理は、 （１∈Ｍ 、n∈M ⇒ n+1∈M）という、１から始まる列（１，２，３，４，５、、、、)を含む部分集合Mは、「ただそれだけで」「どんなに小さく考えても」、実は「自然数全体」になってしまうんだよ、つまりそれ以外の元は存在しないよ、ということを保証してくれるものなんです。 情緒的な表現になってしまいましたが、お分かりいただけたでしょうか。
お礼
長文での回答ありがとうございます。 数学的帰納法を最初に習ったときいまいち気に入らなかったので 最近になって少し勉強しなおしてみていたら質問した間違った証明ができました。 どこかが違っているはずとは思いながらもどこが違うかわからなかったので、ここで皆さんに答えていただいて大変参考になりました。 私としては自然数nの直前の元をずっと考えていけば0（または１）にたどり着くというほうが直感的で好きなのでこれからはそれで理解したことにしようかと思っていたのですが、この説明を読んで帰納法の原理が具体的にどの部分に効果を表すのかがわかったと思います。 また、 「自然数は１から始まる列に全ての元が現れ、他の元はありませんよ」 の意味するところもわかりました。 本当にありがとうございました。
- ninigi
- ベストアンサー率43% (10/23)
> 任意のn∈Nに対して、P(n)が成り立たない⇒P(0)が成り立たない > を前提に追加すればいけるということになると思うのですが、 少し勘違いさせてしまった様なので補足します。 前提が足りないのではありません。この部分を整列集合の性質を使って証明するのです。 証明の基本的なアイディアは P(n)で成り立たない⇒P(n-1)で成り立たない⇒P(n-2)で成り立たない・・・ とnをどんどん小さくしていって、最も小さいnに辿り着いたら、そこで矛盾が発生する というものです。 しかし繰り返し操作を省略できないので、代わりに整列集合の性質「任意の部分集合は最小値を持つ」を使います。 繰り返し操作を用いずにいきなり最小値を取り出せるところに証明のポイントがあります。 勉強に使われている本にも書いてあるとは思いますが、証明はおよそ以下のようになります。 [証明] P(n)が成り立たないような集合をSとする Sが空集合である事を示せばP(n)がすべての自然数ｎについて成り立つ事になる Sが空集合でないと仮定すると、Sは整列集合N(=自然数全体)の部分集合なので最小値mを持つ。 条件(i)よりm≠0である、よってm≧1。従ってm-1∈Nである。 mはSの最小値なのでm-1はSに含まれない。従ってP(m-1)は成り立つ。すると条件(ii)よりP(m)が成り立つ。 これはmがSの元である事に反する。 従ってSは空集合でなければならない。 (証明終) ちなみにfunoeさんが仰っているのは、おそらく「ペアノの公理」の第五公理のことだと思います。 論理学や数学基礎論の本に詳しく載っているので、そちらも参照するとさらに理解が深まるでしょう。
お礼
数学的帰納法の原理⇔自然数が整列集合ですが ＊命題A 任意のn∈Nに対して、P(n)が成り立たない⇒P(0)が成り立たない か、できれば ＊命題B 任意の”自然数”ｍに対して列{m,m-1,m-2,・・・}が０（または１）に到達する が数学的帰納法の原理、整列性と同値にならないかなと思いまして。 整列性による数学的帰納法の証明ありがとうございます。
- ----------
- ベストアンサー率30% (30/98)
No3です。 質問者の質問したいことが あまりみなさんに伝わっていないかもしれませんが、 おそらく、質問者の聞きたいことは 「数学的帰納法を証明する」方法であり、 「数学的帰納法を使って証明する」方法ではないと思います。 質問文では、0を自然数に含めるような書き方をしていますが、 もし、0を自然数に含めると仮定してそのまま議論を進めるとしたら、 質問者の証明は 「数学的帰納法を証明」できたことになっていると思います。 (ii)の対偶(II)で「すべての」と書いてあるところは 「ある」の間違いですが、それ以外はあっています。 で、整列集合についてですが、 >P(m)が成り立たないのでP(m-1)も成り立たないことになる >このときP(m-1)が成り立たないのでP(m-2)も成り立たない >以下続けると結局 >P(1)が成り立たないのでP(0)も成り立たないことになるが の部分で、(II)を繰り返し用いて(i)との矛盾を示そうとしていますが、 この部分で使われているんだろうと思います。 自然数ではなく、たとえば実数全体について 同じことをしようとしても同じようにはいかないと思います。
お礼
回答ありがとうございます。 もし間違っていたらすみません。 確かに私の質問したいことは 「数学的帰納法を証明する」方法 です。 Nに0が含まれようが含まれまいがあまり関係ないと思うのですがどうなのでしょうか。 また、 P(n)が成り立つ⇒P(n+1)が成り立つ の部分の対偶をとっているので「すべての」部分はそのままでいいと思います。 もし（II）を ある自然数ｎに対して、P(n+1)が成り立たない⇒P(n)も成り立たない にしてしまうと P(0),P(1),P(2)では正しく、P(3)以上で正しくないような命題を考えると P(4)で正しくない⇒P(3)で正しくない が成り立っているのですべての自然数nに対してP(n)が正しいことになり おかしいのではないでしょうか。
- ninigi
- ベストアンサー率43% (10/23)
論法が間違っています。 お判りだと思いますが、任意の自然数nに対して P(0)が成り立つならばP(1)も成り立つ P(1)が成り立つならばP(2)も成り立つ ・・・ P(n-1)が成り立つならばP(n)も成り立つ の、途中の省略した「・・・」の部分を補うのが数学的帰納法です。 したがって、この対偶 P(n)が成り立たないならばP(n-1)も成り立たない P(n-1)が成り立たないならばP(n-2)も成り立たない ・・・ P(1)が成り立たないならばP(0)も成り立たない の途中の「・・・」を補うには、数学的帰納法が必要なのです。 つまり、貴方の証明は >P(m)が成り立たないのでP(m-1)も成り立たないことになる >このときP(m-1)が成り立たないのでP(m-2)も成り立たない >以下続けると結局 >P(1)が成り立たないのでP(0)も成り立たないことになるが の部分で数学的帰納法を使ってしまっているのです。 「途中を省略してもいい」事を示すのが数学的帰納法の醍醐味なので、 その数学的帰納法を証明するために途中を省略してはいけません。
お礼
ええっとつまり 任意のn∈Nに対して、P(n)が成り立たない⇒P(0)が成り立たない を証明するのに数学的帰納法が必要と言うことでしょうか。 確かにその通りですね。 ということは 任意のn∈Nに対して、P(n)が成り立たない⇒P(0)が成り立たない を前提に追加すればいけるということになると思うのですが、 このままでは直感的にわかりにくい上にかなり限定された命題だと思われるのでもう少し考えて来ます。
- ----------
- ベストアンサー率30% (30/98)
0は自然数ですか？
補足
funoeさんがおっしゃられてるとおり 0から始めるか1から始めるかは些細な事かと思います
- funoe
- ベストアンサー率46% (222/475)
「以下続けると結局,P(1)が成り立たない」の部分がNGでしょう。 帰納法の原理を仮定しないとき、ある元の逆元(後継関数の逆元)の逆元の逆元の・・・が１になることを保証できないのではありませんか。 帰納法の原理を仮定しないと、 Ｎ＋＝Ｎ∪｛w0,w1｝として、s(w0)＝ｗ１、s(w1)=w0 と定義した自然数モドキを否定できません。 このＮ＋では、ｗ０の逆元の逆元の・・・は、１になりません。
お礼
夜遅くの回答ありがとうございます。 今日は一日予定がありましたので、今から少し考えてからNo.6の方に考えた事を書き込みたいと思います。 具体例を出していただいたので非常にわかりやすいです。
- a-saitoh
- ベストアンサー率30% (524/1722)
「すべての自然数nに対して成り立つ」ならば「「すべての自然数nに対して成り立つ」 といってるだけです。何の証明にもなっていません。 証明したいことそのものを仮定したら、証明したいことが成り立つのは当たり前。
お礼
さっそくのご回答ありがとうございます どの部分で すべての自然数nに対してP(n)が成り立つを仮定してるのでしょうか それがわからないのです すべての自然数ｎに対して、P(n)が成り立つならばP(n+1)も成り立つ と すべての自然数ｎに対してP(n)が成り立つ は同じ命題だということでしょうか？
お礼
返答が遅くなってしまい申し訳ないです。 普通の自然数の中の帰納法の原理だけが保証されていない”自然数”において 任意の”自然数”ｍに対して列{m,m-1,m-2,・・・}が０（または１）に到達する を公理として追加すれば大丈夫ということでしょうか このままの表現でいいのかは私にはちょっとわかりませんが この表現だと自分たちの知っている自然数の感じと一致していてちょっといい感じです。 帰納法の原理や整列性の仮定でもわかりやすいのですが ちょっと納得がいかなかったので・・・。 funoeさんの回答はまさに聞きたいところを答えていただいていたので大変感謝しています。 ありがとうございました。 もしよろしければ最後の ＞帰納法の原理って、言い換えると「自然数は１から始まる列に全ての元が現れ、他の元はありませんよ」っていう原理ですね。 の解説を少しだけしていただけないでしょうか。