原始帰納的関数

この規則を有限界適用して作られた関数

ゼロ

$ 0

原始帰納的関数

後継者関数

$ S(x) = x + 1

原始帰納的関数

射影

$ f(x_0, ..., x_n) = x_i(0 \leq i \leq n)

原始帰納的関数

合成

$ f, gは原始帰納的関数

$ f \circ g

原始帰納法

$ f, gは原始帰納的関数

$ h(x_0, ..., x_n, 0) = f(x_0, ..., x_n)

$ h(x_0, ..., x_n, S(y)) = g(x_1, ..., x_n, y, h(x_0, ..., x_n, y))

例

$ add(x, y) = x + y

$ f(x) = x

$ h(x, y, z) = z

$ g(x, y, z) = S(h(x, y, z)

$ add(x, 0) = f(x)

$ add(x, S(y)) = g(x, y, add(x, y))