X
トップページ⇒数学
615コメント174KB

集合論について

■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
垢版 |
2013/11/18(月) 04:05:17.08
いくらなんでも数学板に集合論全般を扱うスレがないのはおかしいだろ
0126１３２人目の素数さん
垢版 |
2014/03/08(土) 12:48:38.78
MSRIって凄いですな 日本で言えば,京大のリポジトリで過去のRIMS研究集会の講演内容を公開してる感じなのかな
0127１３２人目の素数さん
垢版 |
2014/03/08(土) 16:26:39.54
>>107と>>117でだいぶ言ってることが違ってる気がするけど。
>>116までを読む限り、公理系が完全なのは前提みたいな書き方だから
2^n通りを虱潰しに調べりゃ良いじゃないか、ということになる。

なんで命題論理の公理図式は一般に3つだと思うようになったのか知らないけど
その体系の公理図式が3つであるのは偶然で、大した意味は無いよ
メレディスの図式みたいに一個からトートロジーを全て導き出せるようなものもある

ウカシェヴィチの公理系から上の三つを頑張って示すか、
ウカシェヴィチの公理系が完全であることの証明が載ってる文献を探すのが一番近道だと思う。

＞ヒラメキなして自動的に判断するアルゴリズムが必要
そんなアルゴリズムあるのかなあ。そもそも無い可能性もある気がするけど。
0128１３２人目の素数さん
垢版 |
2014/03/08(土) 17:49:04.92
>>117
＞ルカシーヴィッツの公理系も同等の性質を持つ公理系らしい

違うと思う
117の公理系では重複する前提を１つにまとめられないと思う
0129１３２人目の素数さん
垢版 |
2014/03/08(土) 17:55:32.28
>>128のつづき

例えば(L1)〜(L3)で
（Ａ⇒（Ａ⇒Ｂ））⇒（Ａ⇒Ｂ）
を証明できる？
0130１３２人目の素数さん
垢版 |
2014/03/08(土) 20:22:17.65
>>128-129

129 の命題式は恒真なので、(L1)〜(L3) から証明できると思ってました

自分のネタ元は
Elliott Mendelson 『Introduction to Mathematical Logic, 5th ed.』
の
Exercise 1.58
で
"Prove that a wf B of L is provable in L if and only if B is a tautology."
とあります
0131１３２人目の素数さん
垢版 |
2014/03/08(土) 20:35:07.14
>>127
＞ >>107と>>117でだいぶ言ってることが違ってる気がするけど。
＞ >>116までを読む限り、公理系が完全なのは前提みたいな書き方だから
＞ 2^n通りを虱潰しに調べりゃ良いじゃないか、ということになる。

とすると、>115 のアルゴリズムはまだ自分では把握できていないのですが、
上記のような考え方でのアルゴリズムになるんですかね？

＞ ウカシェヴィチの公理系から上の三つを頑張って示すか、
＞ ウカシェヴィチの公理系が完全であることの証明が載ってる文献を探すのが一番近道だと思う。

確かに目の前のエクササイズの解答を得るにはそれが良さそうですが、それでも
別の ｎ個の公理図式を与えた場合はどうか、また別の…、というふうに
いくらでも問うことができて、そのたびに解くためにヒラメキが必要とされるのであれば
一般的に解けたといいにくいなあと思うので

＞＞ヒラメキなして自動的に判断するアルゴリズムが必要
＞ そんなアルゴリズムあるのかなあ。そもそも無い可能性もある気がするけど。

まだ誰も研究テーマにしたことないでしょうか？
0132１３２人目の素数さん
垢版 |
2014/03/09(日) 00:00:03.36
かなり踏み込んだ話題でもレスしてくださる方がいらっしゃるようですが,
じゃあ,私も山本新先生の数学基礎論についても埋めれなかった行間が沢山あるんですが・・・
0136１３２人目の素数さん
垢版 |
2014/04/01(火) 02:12:29.10
無限公理として ∃y(φ∈y∧∀x(x∈y→x∪{x}∈y)) を採用した場合、
∃y(φ∈y∧∀x(x∈y→{x}∈y)) は証明できますか？
0137１３２人目の素数さん
垢版 |
2014/04/01(火) 02:39:15.45
置換公理があれば可能、なければ
ZC（ZFC - 置換公理 + 分出公理）では不可能
0139１３２人目の素数さん
垢版 |
2014/04/01(火) 15:00:34.74
可能である事を主張するのは,証明図を見つけたらいいだけいい一方,,
不可能である事を主張するのって大分困難だと思ってるんですが,
それをささっとレスして凄いですね。
0140１３２人目の素数さん
垢版 |
2014/04/01(火) 15:04:00.48
質問文を読んでから問題を検討したわけでもあるまいに
ささっとレスすることの何が凄いのだろうか
0141１３２人目の素数さん
垢版 |
2014/04/01(火) 21:12:47.16
最近公理的集合論の勉強を始めたばかりなのですが、
整列可能性と可算性の関係はどういう関係なのでしょうか？同じに見えるのですが。
また、選択公理の独立性は話題になるのに、置換公理や無限公理など他の公理の
独立性が話題になることが余りないのは何故なのでしょうか？
0142１３２人目の素数さん
垢版 |
2014/04/01(火) 23:10:36.51
割と有名な教科書にそのまま載ってます。
片方が成り立ってもう片方が成り立たないモデルを作れば良い。

