ライス＝シャピロの定理
I n d e x ( A ) {\displaystyle \mathrm {Index} (A)} は帰納的可算であるから、 N ∖ W e {\displaystyle \mathbb {N} \setminus W_{e}} も帰納的可算である。これは W e {\displaystyle W_{e}} の取り方に反する。
次に f を A に属さない部分帰納的関数で、 f の有限部分 g で A に属すものが存在すると仮定する。帰納的でない帰納的可算集合 W e {\displaystyle W_{e}} を取る。次の部分帰納的関数を考える:
h ( x , y ) = { f ( y ) g ( y ) ↓ or x ∈ W e ↑ otherwise {\displaystyle h(x,y)={\begin{cases}f(y)&g(y)\downarrow {\mbox{ or }}x\in W_{e}\\\uparrow &{\mbox{otherwise}}\end{cases}}}
smn定理より φ k ( x ) ( y ) = h ( x , y ) {\displaystyle \varphi _{k(x)}(y)=h(x,y)} なる全域帰納的関数 k が存在する。明らかに φ k ( x ) ⊆ f {\displaystyle \varphi _{k(x)}\subseteq f} が成り立つ。次の2つの場合が考えられる: