数学的構造における決定手続きの研究

点击翻译按钮获取中文摘要

本年度は,構造とその中である述語で定義される部分構造との関係を中心に研究を行なった.L-構造Mがあるとする.Lに一変数述語PがあるときN=M^Pを考えるとNは自然にL^-=L＼{P}構造になる.ここで,Nの中の関係が外側のMの中で定義されるとすると,それはすでにNの中で定義されているという状況を考える.このときMはN上reduction propertyをもつという.この性質を厳密に定義しようとすると何通りかの定義が考えられる.そこで,O-reduction property,reduction property,strong reduction property,uniform reduction propertyという性質を提唱し,これらの性質の相互関係を調べ,またこれらの条件のもとでNの性質がどの程度Mに移るかを調べた.Mの理論が安定の場合はO-reduction propertyがstrong reduction propertyを除いて最も強く,reduction propertyとuniform reduction propertyが同値になる.一般にはstrong reduction propertyからreduction propertyが導かれるが,他のものは独立な性質になることが分かった.Mが可算モデルのとき,その理論がP上極小でstrong reduction propertyをもつならばNの〓_0-範疇性はMに移る.0-reduction propertyしか成り立たない場合には,構造を増やしてこの反例に拡張する一般的方法を与えた.さらに,Mの理論TがP上極小でuniform reduction propertyをもつ場合,Nの理論T^-が〓-安定ならばTもそうなり,また単次元性も移ることを示した.O-reduction propertyだけある場合は,上と同様に反例に拡張できる.他に,非決定性と交代Turing機械の間の関係,n×n盤上のオセロゲームの計算量の決定,ジャンプナンバー問題に関する研究などを行なった.