>>141
可算⇒整列可能は成り立つけど
整列可能⇒可算は成り立たない。
実際、ちょっと厳密じゃない言い方になるけど
可算な整列順序の順序型の全体は整列可能だけど
ω＝aleph_0の次の基数になる。

置換公理や無限公理の独立性は選択公理より遥かに簡単に示せます。
これも丁寧に書いた教科書なら大抵載ってます。
0144１３２人目の素数さん
垢版 |
2014/04/02(水) 20:15:28.26
>>142
ありがとうございます。
可算でないのに整列可能ということがあり得るということですが、どうもよく
わかりません。非可算な集合を整列するとき、最初の可算部分を整列させた後、
残りの非可算の部分をどうやって整列させるのでしょうか？

ところで、無矛盾性や独立性を示すには、モデルの存在によって示すしか他に方法は
方法はないのでしょうか？モデルを持ち出さずに直接？示すことはできないのでしょうか？
また、モデルが矛盾するということはないのでしょうか？
0146１３２人目の素数さん
垢版 |
2014/04/02(水) 22:58:02.79
144は任意の非可算集合を整列させることを問題にしているけど
142で言っているのは非可算な整列集合が存在するということだけで、
後者を示すだけなら選択公理みたいなものは使わない。

無矛盾性について言えば、
証明を形式的に分析して0=1に至る証明が存在しないことを
何らかの方法で示すという証明論的方法もあるにはある。
正直あまり実用的な感じではないけど。

あとは教科書読んで勉強して下さい
0147１３２人目の素数さん
垢版 |
2014/04/03(木) 15:40:43.86
>142で言っているのは非可算な整列集合が存在するということだけで、
>後者を示すだけなら選択公理みたいなものは使わない。
実数の集合がその例ですね。非可算かつ自然な順序関係によって整列される
0148１３２人目の素数さん
垢版 |
2014/04/03(木) 18:28:01.78
>>147
> 実数の集合がその例ですね。非可算かつ自然な順序関係によって整列される

