"Mass Problem (1)" (S. G. Simpson)

研究集会 logic

16:50-17:50。講演の要旨とスライドはここより入手可能。

  1. "Mas problem"とは、Medvedevによって始められた一般化された決定問題である。この問題を考えることで、最終的には決定不可能な問題を分類することを目的としている。
    1. 通常のTuring degreeでは、 A\leq_T Bで、「A が解決できれば、B も解決できる」ということを表現している。しかし、Turing degereeによる分類が適切でないような種類の決定問題も存在する。
    2. 例：CPA (The completion of Arithmetic)
      • 不完全性定理により、PAは不完全である。CPAは、理論に論理式を加えていき、完全な理論にするという操作のことである。
      • まずポイントなのは、CPAは決定問題ではない。だから、Turing degree がCPAに関して適切な指標にはならない。
      • というのも、完全化の方法は、決して一つではないからである。例えば、Turing degree 0 から初めて、jumpを \omega回繰り返した 0^{(\omega)}は、いわゆる "True Arithmetic" に相当し、これは完全な算術を含む理論である。しかし、もちろん 0^{(\omega)}以外にも完全化は存在するはずである（そしてTuring degreeが\omegaより低いものが存在するはずである）。
      • このような一般化された（一つではなく集合に関する）決定問題を "Mass Problem" と呼ぶ。

（後日また続きを記入します）