1.2

证明：对任意 $k \in \mathbb{N}^{+}$，$f: \mathbb{N}^k \rightarrow \mathbb{N}$，若 $f \in \mathcal{BF}$，则存在 $h$，使得 $f(\vec{x}) < \|\vec{x}\|+h$ 其中 $\|\vec{x}\| = \max\{x_i; 1\leq i \leq k\}.$

证明

设 $f \in \mathcal{BF}$

• case 1：如果 $f$ 为零函数 $Z$，后继函数 $S$，或投影函数 $P_i^n$ 之一， $Z(x) < x+1, \quad S(x)<x+2, \quad P_i^n(\vec{x})<\|\vec{x}\|+1$ 显然存在这样的 $h$；

• case 2：设 $f(\vec{x}) = g(g_1(\vec{x}), g_2(\vec{x}), \cdots, g_m(\vec{x}))$

  设 $g(\vec{y}) < \|\vec{y}\| + h_0$，$g_i(\vec{x_i}) < \|\vec{x}\|+h_i\ (i = 1,2,3, \cdots, m)$

  从而$f(\vec{x}) < \max_{1\leq i \leq m} g_i(\vec{x}) + h_0<\max_{1\leq i \leq m}(\|\vec{x}\|+ h_i) + h_0 < \|\vec{x}\|+ h_0+h_1+ \cdots + h_m$

  取 $h = h_0+h_1+ \cdots + h_m$ 即可。