？
0151１３２人目の素数さん
垢版 |
2014/04/04(金) 20:31:23.75
>>148
そうか、０以上の実数の集合、としても駄目ですね。
じゃあ、非可算な整列集合ってどういうものだろう？
整列って変な性質ですね
0153１３２人目の素数さん
垢版 |
2014/04/04(金) 22:53:16.63
選択公理はどこが変なのでしょうか？無限公理が変だと思わないように
選択公理も全然変だと思わないですけどね。
整列の方は、可算でもなく単なる全順序でもないという、なんだか変な
感じがするけど。
0154１３２人目の素数さん
垢版 |
2014/04/04(金) 23:39:15.03
147みたく教科書も読んでない人みたいなレスだな
0155１３２人目の素数さん
垢版 |
2014/04/04(金) 23:49:09.46
整列可能定理よりもZornの補題の方が遥かに「成り立ってそうな感じ」がする
0157１３２人目の素数さん
垢版 |
2014/04/05(土) 03:07:01.43
>>153
選択公理の帰結や、選択公理と同値な命題を色々眺めてれば何か悟るんじゃね？
0158１３２人目の素数さん
垢版 |
2014/04/05(土) 04:44:42.62
選択公理が変だと思う奴はあまりいないだろ
選択公理から出る結果が変だと思うから選択公理も疑われるだけ
有名なのはバナッハ・タルスキーの定理だな
0159１３２人目の素数さん
垢版 |
2014/04/05(土) 08:26:10.40
濃度をまともに扱いたければ結局選択公理に頼るしかなくなるから大抵は悟ることになる。
0160１３２人目の素数さん
垢版 |
2014/04/05(土) 12:48:31.25
>>151
たしかに変なことが起きるのは非可算な整列集合のときだけかもしれん
可算集合の場合はいくら選択公理を適用してもおかしなことは起きんのじゃないかな
0161１３２人目の素数さん
垢版 |
2014/04/05(土) 13:38:50.39
選択公理そのものは認めずに、可算選択や従属選択に制限してADつけ加えるとかもあるけど、実数を扱うならちゃんとした選択公理が欲しい。
たとえばRを、差が有理数な時同値という同値関係〜で類別した時に、従属選択ぐらいではR/〜の濃度がRの濃度より大きくなったりしてしまう。
0162１３２人目の素数さん
垢版 |
2014/04/06(日) 00:35:26.00
＞R/〜の濃度がRの濃度より大きくなったりしてしまう
それはバナッハ・タルスキーの定理よりもよっぽど気持ち悪いですね
0163１３２人目の素数さん
垢版 |
2014/04/06(日) 00:40:03.52
ここはお前の日記帳だ
0165１３２人目の素数さん
垢版 |
2014/04/06(日) 00:57:32.19
集合論が終わったのは全部ラッセルのせいらしいな
0168１３２人目の素数さん
垢版 |
2014/04/06(日) 10:36:34.63
ラッセルが、１足づつある靴下（左右の区別がつかない）の集合から片方を
一つづつ選んだ選択集合は作れないだろうという主旨のことを言っているが、
なんでつくれないんだっけ？
0169１３２人目の素数さん
垢版 |
2014/04/06(日) 11:08:33.83
写像というのは定義域のすべての要素に対してそれぞれ値がただひとつ決まらなければならない。重要なのは順に決めるんじゃなく、一気に全部決まる必要があること。写像は集合の一種。
脚が有限組なら、もちろん具体的に指示して前から順に靴下を選べばよい。終われば一気に決めたのと実質同じだから。しかし、無限組ある場合、このような具体的な指示ではいつまでも対応づけは終わらない。一気に決めた状態に辿り着くことはない。
無限にあっても前の組までの対応から次の組の対応が決まるならそれは具体的な指示だから値は決められるかもしれない。可算選択や従属選択が比較的嫌われないのはそのあたりにあるわけで、その意味で靴下のたとえはあまり適切ではないかも。
また、靴なら右を選ぶという具体的な指示ですべて一気に選べるだろう。
しかし、たとえば無限組の脚がぐちゃぐちゃな配置で前から並んでいない虫で、ペアとなる脚の組から靴下をひとつずつ選ぶ時、適当な指示を与える有効な手段は無いかもしれない。となると、一気に決まると断言することはできない。
選択公理はそれができると断言することにあたる。
0170１３２人目の素数さん
垢版 |
2014/04/06(日) 11:28:18.61
選択公理は、「そういう写像が在る」ということを主張しているだけで、
「そういう写像が決まる」ことを言ってるのじゃないから、ラッセルの
例は、選択公理に対する反例（というのかな）にはならないのでは？
0171１３２人目の素数さん
垢版 |
2014/04/06(日) 11:52:46.06
ラッセルのは反例というよりは、じゃあこの場合は本当に選択関数はあるの？という問いかけでしょう。あるというなら具体的に示して、と。
ヒルベルトの「神学」や、カントールの実無限に対する批判を見れば感じると思うけど、20世紀に抽象数学が発達する以前は具体的手段がないのに選択ができるというのは数学者のスタンダードから外れていた。
まだ選択公理批判が始まった頃はその感覚は相当残っていたんじゃないかと。
0172１３２人目の素数さん
垢版 |
2014/04/06(日) 11:54:36.43
互いに素な（空でない）集合からなる（空でない）集合　から代表元を選び出すことの喩え
左右の区別がつかないので、一斉に左を選ぶというような方法で代表元を指定することはできない
0173１３２人目の素数さん
垢版 |
2014/04/06(日) 11:55:55.92
急にポエム化が進んだな
0175１３２人目の素数さん
垢版 |
2014/04/06(日) 12:00:02.49
可算集合の場合はいくら選択公理を適用してもおかしなことは起きんのじゃないかな
0176１３２人目の素数さん
垢版 |
2014/04/06(日) 12:09:37.12
整列してあれば当然問題ないけどそのような構造を与えてない怪しい可算集合なら安心できないというのもひとつの考え方。
0178１３２人目の素数さん
垢版 |
2014/04/06(日) 12:40:09.79
ラッセルの靴下の例は選択公理の理解に有用だけど
「虚数集合」とか良く分からない用語を勝手に自分流で使ったりするのはアレだね
しかも集合論の話っぽくないし
0179１３２人目の素数さん
垢版 |
2014/04/06(日) 12:44:05.45
行列を習ったばかりの高校生が、複素係数の行列も考えられるのでしょうか？
という趣旨の質問をしたと解釈
0180１３２人目の素数さん
垢版 |
2014/04/06(日) 14:40:40.82
>>176
自然な整列ができない可算集合があるということ？
0181１３２人目の素数さん
垢版 |
2014/04/06(日) 15:41:58.79
可算ということは自然数全体の集合からの1対1ontoな写像はあるはずだから、それを具体的に与えれば整列できるはず。ただ、写像がある、というだけだと、具体的には整列しようがない。
0182１３２人目の素数さん
垢版 |
2014/04/06(日) 18:18:59.77
全単射があれば整列順序は得られるし
具体的な全単射があれば具体的な整列順序が得られるというだけの話じゃないの
0183１３２人目の素数さん
垢版 |
2014/04/06(日) 18:35:34.96
>>182
>全単射があれば整列順序は得られるし

