Smn定理
本定理の基本形は、2引数の関数に適用される。再帰関数のゲーデル数 φ {\displaystyle \varphi } が与えられたとき、次のような性質の2引数の原始再帰関数 s が存在する。すなわち、あらゆる2引数の関数 f のゲーデル数 p について、同じ x と y の組合せでの φ s ( p , x ) ( y ) {\displaystyle \varphi _{s(p,x)}(y)} と f ( x , y ) {\displaystyle f(x,y)} が定義され、その組合せにおいて等しい。言い換えれば、次のような外延的等価性が成り立つ。
φ s ( p , x ) = λ y . φ p ( x , y ) {\displaystyle \varphi _{s(p,x)}=\lambda y.\varphi _{p}(x,y)\,}
これを一般化するため、元の数を原始再帰関数で引き出せるように、n 個の数を1つの数に符号化する方法を採用する。