フリードバーグ・ナンバリング（）は帰納的関数や帰納的可算集合の単射なナンバリング（枚挙）をいう。
このようなナンバリングの存在は1958年にリチャード・フリードバーグによって0'-優先法を用いて示された（Friedberg, 1958）。マルティン・クンマーは優先法を用いない構成法を与えた（Kummer, 1990）。
性質
Padding lemma により アクセプタブル・ナンバリングは単射ではない。もっといえば任意の帰納的関数は可算無限個の指標を持つ。したがってフリードバーグ・ナンバリングはアクセプタブルでない。
Smn定理の成立するナンバリングはアクセプタブルである。したがってフリードバーグ・ナンバリングに対してはSmn定理が成立しない。クリーネの再帰定理も同様。このことを見るためにフリードバーグ・ナンバリング に対して再帰定理が成立すると仮定しよう。そこで なる全域帰納的関数を考える。すると再帰定理より なる自然数 が存在するはずである。ところが対応 は単射であるから でなければならない。すなわち が成り立つ。これは不合理。
アクセプタブル・ナンバリングに対してはライスの定理が成立する。例えば2つの自然数が同じ関数の指標であるかは決定不能である。ところがフリードバーグ・ナンバリングは単射なので、2つの自然数が同じ関数の指標であるかは決定可能である。したがってフリードバーグ・ナンバリングに対してはライスの定理が成立しない。
ナンバリング（の同値類）の全体は還元可能性によって上半束の構造を持つ。これをロジャース半束（）という。いま をフリードバーグ・ナンバリングとする。また を に還元可能なナンバリング、 をその還元関数とする。すなわち である。そこで なる帰納的関数を考える。 は全単射であること、また は全射であることより、 は全射でなければならない。ゆえに は全域的である。 であるから、 は に還元可能である。 したがって は還元可能性に関して極小である。
標準的なナンバリングからフリードバーグの方法で得られるフリードバーグ・ナンバリングのほかに、還元可能性の意味で同値でない別のナンバリングが存在する（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.
外部リンク Institute of Mathematics