\Pi^0_1……">

翻訳と辞書 Words near each other ・ 低地フランク語 ・ 低地フランケン語 ・ 低地フランコニア語 ・ 低地ライン語 ・ 低地地方 ・ 低地帯 ・ 低地草原 ・ 低地諸国 ・ 低地農業 ・ 低域通過フィルタ ・ 低基底定理 ・ 低基礎代謝率 ・ 低塩症候群 ・ 低塩素化銅フタロシアニングリーン ・ 低塩素血 ・ 低塩素血(症) ・ 低塩酸 ・ 低塩酸(症) ・ 低塩食 ・ 低声 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 低基底定理 ： ミニ英和和英辞書 低基底定理[り] ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 基 ： [き, もとい] 　【名詞】 1. basis　 ・ 基底 ： [きてい] 　【名詞】 1. base　2. ground ・ 底 ： [そこ, てい] 　【名詞】 1. bottom　2. sole　 ・ 定理 ： [ていり] 　【名詞】 1. theorem　2. proposition ・ 理 ： [り] 　【名詞】 1. reason　 低基底定理 ： ウィキペディア日本語版 低基底定理[り] 計算可能性理論における低基底定理（）は $2^$ の任意の空でない$\backslash Pi^0\_1$クラス（算術的階層を見よ）は低次数の元を含むことを示す（Soare 1987:109）もので、1972年にカール・ジョックシュとロバート・アーヴィング・ソーアによって証明せられた（Nies 2009:57）。Cenzer (1993:53) はこれを"もしかすると $\backslash Pi^0\_1$ クラスの理論において最も引用されている結果"と記している。 この定理の証明には $\backslash Pi^0\_1$ クラスによる強制法が用いられている（Cooper 2004:330）。未出版の元々の証明では $0\text{'}$-構成が用いられていた（Diamondstone et al.:2010:135）。シェイファーはこの証明が実際には超低次数の元の存在を示していることを指摘した。この意味で強化された主張は超低基底定理と呼ばれる。 $\backslash Pi^\_$クラスは木の概念と密接に関係している。$\backslash Pi^\_$クラスに関する定理はしばしば木に関する定理として定式化される。低基底定理は「任意の計算可能な無限二分木は低い無限枝を持つ」ことを述べている。 == 歴史 == 1936年、デネス・ケーニヒは局所有限な無限グラフは無限道を持つことを示した。これはケーニヒの補題として知られている。系として有限分岐な無限木は無限枝を持つことが従う。これもケーニヒの補題と呼ばれる。これよりも弱い主張「任意の無限二分木は無限枝を持つ」は弱ケーニヒの補題と呼ばれる。これらの定理の証明には選択公理（より正確には従属選択公理やその弱形）が使用されており、その意味で非構成的である。 スティーヴン・コール・クリーネは弱ケーニヒの補題の計算可能バージョンが成立しないことを証明した（Kleene 1952）。すなわち、計算可能な無限二分木であって、計算可能な無限枝を持たないものを構成した。ここで構成されている木はクリーネ・ツリーと呼ばれることがある。クリーネ・ツリーの構成は再帰的分離不能対の存在と密接に関係している。 ゲオルク・クライゼルは計算可能な無限二分木は $0\text{'}$-計算可能（したがって極限計算可能）な無限枝を持つことを示した（Kreisel 1953）。この定理を利用してジョゼフ・ロバート・シェーンフィールドは計算可能な無限二分木は $0\text{'}$ よりも真に小さい次数の無限枝を持つことを示した(Shoenfield 1960)。 ジョックシュとソーアは計算可能な無限二分木は低次数の無限枝を持つことを示した(Jockusch and Soare: 1972)。この結果は上記の結果を精緻化するものである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「低基底定理」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.