16/06/05 14:14:38.20 3R0gafSZ.net
以下の構造帰納法について質問があります。
数学的帰納法のいわゆるBase Caseにあたる部分がないと思いますが、
それでも A のすべての要素 z に対し P(z) が成り立つことが言える
のでしょうか？
構造帰納法：
R を集合 A 上の整礎な関係とする。
P(x) を A の要素 x についての性質とする。いま x R y かつ x ≠ y となる
すべての x について P(x) が成り立つという仮定から、 p(y) が成り立つことが
導かれるとする。このときには、 A のすべての要素 z に対し P(z) が成り立つ。
1001:１３２人目の素数さん
16/06/05 15:57:27.18 y6zUh7sE.net
基礎でなかったら成り立たない例は簡単に作れる
基礎なら空集合がBase Caseにあたる
1002:１３２人目の素数さん
16/06/06 01:05:26.75 fk4i0h
1003:hd.net
1004:１３２人目の素数さん
16/06/06 12:18:15.32 7BpBxd+J.net
構造帰納法：
P(x) を A の要素 x についての性質とする。いま x R y かつ x ≠ y となる
すべての x について P(x) が成り立つという仮定から、 P(y) が成り立つことが
導かれるとする。このときには、 A のすべての要素 z に対し P(z) が成り立つ。
>>971-972
ありがとうございました。
x R y かつ x ≠ y となるすべての x について P(x) が成り立つ
⇒
P(y) が成り立つ
を証明しようとすると、結局、Base Caseを証明しなければならないんですね。
y を A の R 極小元とすると、
{x ∈ A| x R y かつ x ≠ y} = φ
だから、x R y かつ x ≠ y となるすべての x について P(x) は成り立つ。
したがって、
x R y かつ x ≠ y となるすべての x について P(x) が成り立つ
⇒
P(y) が成り立つ
を証明しようと思うと、すべての A の R 極小元 y について P(y) が成り立つことを証明しなければならない、
つまり、Base Caseを証明しなければならないわけですね。
1005:１３２人目の素数さん
16/06/06 12:55:16.41 7BpBxd+J.net
今、読んでいる本で分からない箇所にまた出くわしました。
まず、その本には、
------------------------------------------------------------------
集合 A 上の順序 ≦ が整列になるための必要十分条件は、
A の空でない任意の部分集合 B に必ず（ ≦ に関する）最小元が存在する
ことである。
------------------------------------------------------------------
と書いてあります。その後に、
------------------------------------------------------------------
定理4.2
<A, ≦> を整列順序集合とする。任意の要素 a ∈ A に対し、 a0 ≦ a となる
A の極小元 a0 が存在する。
------------------------------------------------------------------
と書いてあります。そして、その証明が以下の画像のように書かれています：
URLﾘﾝｸ(imgur.com)
そこで、質問です。
なぜ、↑のようにわざわざ証明をしているのでしょうか？
「<A, ≦> は整列順序集合だから、最小限 m が存在する。
a0 := m とすればよい。」とだけ書けば済むと思うんです。
1006:１３２人目の素数さん
16/06/06 14:25:49.65 7BpBxd+J.net
すみませんが、またまた質問があります。
URLﾘﾝｸ(imgur.com)
↑の画像の(2) ⇒ (1)が今読んでいる本では証明が省略されているので、自分で証明を試みました。
ただ、すこし自信がありません。
証明は以下で、あっているでしょうか？
1007:１３２人目の素数さん
16/06/06 14:26:19.85 7BpBxd+J.net
R を集合 A 上の二項関係とする。このとき
2) R に関する構造帰納法が成立すると仮定する。
⇒
1) R は整礎である。
【証明】
以下の定理4.1を利用して証明する。
定理4.1：
集合 A 上の2項関係 R が整礎であるための必要十分条件は、 A の要素の列 <a_n | n ∈ N> ですべての i ∈ N に対し、
a_(i+1) R a_i かつ a_(i+1) ≠ a_i となるものは存在しないことである。
A の任意の要素 x に対して、 a_0 = x、a_(i+1) R a_i かつ a_(i+1) ≠ a_i
となるような A の要素の列 <a_n | n ∈ N> が存在しないことを R に関する
構造帰納法により証明する。
x R y かつ x ≠ y となるすべての x について、
a_0 = x、a_(i+1) R a_i かつ a_(i+1) ≠ a_i
となるような A の要素の列 <a_n | n ∈ N> が存在しない
と仮定する。
このとき、
a_0 = y、a_(i+1) R a_i かつ a_(i+1) ≠ a_i
となるような A の要素の列 <a_n | n ∈ N> が存在すると仮定すると
矛盾が起きることを以下で示す。
x := a_1
b_i := a_(i+1) (i = 0, 1, …)
とおく。
仮定により、 x R y かつ x ≠ y であり、
b_0 = x、 b_(i+1) R b_i かつ b_(i+1) ≠ b_i
であるから、
「x R y かつ x ≠ y となるすべての x について、
a_0 = x、a_(i+1) R a_i かつ a_(i+1) ≠ a_i
となるような A の要素の列 <a_n | n ∈ N> が
存在しない」という仮定に反する。
よって、
a_0 = y、a_(i+1) R a_i かつ a_(i+1) ≠ a_i
となるような A の要素の列 <a_n | n ∈ N> は存在しない。
以上より、構造帰納法により、 A の任意の要素 x に対して、
a_0 = x、a_(i+1) R a_i かつ a_(i+1) ≠ a_i
となるような A の要素の列 <a_n | n ∈ N> が存在しないことが
示された。
定理4.1により、 R は整礎である。
【証明終わり】
1008:１３２人目の素数さん
16/06/06 16:56:13.90 fk4i0hhd.net
>>976
合ってるけど、その定理4.1は従属選択公理を使わないと
導けないので、あまり好きではない。
基本的に、点列の議論に落とし込むときには、
そこで従属選択公理が必要になることが多い。
点列の議論をしなくても、 構造帰納法⇒整礎 は導ける。
1009:１３２人目の素数さん
16/06/06 17:32:30.55 cSauNd7/.net
選択公理のない整列集合って意味あるのか？
1010:１３２人目の素数さん
16/06/06 17:45:31.42 7BpBxd+J.net
>>977
ありがとうございました。
選択公理は何が言いたいのかよく分かっていません。
勉強してみようと思います。
1011:１３２人目の素数さん
16/06/06 21:32:07.78 fk4i0hhd.net
>>979
点列は帰納的な手順で構成するのが一般的。
しかし、a_1,…,a_i までの点列が構成できたときに、
a_{i＋1}をどうやって選び出すのかが問題になる。
a_{i＋1}の候補が保証されていても、その候補の中から
1つ選び出さなければならない。普通はそこで、
従属選択公理が必要になる。
1012:１３２人目の素数さん
16/06/07 18:10:03.50 y24GgR47.net
>>980
ありがとうございます。
選択公理がなぜ必要なのかが理解できません。
選択公理が本当に必要なことを理解するには、選択公理が他の公理から独立である
ということの証明を読まなければならないのでしょうか？
それと、他にも無意識的に使っているが公理としなければならないものがあるのでは
ないかと考えてしまいます。
1013:１３２人目の素数さん
16/06/07 19:06:53.44 EgoicPeA.net
>>981
定理4.1の証明に従属選択公理が「必須」であることの証明は、実は俺も知らない。
定理4.1のような、点列に関する議論を普通に行うと、
「どうしても従属選択公理を使ってしまう」という経験則は知っている。
なぜなら、点列の構成においてa_{i＋1}を作るときに、実際にそこで1つ
元を選び出さなければならず、その行為はまさに属選択公理だからだ。
一般に、可算無限回の手続きがあって、その中の各ステップで1つずつ
何かを選び出しているとき、その行為は従属選択公理そのものである。
1014:１３２人目の素数さん
16/06/07 19:07:31.61 BSGTwmRQ.net
証明じゃなくググって説明を読め
探せば納得できる説明も見つかるだろ
1015:１３２人目の素数さん
16/06/07 20:55:30.48 M0ITkbib.net
ある条件を満たすものが存在する（もしくは、ある集合が空でない）という仮定の下で
その条件を満たすもの（その集合の元）をaと表して、aに関して議論する
これは数学の証明で当たり前に行われている推論方法の一つ
ただし、証明はこのような推論の有限回の積み重ねでなければならない
無限に長い証明というものは認めない
件の点列の議論をそのまま読むと
「ある条件を満たすものをa_1と表す」 「別のある条件を満たすものをa_2と表す」 「そのまた別のある条件を満たすものをa_3と表す」 …
というように無限回の推論を行っていることになり、このままでは証明として正当化できない
そこで、この種の議論を正当化するために
「空でない集合からなる集合族(A_i)があるとき、各集合A_iから元を一斉に選び出す写像fの存在を保証する
つまりf(A_i) = a_i ∈ A_i」
という選択公理を認めることにより、件の点列の議論を疑似的に正当化する
1016:１３２人目の素数さん
16/06/07 21:31:45.89 BSGTwmRQ.net
ところで、無限推論を認めると矛盾する例ってあったかな？
1017:１３２人目の素数さん
16/06/07 22:16:22.12 J28iYUpe.net
おばかさんなんで、
従属選択公理と可算選択公理の違いがわかりません。
教えて、えらいひと。
選択公理と可算選択公理の違いは、わかります。
1018:１３２人目の素数さん
16/06/07 22:23:25.59 +hi5ZoTT.net
次スレだけど高校範囲はすでにあるから
大学学部レベル質問スレにしない？
1019:１３２人目の素数さん
16/06/07 22:32:56.71 Dv9Gubi0.net
埋め
1020:１３２人目の素数さん
16/06/07 22:48:29.40 +hi5ZoTT.net
次スレ
大学学部レベル質問スレ 2単位目 [無断転載禁止]©2ch.net
ｽﾚﾘﾝｸ(math板)
1021:１３２人目の素数さん
16/06/08 13:13:27.58 4DqAgVj4.net
>>986
「必要なとき」と「一斉に」
1022:￥ ◆2VB8wsVUoo
16/06/08 22:52:50.44 qOgoDwjT.net
￥
1023:￥ ◆2VB8wsVUoo
16/06/08 22:53:09.66 qOgoDwjT.net
￥
1024:￥ ◆2VB8wsVUoo
16/06/08 22:53:28.74 qOgoDwjT.net
￥
1025:￥ ◆2VB8wsVUoo
16/06/08 22:53:47.50 qOgoDwjT.net
￥
1026:￥ ◆2VB8wsVUoo
16/06/08 22:54:06.46 qOgoDwjT.net
￥
1027:￥ ◆2VB8wsVUoo
16/06/08 22:54:24.15 qOgoDwjT.net
￥
1028:￥ ◆2VB8wsVUoo
16/06/08 22:54:42.29 qOgoDwjT.net
￥
1029:￥ ◆2VB8wsVUoo
16/06/08 22:55:12.07 qOgoDwjT.net
￥
1030:￥ ◆2VB8wsVUoo
16/06/08 22:55:32.53 qOgoDwjT.net
￥
1031:￥ ◆2VB8wsVUoo
16/06/08 22:55:52.80 qOgoDwjT.net
￥
1032:１３２人目の素数さん
16/06/08 23:02:07.52 rB7pydo1.net
猫埋め
1033:１３２人目の素数さん
16/06/09 00:19:58.73 QYPhPqLC.net
猫しぐさ
1034:1001
Over 1000 Thread.net
このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。
life time: 443日 0時間 56分 41秒
1035:過去ログ ★
[過去ログ]
■ このスレッドは過去ログ倉庫に格納されています