2006-06-08 [長年日記]
λ. 正則性公理
<URL:http://d.hatena.ne.jp/kururu_goedel/20060608/1149748301>
数学ではともかく計算機科学では、正則性公理が直接役に立っている話はあまり聞かないし、むしろ循環構造を素直に集合として表現出来なくなるので、計算機科学では正則性公理はあんまし嬉しくない気がします。
そのような構造として例えばストリームがあります。 ストリームを集合論で扱うには、集合Aの要素からなるストリームの全体を「S = A×S を満たす最大のS」として、0,1,0,1,… というストリームは s = (0,(1,s)) という集合で扱うのが直観的で自然だと私は思います。しかし、これは反基礎の公理(AFA, Anti-Foundation Axiom)を公理にした集合論では可能ですが、正則性公理=基礎の公理(FA, Foundation Axiom)を公理にした集合論では不可能ですし。まあ、S = A×S ではなく S ≅ A×S に弱めれば正則性公理にも矛盾しないので、本質的な問題というよりはむしろ利便性の問題と思いますが。
おまけ
『反基礎の公理』について書こうとしたら、Myブログ軍師に「我が君･･･。『反基礎の公理』についてですか？ 炎上も覚悟の上でしょうな 」と言われたので、やめておく。
追記 (2006-06-20)
くるるの数学ノート - Antifoundation で、Aczelの『Non-well-founded sets』のPDFが公開されていることを知った。原典は向井先生の本棚にあったのをパラパラめくったことしかなかったので、後でちゃんと読んでみたいところだ。
それから、かがみさんの日記に以下のように書かれていた。「推移的崩壊」(transitive collapse)って何だろう。
Axiom of regularity に関してもちょっと書きたいことありなのですが、ぼろぼろになりそうなので今度機会があったら...。ただし、AFA を認める立場で Axiom of regularity が adhoc であるという批判 は成り立たないと思います(もちろん nuc さんが AFA を認めないというなら話は別ですが)。明らかに AFA の方が adhoc だと思うし、そもそも Axiom of regularity からのアイディアと思われる「推移的崩壊」をちゃっかり借用してるし。
fj.sci.math のこのスレッドには以下のように書かれていて、transitive collapse というのは Mostowski's collapsing lemma に関係した概念のような気がするが…… Mostowski's collapsing lemma 自体よく知らないのでした……とほほ。
「うそつき」では、AFA のことを、「Mostowski の Collapsing Lemma を、グラフが well-founded という仮定をはずした形に拡張したようなものだ」というような感じ(この通りの書き方ではない)で説明していました。これはちょっと公理的集合論を知っている人にはわかりやすい説明だと思います。
追記 (2006-06-21)
<URL:http://en.wikipedia.org/wiki/Mostowski_collapse> 読んで、Mostowski's collapsing lemma がどういうものか少し分かってきた。
