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

Takayuki Kihara @tri_iro

そういや以前Noam Greenbergから非可算構造上の計算可能モデル理論の話を聞いた（admissible ordinal上のいわゆるα-再帰理論を使う形式）けど、最近それ系の話題が流行り出したのだろうか： http://t.co/iZMX3WZtM2

Takayuki Kihara @tri_iro

非可算の計算論は前世紀に大規模な研究が行われていて、Odifreddiとか、あるいは今は逆数学で知られるS. G. Simpsonが、非可算再帰理論の教科書書くよ宣言を前世紀にしていたものの、世紀末前に何故かこの種の研究が急速に終息し、結局、教科書出る出る詐欺に終わっていたという

Takayuki Kihara @tri_iro

で、結局admissible ordinal上の計算論に関するまともな教科書がSacksのHigher Recursion Theory http://t.co/XVY8jlxNvV しか存在しないという状況だったのであるけれど、これがついに改善されるのだろうか。

Takayuki Kihara @tri_iro

計算論は、まわりに「役に立つ」研究が多すぎたせいで、数学的に重要で美しいけど一見あんまり役に立たない系の研究が後回しにされてしまっている傾向があるのではないだろうか説

H. Miyoshi (ALC Japan is rescheduled in 2025) @metaphusika

@tri_iro 私が学生の頃はhigher recursionについてはなんとなくやりづらい雰囲気を感じていました。興味を持ってもそこからどう進めればいいのかよくわからない的な。そう考えると当時のrecursion theoryの衰退は日本だけでなく世界的な傾向だったのかな？

Takayuki Kihara @tri_iro

@metaphusika 憶測ですが、Sy Friedmanを初めとしたhigher recursion研究者が現在は集合論の研究者と認識されているように、集合論と興味を共有しすぎたせいで、その辺りの分野が衰退したというか、集合論と一体化したのかなという印象があります。

Takayuki Kihara @tri_iro

@metaphusika Recursionと集合論の興味の方向性が近すぎたせいで、higher recursionと集合論は融合していたけれど、最近その辺りにrecursion特有の興味が浮上してきて、higher recursionが再分離しつつあるのではないかなと思ってます

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika Admissible 再帰理論の手法やものの考え方は，記述集合論や fine structure の研究で頻繁に使われています。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika 一方で，α-recursion の方は，集合論をやる立場としてはどうも使い勝手が悪い，という印象を持っています。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika この前の夏に，シンガポールのサマースクールで Sacks のα-recursion についてのチュートリアルを聴いたんですが，強制法の一般論を α-recursion でやるとかなり複雑で，いじりづらい感じでした。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika KP での強制法は，ZF の場合と同様にできちゃうので，admissible な再帰理論の方が集合論の物の見方には fit している感じがします。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika もし，α-recursion 固有のモチベーション，問題意識についてご存知でしたら，教えていただけるとありがたいです。Sacks のチュートリアルではそういう部分についての言及がなかったので。

Takayuki Kihara @tri_iro

@DaiskeIkegami @metaphusika 個人的に、α-recursionはadmissibleな再帰理論の一部というイメージだったんですが、ここら辺をどう区別されている感じですか？

Takayuki Kihara @tri_iro

@DaiskeIkegami @metaphusika α-recursionが扱いづらいというのは、これが単にKP集合論のモデルを扱うわけでなく、実際はモデルの外側というか、admissible ordinalの部分集合のdegreeを取り扱うという理由からになるのでしょうか

Takayuki Kihara @tri_iro

@DaiskeIkegami @metaphusika 同型な2つの非可算構造が与えられたとき、どれ位の次数の同型が取れるかや、ある非可算構造を表現するのに必要な次数を調べる、という目的でα-再帰理論を使うという研究が最近出てきたので、新しい方向性が出てきたのかなという印象です。

Takayuki Kihara @tri_iro

@DaiskeIkegami @metaphusika といっても、これがα-recursion固有のモチベーションといっていいかは分からないというか、記述集合論っぽい話になれば類似の研究はありそうな気もしますが。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika ごめんなさい，タイポです…。「α-recursion」ではなく「E-recursion」の話をしていました…。

Takayuki Kihara @tri_iro

@DaiskeIkegami @metaphusika あ、E-recursionの方でしたか。αとEの扱いづらさの差というのは、KP集合論と高階算術に対する強制法の取り扱いのむずかしさの差みたいな感じになるのでしょうか。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika 失礼しました。> タイポ　E-recursion の場合，E-recursive function について閉じている集合上で強制法をするわけですが，こういう集合が KP のモデルと比べて結構扱いづらいんです（特に強制法をするときは）。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika 高階算術のモデルの場合，フルに Comprehension があれば，集合論のブール値モデルの場合と同様に強制法の理論は扱えて，結構使い勝手がいいです。フルに Comprehension がないときはあまり知らないんですが。

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

α-recursion と E-recursion を間違えたとな？ 東広島市と北広島市ぐらいちがいそうやねんけど…

Takayuki Kihara @tri_iro

@DaiskeIkegami @metaphusika αは平べったくて、Eは何か積み重なってる印象があるので、見る深さの違いというか、確かにEの方が強制法をやるのは大変そうだなあというイメージはなんとなく伝わってきます（実際はもっと複雑な理由なんでしょうけれども）

Ikegami Daisuke @DaiskeIkegami

@tenapi えぇ，ごめんなさい…

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

@DaiskeIkegami 松山市と東松山市もかなり違いそうです。てか結局集合論的にはJensen理論にマージされそうな気がします。

Ikegami Daisuke @DaiskeIkegami

@tri_iro @metaphusika ええ，E-recursive function の構成に関する帰納法で頑張って force relation を定義していくんですけど，定義するときにすでに E-recursion の基本的な定理をバリバリ使ってややこしい感じでした。