定理 IV

若 F 為雙元正整數遞迴函，其定義為對每個正整數 x 而言，都存在 y 使得 F(x,y) > 1。

則可建構函數 F*，對每個正整數 x 而言，F*(x) 等於最小正整數 y 使得 F(x,y) > 1，且 F* 是遞迴函。

F* 之遞迴等式如下，其中 f1 表示 F* 而 f2 表示 F：

i2(1   ,2      ) = 2 若 x = 1 且 y = 2，則傳回 2
i2(S(x),2      ) = 1 若 x > 1 且 y = 2，則傳回 1
i2(x   ,1      ) = 3 若 y = 1 則傳回 3
i2(x   ,S(S(y))) = 3 若 y > 2 則傳回 3

j2(1 ,y ) = y 若 x = 1 則傳回 y j2(S(x),y ) = x 若 x > 1 則傳回 x