1.17

设 $g: \mathbb{N}\rightarrow \mathbb{N} \in \mathcal{PRF}, f: \mathbb{N}^2 \rightarrow \mathbb{N}$ ，满足 $f(x, 0)=g(x)$ $f(x,y+1) = f(f(\cdots f(f(x,y), y-1), \cdots),0),$ 证明：$f \in \mathcal{PRF}$

证明

证明 $f(x,y)$ 呈形 $g^{a(y)}(x)$

Basis: $y = 0, f(x,y) = f(x,0) = g(x), a(0) = 1$

假设 $f(x,y) = g^{a(y)}(x)$，那么， $\begin{array}{rl} f(x, y+1) &=f(f(\cdots f(f(x,y), y-1), \cdots), 0) \\ & = g^{a(0)}(f(\cdots f(f(x,y), y-1), \cdots), 1) \\ & = g^{a(0)+a(1)}(f(\cdots f(f(x,y), y-1), \cdots), 2) \\ & = g^{a(0)+a(1)+ \cdots a(n)}(x) \end{array}$ 从而，$a(0)=1, a(y+1) = a(0)+a(1)+\cdots +a(y)$

易见 $a(y) \in \mathcal{PRF}$，故 $f(x,y) = g^{a(y)} (x)$

令 $h(x,y) = g^y(x)$，因为 $\left\{\begin{array}{ll} h(x, 0) = x \\ h(x, y+1) = g(h(x,y)) \end{array}\right.$ $\therefore h \in \mathcal{PRF}$

$\because f(x,y)= h(x, a(y))$

$\therefore f \in \mathcal{PRF}$