フリードバーグ・ナンバリング
これは不合理。
アクセプタブル・ナンバリングに対してはライスの定理が成立する。例えば2つの自然数が同じ関数の指標であるかは決定不能である。ところがフリードバーグ・ナンバリングは単射なので、2つの自然数が同じ関数の指標であるかは決定可能である。したがってフリードバーグ・ナンバリングに対してはライスの定理が成立しない。
ナンバリング(の同値類)の全体は還元可能性によって上半束の構造を持つ。これをロジャース半束(英: Rogers' semilattice)という。いま φ {\displaystyle \varphi } をフリードバーグ・ナンバリングとする。また ψ {\displaystyle \psi } を φ {\displaystyle \varphi } に還元可能なナンバリング、 f {\displaystyle f} をその還元関数とする。すなわち ψ i = φ f ( i ) {\displaystyle \psi _{i}=\varphi _{f(i)}} である。そこで g ( i ) = μ j . ( f ( j ) = i ) {\displaystyle g(i)=\mu j.(f(j)=i)} なる帰納的関数を考える。