|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
フリードバーグ・ナンバリング（）は帰納的関数や帰納的可算集合の単射なナンバリング（枚挙）をいう。 このようなナンバリングの存在は1958年にリチャード・フリードバーグによって0'-優先法を用いて示された（Friedberg, 1958）。マルティン・クンマーは優先法を用いない構成法を与えた（Kummer, 1990）。 ==性質== Padding lemma により アクセプタブル・ナンバリングは単射ではない。もっといえば任意の帰納的関数は可算無限個の指標を持つ。したがってフリードバーグ・ナンバリングはアクセプタブルでない。 Smn定理の成立するナンバリングはアクセプタブルである。したがってフリードバーグ・ナンバリングに対してはSmn定理が成立しない。クリーネの再帰定理も同様。このことを見るためにフリードバーグ・ナンバリング に対して再帰定理が成立すると仮定しよう。そこで なる全域帰納的関数を考える。すると再帰定理より なる自然数 が存在するはずである。ところが対応 は単射であるから でなければならない。すなわち が成り立つ。これは不合理。 アクセプタブル・ナンバリングに対してはライスの定理が成立する。例えば2つの自然数が同じ関数の指標であるかは決定不能である。ところがフリードバーグ・ナンバリングは単射なので、2つの自然数が同じ関数の指標であるかは決定可能である。したがってフリードバーグ・ナンバリングに対してはライスの定理が成立しない。 ナンバリング（の同値類）の全体は還元可能性によって上半束の構造を持つ。これをロジャース半束（）という。いま をフリードバーグ・ナンバリングとする。また を に還元可能なナンバリング、 をその還元関数とする。すなわち である。そこで なる帰納的関数を考える。 は全単射であること、また は全射であることより、 は全射でなければならない。ゆえに は全域的である。 であるから、 は に還元可能である。 したがって は還元可能性に関して極小である。 標準的なナンバリングからフリードバーグの方法で得られるフリードバーグ・ナンバリングのほかに、還元可能性の意味で同値でない別のナンバリングが存在する（Pour-El, 1964）。したがってロジャース半束は束ではない。というのも、このことと上の結果とを考え合わせると、比較不能な2つの極小元が存在することになり、それらの交わり（下限）は存在しないからである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「フリードバーグ・ナンバリング」の詳細全文を読む スポンサード リンク
|