ライス＝シャピロの定理
A を部分帰納的関数の集合で、指標の集合 I n d e x ( A ) {\displaystyle \mathrm {Index} (A)} が帰納的可算であるものとする。
まず f が A に属す部分帰納的関数で、f のいかなる有限部分関数も A に属さないと仮定する。帰納的でない帰納的可算集合 W e {\displaystyle W_{e}} を取る(例えば W e {\displaystyle W_{e}} として停止性問題の対角線を取ればよい)。次の部分帰納的関数を考える:
g ( x , y ) = { ↑ x ∈ W e , y f ( y ) otherwise {\displaystyle g(x,y)={\begin{cases}\uparrow &x\in W_{e,y}\\f(y)&{\mbox{otherwise}}\end{cases}}}
ここで W e , y {\displaystyle W_{e,y}} は有限集合の帰納的な増大列で lim W e , y = W e {\displaystyle \lim W_{e,y}=W_{e}} が成り立つようなものとする。smn定理より φ h ( x ) ( y ) = g ( x , y ) {\displaystyle \varphi _{h(x)}(y)=g(x,y)} なる全域帰納的関数 h が存在する。明らかに φ h ( x ) ⊆ f {\displaystyle \varphi _{h(x)}\subseteq f} が成り立つ。次の2つの場合が考えられる:
いま A を(1変数)部分帰納的関数の集合で、指標の集合 I n d e x ( A ) = { e ∣ φ e ∈ A } {\displaystyle \mathrm {Index} (A)=\{e\mid \varphi _{e}\in A\}} が帰納的可算であるものとする。ここに φ {\displaystyle \varphi } は部分帰納的関数のアクセプタブル・ナンバリングである。
このとき任意の部分帰納的関数 ψ {\displaystyle \psi } について、次は同値:
ψ ∈ A {\displaystyle \psi \in A} ;
有限関数 θ {\displaystyle \theta } で θ ⊆ ψ {\displaystyle \theta \subseteq \psi } かつ θ ∈ A {\displaystyle \theta \in A} なるものが存在する。
ここで有限関数とは有限な定義域を持つ部分関数をいう。また θ ⊆ ψ {\displaystyle \theta \subseteq \psi } とは θ {\displaystyle \theta } の定義域で θ ( x ) = ψ ( x ) {\displaystyle \theta (x)=\psi (x)} が成り立つこと( θ {\displaystyle \theta } が ψ {\displaystyle \psi } の制限であること)をいう。