それができるというのがまさしく可算選択公理なわけで。つい当たり前と思ってしまうが、自明からはほど遠い話。
0184１３２人目の素数さん
垢版 |
2014/04/06(日) 18:59:06.26
Xが可算集合であるとは全単射f:X→Nが存在することであり、
x, y∈X に対してx≦y⇔f(x)≦f(y)と定義すると(X,≦)は順序集合となり、fは順序同型写像。
ゆえに(X,≦)は整列集合である。

これだとどこか間違ってるの？
0185１３２人目の素数さん
垢版 |
2014/04/06(日) 19:18:19.83
具体的な全単射が指定されていればそれで整列できるが、全単射があるというだけではそのように順序を与えることができない。
0186１３２人目の素数さん
垢版 |
2014/04/06(日) 19:29:17.01
んん？？
そうなのか？

Xが可算集合であるとは∃f(fはXからNへの全単射)のことであり、
x, y∈X に対してx≦y⇔f(x)≦f(y)と定義すると(X,≦)は順序集合となり、fは順序同型写像。
ゆえに(X,≦)は整列集合である。
したがってXは整列可能な集合である(変数fは消えた)。

上の論証でも、Nが整列集合であることの証明でも、選択公理を使っていない。
0187１３２人目の素数さん
垢版 |
2014/04/06(日) 19:40:29.06
非可算無限ある全単射: X→N から一個の f を取り出すのはまさに選択公理でしょう
0188１３２人目の素数さん
垢版 |
2014/04/06(日) 19:48:48.12
それは選択公理ではなく、ヒルベルトのchoice operatorというやつなのでは。
不定にchoiceされたfは最終的に消えるので「可算集合は整列可能である」は証明できたことになると思う。
0189１３２人目の素数さん
垢版 |
2014/04/06(日) 20:06:02.05
何度繰り返しても選択公理を使ってないと思い込んでしまうくらい勘違いしやすいということだな。
0191１３２人目の素数さん
垢版 |
2014/04/06(日) 20:17:33.68
非常に芳しいやりとりだ。
0192１３２人目の素数さん
垢版 |
2014/04/06(日) 20:24:37.47
非可算集合は、選択公理のもとでも、整列可能だが、「具体的には整列
しようがない」のね？
0193１３２人目の素数さん
垢版 |
2014/04/06(日) 20:30:21.36
>>192 実数の全体について言えば、その種の言明は正しい。
0194１３２人目の素数さん
垢版 |
2014/04/06(日) 20:33:23.45
>>190
最終的な結論は「Xは整列可能である」、つまり∃R[ (X,R)は整列集合) ]だよ。
Rはただの束縛変数。
何の問題もないと思うけど。
0195１３２人目の素数さん
垢版 |
2014/04/06(日) 20:34:16.61
>>193
「実数の全体」という限定は必要ないのでは？

