計算論家トリイロさんと集合論家DIkeさんの対話

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika まぁ，E-recursion や E-closed sets について十分な知見があれば印象も変わるかもしれませんが。

Takayuki Kihara @tri_iro

@DaiskeIkegami @metaphusika なるほど。αはさておき実はEの方はあんまり知らないのですが、そのうちちゃんと十分な知見を身に付けておきます。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika あぁ，それで，E-recursion theory 固有のモチベーション・問題意識について何かご存知でしたら教えていただけるとありがたいです。

Ikegami Daisuke @DaiskeIkegami

@tenapi そうですね。> Jensen 理論にマージ　Jensen と Karp がやってた Primitive Recursive Set Functions も，集合論やってて refer することはそんなにないですよね。

Ikegami Daisuke @DaiskeIkegami

@tenapi Fine structure やってるときにちょっと見るくらいで。

Ikegami Daisuke @DaiskeIkegami

@tenapi まぁ，任意のαに対して，Jα 上で強制法を展開するのは厳しいので，ぎりぎりのところを見ようとすると，Mathias がやってるような weak set theory を見ることになりそうですが。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika Sacks がシンガポールでチュートリアルをしたときはスライド使ってたんですけど，そのスライドはちょっと web 上に見つかりませんでした。もし見つけたらお知らせしますね。

Takayuki Kihara @tri_iro

@DaiskeIkegami @metaphusika E-recursionについては詳しくないので、単純に、高階の計算論としては自然な形式化のようだ、という点くらいしか動機は分からないです。α-recursionだと、対象となる数学的概念が限られてきそうなので。

紫陽花の葉に青蛙とゼルプスト殿下 @tenapi

@DaiskeIkegami Sacks はRecursion Theory の大ボスという矜恃があるから、Jensen 理論に対するE-recursion の独自性を言いたいでしょうけど、実際のところどうなのでしょう。俺は両方勉強しなきゃならぬ立場なのですが、はてさて…

Ikegami Daisuke @DaiskeIkegami

@tenapi 計算論の立場からすると自然なものなのかもしれませんね。理論構成は admissible な再帰理論と比べるとそんなにきれいじゃない印象を受けましたが。また，これら二つと異なる高次の計算論が出てくるかもしれませんね。

紫陽花の葉に青蛙とゼルプスト殿下 @tenapi

@DaiskeIkegami 計算論の拡張はいろいろ試みられているのでしょうが、古典論のアナロジーから離陸できないことには多くの研究者を呼び込むことはできないと思います。俺はもう呼び込まれてしまってるのでいいんですが。

Takayuki Kihara @tri_iro

@tenapi @DaiskeIkegami αやEでもなく、BSS(Blum-Shub-Smale)やTTE(Type Two Theory of Effectivity)のような対象の一般化という方向性でもなく、計算の定義から全く異なる発想になることが必要ということでしょうか

紫陽花の葉に青蛙とゼルプスト殿下 @tenapi

@tri_iro @DaiskeIkegami 計算の対象の「本性」の解明になんらか寄与すべきだ、というくらいの意味で言いました。

紫陽花の葉に青蛙とゼルプスト殿下 @tenapi

@tri_iro @DaiskeIkegami エフェクティブな記述集合論はそこのところが奇跡的にうまくいっていると思います。

Takayuki Kihara @tri_iro

@metaphusika @DaiskeIkegami ここ http://t.co/gMjIZIStZo を見る限り，E-recursionの講義をしたようですが、Sacksの講義だけはデータのリンクが貼られていないみたいですね。

Ikegami Daisuke @DaiskeIkegami

@metaphusika @tri_iro E-recursion です。失礼しました。ええ，講義資料がウェブ上で見つからないのが残念です。

Ikegami Daisuke @DaiskeIkegami

集合論で使われている一般の集合上の「計算論」というと，パッと思いつくのは a) rudimentary functions, b) primitive recursive set functions と c) admissible set theory かな。

Ikegami Daisuke @DaiskeIkegami

@tenapi @tri_iro 僕は計算論の知識が乏しいので，エフェクティブな記述集合論が計算の対象の「本性」の解明に寄与しているかどうかわからないのですが，

Ikegami Daisuke @DaiskeIkegami

@tenapi @tri_iro エフェクティブな記述集合論がこれだけ成功しているのは，古典的な記述集合論に深い洞察と新しいものの見方を与え，多くの新しい数学的現象を観測させるまでに至った点が大きいと思います。

Ikegami Daisuke @DaiskeIkegami

@tenapi @tri_iro エフェクティブな記述集合論がどういう経緯で研究され始めたのか，という歴史はよく知りませんが，ω上の計算論の拡張として考えられたエフェクティブな記述集合論が古典的な記述集合論と結びついた当時は，この関連の発見は衝撃だったんだろうなぁ ，と思います。

紫陽花の葉に青蛙とゼルプスト殿下 @tenapi

@DaiskeIkegami @tri_iro 補解析的同値関係に関するSilverの定理やボレル同値関係についてのGlimm-Effros DichotomyがGandy-Harrington forcingによって証明されたりとか。計算対象としてボレル集合などを想定してます。

紫陽花の葉に青蛙とゼルプスト殿下 @tenapi

@DaiskeIkegami @tri_iro 点集合のハウスドルフ演算やコルモゴロフ階層を計算論的な観点から理解できたことも意義深かったとおもいます。

Ikegami Daisuke @DaiskeIkegami

@tenapi @tri_iro 確かに，anaylytic sets やボレル集合に対する理解はとても深まりましたし，新しい物の見方も導入されましたね。そういう意味で「計算」，「計算対象」をとらえているなら，完全に同意します。

Ikegami Daisuke @DaiskeIkegami

@tenapi @tri_iro そうですね。いろんなことがきれいにまとまっていった印象があります。

Ikegami Daisuke @DaiskeIkegami

@tenapi @tri_iro Rudimentary functions や fine structure についても同様のことが言えて，これらの理論によって，L や admissible set theory についての深い洞察，新しいものの見方が与えられ，