フリードバーグ・ナンバリング
フリードバーグ・ナンバリング（英: Friedberg numbering）は帰納的関数や帰納的可算集合の単射なナンバリング（枚挙）をいう。
このようなナンバリングの存在は1958年にリチャード・フリードバーグによって0'-優先法を用いて示された（Friedberg, 1958）。マルティン・クンマーは優先法を用いない構成法を与えた（Kummer, 1990）。
性質
Padding lemma により アクセプタブル・ナンバリングは単射ではない。もっといえば任意の帰納的関数は可算無限個の指標を持つ。したがってフリードバーグ・ナンバリングはアクセプタブルでない。
Smn定理の成立するナンバリングはアクセプタブルである。したがってフリードバーグ・ナンバリングに対してはSmn定理が成立しない。クリーネの再帰定理も同様。このことを見るためにフリードバーグ・ナンバリング [math]\varphi[/math] に対して再帰定理が成立すると仮定しよう。そこで [math]f(x)=x+1[/math] なる全域帰納的関数を考える。すると再帰定理より [math]\varphi_e = \varphi_{f(e)}[/math] なる自然数 [math]e[/math] が存在するはずである。ところが対応 [math]i \mapsto \varphi_i[/math] は単射であるから [math]e = f(e)[/math] でなければならない。すなわち [math]e = e + 1[/math] が成り立つ。これは不合理。
アクセプタブル・ナンバリングに対してはライスの定理が成立する。例えば2つの自然数が同じ関数の指標であるかは決定不能である。ところがフリードバーグ・ナンバリングは単射なので、2つの自然数が同じ関数の指標であるかは決定可能である。したがってフリードバーグ・ナンバリングに対してはライスの定理が成立しない。
ナンバリング（の同値類）の全体は還元可能性によって上半束の構造を持つ。これをロジャース半束（英: Rogers' semilattice）という。いま [math]\varphi[/math] をフリードバーグ・ナンバリングとする。また [math]\psi[/math] を [math]\varphi[/math] に還元可能なナンバリング、[math]f[/math] をその還元関数とする。すなわち [math]\psi_{i} = \varphi_{f(i)}[/math] である。そこで [math]g(i) = \mu j.(f(j) = i)[/math] なる帰納的関数を考える。 [math]\varphi[/math] は全単射であること、また [math]\psi[/math] は全射であることより、[math]f[/math] は全射でなければならない。ゆえに [math]g[/math] は全域的である。 [math]\psi_{g(i)} = \varphi_{f(g(i))} = \varphi_{i} [/math] であるから、 [math]\varphi[/math] は [math]\psi[/math] に還元可能である。 したがって [math]\varphi[/math] は還元可能性に関して極小である。
標準的なナンバリングからフリードバーグの方法で得られるフリードバーグ・ナンバリングのほかに、還元可能性の意味で同値でない別のナンバリングが存在する（Pour-El, 1964）。したがってロジャース半束は束ではない。というのも、このことと上の結果とを考え合わせると、比較不能な2つの極小元が存在することになり、それらの交わり（下限）は存在しないからである。
関連項目
参考文献
- Nigel Cutland (1980), Computability: An Introduction to Recursive Function Theory, Cambridge University Press. ISBN 9780521294652.
- Richard M. Friedberg (1958), Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication, Journal of Symbolic Logic 23:3, pp. 309–316.
- Martin Kummer (1990), An easy priority-free proof of a theorem of Friedberg, Theoretical Computer Science 74(2), pp. 249-251.
- Marian B. Pour-El (1964), Gödel Numberings Versus Friedberg Numberings, Proceedings of the American Mathematical Society 15(2), pp. 252-256.
- Nikolaj K. Vereščagin and A. Shen (2003), Computable Functions, American Mathematical Soc.