なお、可算集合は、選択公理がなくても、整列可能
0196１３２人目の素数さん
垢版 |
2014/04/06(日) 20:36:41.60
>>195 ω_1 のような非加算順序数の場合は？整列順序を、論理式
x∈y∨x＝y で定義できると思うけど。
0197１３２人目の素数さん
垢版 |
2014/04/06(日) 20:37:50.99
「芳しい」というより、「香ばしい」やりとりだな。
自然数の整列性は、自然数の定義にもよるだろうが、
普通の定義、例えばベアノの自然数なら、証明できる。
その上で、整列順序の存在は、
可算集合と自然数集合との全単射の存在と同値。
可算選択は、数学的帰納法に過ぎない。
0199１３２人目の素数さん
垢版 |
2014/04/06(日) 20:42:57.01
＞可算選択は、数学的帰納法に過ぎない。
可算整列は、数学的帰納法に過ぎない。
の間違い？
0202１３２人目の素数さん
垢版 |
2014/04/06(日) 21:06:39.40
>>183
可算選択公理 axiom of countable choice ってのは
A_n≠φ（n∈ω）のとき選択函数 f : N→∪A_n で f(n) ∈ A_nとなるものが存在する、
という主張のことを言うと思うんだけど。

https://www.google.co.jp/search?q=axiom+of+countable+choice

可算集合が整列できないなんていう変な主張のことじゃないよ。

一個以上あるものから一個を取り出すだけなら
（具体的なものを取れるかどうかは分からないけど）選択公理は要らない。
0204１３２人目の素数さん
垢版 |
2014/04/06(日) 21:16:21.36
>>203
だからそれ（存在量化された命題から、一つの実例を選び出す）は選択関数じゃないっての
選択公理とは、「存在量化された命題から、一つの実例を選び出す」という操作を無限回行えることを保証する公理
0205１３２人目の素数さん
垢版 |
2014/04/06(日) 21:20:20.28
「存在量化された命題から、一つの実例を選び出す」という操作を無限回　　しかも一括で　　行えることを保証する公理

と言った方がいいかも
0206１３２人目の素数さん
垢版 |
2014/04/06(日) 21:21:32.37
選択函数ってのは
空でない集合の族 F = {A_i} (i∈I), A_i ≠φがあったときに
f(i)∈A_i となるような函数
（つまり A_i たちからそれぞれ要素 f(i) をチョイスする函数）
のことを言う、という風に定義されてると思うけど。

選択函数とか或る集合が可算であるとか、可算選択公理とかの
定義を確認した方が良いと思う。
0207１３２人目の素数さん
垢版 |
2014/04/06(日) 21:42:22.59
与えられた集合 X の整列順序を ZFC の具体的な論理式で書き下してくれとか、
与えられた、空でない集合族 (A_i)_{i∈I} (A_i ≠ φ)の
選択関数を具体的に構成してくれとか、そういう要求でないのかな？
0208１３２人目の素数さん
垢版 |
2014/04/06(日) 22:07:51.00
そういう具体的に〜ってできるの？
0209１３２人目の素数さん
垢版 |
2014/04/06(日) 22:13:21.67
たとえば、実数の全体の整列順序関係を、ZFC + GCH 内で具体的な論理式で
書き下すことが不可能なことは、すでに知られているよ。
0210１３２人目の素数さん
垢版 |
2014/04/06(日) 22:14:55.10
>>192
バナッハタルスキの件も、「具体的には整列しようがない」非可算集合を整列しちゃう
ところから生じているの？
0213１３２人目の素数さん
垢版 |
2014/04/07(月) 01:22:10.73
バナッハ・タルスキーは、体積が違う球体が作れてしまうのが
選択公理のせいではないことは分かっている
0214１３２人目の素数さん
垢版 |
2014/04/07(月) 04:03:21.91
今までの議論ざっくり見ましたが,大学2,3年生ぐらいの議論という事ですか?
曖昧な表現や思い込み･勘違いな表現が多数見受けられましたが。
0215１３２人目の素数さん
垢版 |
2014/04/07(月) 07:04:16.99
単に定義について勘違いをしてた人が居ただけ
まああまり高度なポイントではなくて
きちんと本に書いてある定義に則って話をするかどうかということだけど
0216１３２人目の素数さん
垢版 |
2014/04/07(月) 07:07:01.78
選択公理→ハーンバナッハ→バナッハタルスキ
だから、選択公理のせいではないとは言えない
0218１３２人目の素数さん
垢版 |
2014/04/07(月) 10:22:44.34
>>215
定義の意味についての議論もあるね
0219１３２人目の素数さん
垢版 |
2014/04/07(月) 10:24:54.67
ACがあれば証明されるけどACより弱い定理から導かれるのでACが必要というわけではなくAC無しでも証明できる
0223１３２人目の素数さん
垢版 |
2014/04/07(月) 12:21:03.28
>>183を見る限り、定義の勘違いだけではなさそうだが…
本当は必要ないのに、特別な公理が必要だと思い違いをしてて、こっちの方が深刻
■ このスレッドは過去ログ倉庫に格納されています