7.2. 原始递归函数, 集合版本

基本 (Rudimentary) 在经典递归论中恰好指的是 $\mathbb{N}$ 上的 ${\Delta }_0$ 可定义性, 但我们显然常关注的更是原始递归. 我们这一节介绍集合版本的原始递归函数, 并追随 Rathjen 证明它们恰是 $KP$ 可证的 ${\Sigma }_1$ 函数符号——与 $\mathbb{N}$ 上的原始递归函数恰是 $PA$ 可证递归的函数符号遥相呼应.

定义 7.2.0.1. 我们预定一些 (当然是有穷个) 函数符号 ${\mathrm{G}}_{\mathfrak{i}}$, 然后在扩展语言中这样说: 在以下步骤下有穷步内被构造出来的函数符号 $F$ 称作在 $({\mathrm{G}}_{\mathfrak{i}})$ 下原始递归的函数符号, 记为 $F\in \mathrm{Prim}({\mathrm{G}}_{\mathfrak{i}})$:

1.	取初始函数 ${\mathrm{G}}_{\mathfrak{i}}$.
2.	取初始函数 $F(...)=\varnothing$.
3.	取初始函数 $F(x_0,...,x_{\mathfrak{n}})=x_{\mathfrak{k}}$.
4.	取初始函数 $F(x_0,x_1)=x_0\cup \{x_1\}$.
5.	取初始函数 $F(x_0,x_1,x_2,x_3)$, 当 $x_2\in x_3$ 时其值为 $x_0$, 否则其值为 $x_1$.
6.	复合.
7.	递归: $F(x_0,...,x_{\mathfrak{n}+1})=G(x_0,...,x_{\mathfrak{n}+1},\bigcup \{F(x,x_1,...,x_{\mathfrak{n}+1})|x\in x_0\})$.

如果没有任何 ${\mathrm{G}}_{\mathfrak{i}}$ 被引用, 我们就直接写 $\mathrm{Prim}$. 如果一个谓词的特征函数是 $\mathrm{Prim}(...)$ 函数, 则称这个谓词是 $\mathrm{Prim}(...)$ 谓词.

接下来的一系列定理是可以预计的.

定理 7.2.0.2. 我们列举以下性质.

1.	基本函数均原始递归.
2.	$KP$ 可证原始递归函数为 ${\Sigma }_1$ 函数符号.
3.	原始递归函数允许对原始递归谓词用分情形定义.
4.	原始递归函数允许带原始递归谓词的受限极小化.
5.	${\Delta }_0$ 可定义的关系必为原始递归谓词.
6.	原始递归函数允许带原始递归谓词的取像集操作.
7.	原始递归函数允许用属于关系进行递归定义.
8.	原始递归函数允许用序数指标进行迭代.

证明. 我们逐条证明.

1.	第一条只需逐一验证基本函数诸构造方案均为原始递归所覆盖. 1. $F(x_0,...,x_{\mathfrak{n}-1})=x_{\mathfrak{i}}$ 显然也是原始递归的初始函数. 2. $\{x_1,x_2\}=(\varnothing \cup \{x_1\})\cup \{x_2\}$. 3. 我们先验证受限极小化. 如果 $G(x,x_0,...,x_{\mathfrak{n}-1})$ 是原始递归的, 我们希望证明 $F(x_0,...,x_{\mathfrak{n}-1})={\bigcup }_{x\in x_0}g$ 同样原始递归; 我们先来造 $H(x,x_0^{\prime },x_0,...,x_{\mathfrak{n}-1},y)$, 它在 $x\in x_0^{\prime }$ 时值为 $G(x,x_0,...,x_{\mathfrak{n}-1})$, 否则值为 $y$; 这显然只需用最后一个初始函数在合适的地方复合一个 $G$ 就能得到它原始递归. 我们现在递归定义 $$\begin{gathered} D(x,x_0^{\prime },x_0,...,x_{\mathfrak{n}-1}) \\ =H(x,x_0^{\prime },x_0,...,x_{\mathfrak{n}-1},\bigcup \{D(x^{\prime },x_0^{\prime },x_0,...,x_{\mathfrak{n}-1})|x^{\prime }\in x\}) \end{gathered}$$, 这当然也是原始递归的. 最后只需发现 $$\begin{gathered} D(x_0,x_0,x_0,...,x_{\mathfrak{n}-1})=H(x_0, \\ {x}_0,x_0,...,x_{\mathfrak{n}-1},{\bigcup }_{x\in x_0}D(x,x_0,x_0,...,x_{\mathfrak{n}-1}))={\bigcup }_{x\in x_0}H(x,x_0,x_0, \\ ...,x_{\mathfrak{n}-1},\bigcup ...)={\bigcup }_{x\in x_0}G(x,x_0,...,x_{\mathfrak{n}-1})=F(x_0,...,x_{\mathfrak{n}-1}) \end{gathered}$$. 4. $x_1\backslash x_2={\bigcup }_{x\in x_1}F(\varnothing ,\{x\},x,x_2)$, 这 $F$ 是最后一个初始函数.
2.	第二条同样逐一验证原始递归函数诸构造方案均为 $KP$ 所证. 1. 初始函数中最后最奇怪的那个 $y=F(x_0,x_1,x_2,x_3)$ 有 ${\Delta }_0$ 定义 $(x_2\in x_3\wedge y=x_0)\vee (x_2\notin x_3\wedge y=x_1)$. 2. 复合时添加足量的存在以保证 ${\Sigma }_1$. 3. 递归无非是在 $\mathrm{TCl}$ 递归定义原理上稍作修改.
3.	这意味着如果 $R$ 是原始递归谓词, $G,H$ 是原始递归函数, 则 $F$ 同样原始递归: 它在 $R$ 真时取值 $G$, 否则取值 $H$; 只要注意 $R$ 原始递归意味着 $R$ 真当且仅当特征函数 ${\chi }_R$ 的值包括 $\varnothing$.
4.	这意味着如果如果 $G(x,x_0,...,x_{\mathfrak{n}-1})$ 是原始递归的, $R$ 是原始递归谓词, 我们希望证明 $F(x_0,...,x_{\mathfrak{n}-1})=\bigcup \{g|x\in x_0\wedge R\}$ 同样原始递归; 这不过是在一般的受限极小化上面再做判定 (用最后一个初始函数).
5.	否定同上视作一次分情形定义, 用或连接是把特征函数的两个计算结果并起来. 如果 $R$ 原始递归, $\exists x\in y(R)$ 的特征函数的值是 ${\bigcup }_{x\in y}{\chi }_R$.
6.	这意味着如果函数 $F(x,x_0,...,x_{\mathfrak{n}-1})$ 和关系 $R(x,x_0,...,x_{\mathfrak{n}-1})$ 原始递归, 则 $$\begin{gathered} F_R(‘‘y,x_0,...,x_{\mathfrak{n}-1})=\{z|\exists x\in y(z=F(x,x_0,...,x_{\mathfrak{n}-1}))\wedge R(x,x_0, \\ ...,x_{\mathfrak{n}-1})\} \end{gathered}$$ 同样原始递归; 其实这恰是 $\bigcup \{\{F\}|x\in y\wedge R\}$.
7.	我们定义里给的递归方案不太对劲, 因为传给 $G$ 的额外参数并不是 $F(\upharpoonright x_0,x_1,...,x_{\mathfrak{n}-1})$ 而是 $\bigcup F(‘‘x_0,x_1,...,x_{\mathfrak{n}-1})$, 我们这里要证明的是如果把前者传给 $G$ 递归而成的 $F$ 仍原始递归. 我们事实上还能给多一点, 把 $F(\upharpoonright \mathrm{TCl}(x_0),x_1,...,x_{\mathfrak{n}-1})$ 都送给 $G$; 要得到之前承诺的递归方案的话, 只需要稍在 $G$ 上动动手脚. 我们做 $H(x_0,...,x_{\mathfrak{n}-1})=y\cup \{(x,G(x,...,x_{\mathfrak{n}-1},y\upharpoonright x))|x\in x_0\}$, 其中 $y={\bigcup }_{x\in x_0}H(x,x_1,...,x_{\mathfrak{n}-1})$; 这个 $H$ 所用的递归方案正是定义中的那套, 所以自然是原始递归的, 我们来证 $H(x_0,...,x_{\mathfrak{n}-1})=F\upharpoonright \mathrm{TCl}(x_0)$. 对 $x_0$ 施行 $\in$ 归纳法, 鉴于这函数符号 ${\Sigma }_1$, 这整句话也是 ${\Sigma }_1$ 的, 所以确实可以归纳, 其余细节并无难处; $F$ 进而由复合见证原始递归.
8.	这是在说如果 $H,K,L$ 都原始递归, 那如下定义的 $F$ 也原始递归: 1. $F(\varnothing ,x_0,...,x_{\mathfrak{n}-1})=H(x_0,...,x_{\mathfrak{n}-1})$; 2. $F(\mathrm{Succ}(\alpha ),x_0,...,x_{\mathfrak{n}-1})=K(F(\alpha ,x_0,...,x_{\mathfrak{n}-1}),\alpha ,x_0,...,x_{\mathfrak{n}-1})$; 3. 对极限序数 $\alpha$, $F(\alpha ,x_0,...,x_{\mathfrak{n}-1})=L(F\upharpoonright \alpha ,\alpha ,x_0,...,x_{\mathfrak{n}-1})$. 我们定义 $D(y,z)=\bigcup \{(w{)}_{(2)}^{(1)}|w\in y\wedge (w{)}_{(2)}^{(0)}=\bigcup z\}$, 它显然原始递归, 而我们可以将第二条重新写成 $F(\mathrm{Succ}(\alpha ),x_0,...,x_{\mathfrak{n}-1})=K(D(F(\upharpoonright \mathrm{Succ}(\alpha ),x_0,...,x_{\mathfrak{n}-1}),\mathrm{Succ}(\alpha )),\bigcup \mathrm{Succ}(\alpha ),x_0,...,x_{\mathfrak{n}-1})$. 这启示我们这样分情形定义一个 $X(v,\alpha ,x_0,...,x_{\mathfrak{n}-1})$ 如下: 1. 当 $\alpha$ 不是序数的时候, 取值为 $\varnothing$; 2. 当 $\alpha =\varnothing$ 时, 取值为 $H(x_0,...,x_{\mathfrak{n}-1})$; 3. 当 $\bigcup \alpha \in \alpha$ 时, 取值为 $K(D(v,\alpha ),\bigcup \alpha ,x_0,...,x_{\mathfrak{n}-1})$; 4. 当 $\bigcup \alpha =\alpha$ 且 $\alpha \ne \varnothing$ 时, 取值为 $L(v,\alpha ,x_0,...,x_{\mathfrak{n}-1})$. 我们所要的 $F$ 无非是 $F(\alpha ,x_0,...,x_{\mathfrak{n}-1})=X(F\upharpoonright \alpha ,\alpha ,x_0,...,x_{\mathfrak{n}-1})$.

$\square$

有了这么多个性质, 我们实有信心把大部分常见的东西都指认为原始递归函数了. 我们现在来粗略展示 Rathjen 怎么证明 $KP$ 可证 ${\Sigma }_1$ 的函数符号恰是原始递归函数. 我们首先来把 $KP$ 增强一番:

定义 7.2.0.3. 我们给出 ${\Delta }_0$ 弱依赖选择公理模式, 记为 ${\Delta }_0-WDC$: 对公式 $\phi (x,y,v_0,...,v_{\mathfrak{n}-1})$, 令 ${\delta }^{\phi }(a,b,f,v_0,...,v_{\mathfrak{n}-1})$ 为 $$\begin{gathered} \mathrm{isOrd}(a)\to (\mathrm{isFun}(f) \\ \wedge \mathrm{dom}(f)=\mathrm{Succ}(a)\wedge f(\varnothing )=b\wedge \forall u\in a(\forall x\in f(u)\exists y\in f(\mathrm{Succ}(u))(\phi (x,y, \\ {v}_0,...,v_{\mathfrak{n}-1}))\wedge \forall y\in f(\mathrm{Succ}(u))\exists x\in f(u)(\phi (x,y,v_0,...,v_{\mathfrak{n}-1})))) \end{gathered}$$; 对 ${\Delta }_0$ 公式 $\phi$ 而言, $({\Delta }_0-WDC{)}_{\phi }$ 即 $\forall v_0...\forall v_{\mathfrak{n}-1}(\forall x\exists y(\phi )\to \forall a\forall b\exists f({\delta }^{\phi }))$.

元定理 7.2.0.4. $KP$ 加 ${\Delta }_0$ 弱依赖选择公理模式可证 ${\Sigma }_1$ 基础公理模式; 我们将记前一公理体系为 $K{P}^{\prime }$.

证明. 反设有一 ${\Pi }_1$ 公式 $\phi (x,...)$ 即 $\forall u(\theta (x,u,...))$(此处 $\theta$ 为一 ${\Delta }_0$ 公式) 在对 $x$ 归纳时失效, 这意味着 $\forall x(\forall y\in x(\phi (y,...))\to \phi (x,...))$ 但存在 $a$ 使得 $\neg \phi (a,...)$. 为了让 ${\Delta }_0-WDC$ 生效, 我们注意到条件说 $\forall x(\neg \phi (x,...)\to \exists y\in x(\neg \phi (y,...)))$, 这句话拆开就是 $\forall x\forall u\exists y\exists v(\neg \theta (x,u,...)\to (y\in x\wedge \neg \theta (y,v)))$; 一方面, 这告诉我们有 $b$ 使得 $\neg \theta (a,b,...)$; 另一方面, 用典范技术将 $(x,u)$ 编码为一个 $z$ 这句话就是 $\forall z\exists w(\neg \theta ((z{)}_{(2)}^{(0)},(z{)}_{(2)}^{(1)},...)\to \exists w((w{)}_{(2)}^{(0)}\in (z{)}_{(2)}^{(0)}\wedge \neg \theta ((w{)}_{(2)}^{(0)},(w{)}_{(2)}^{(1)},...)))$, 熟知的可替性告诉我们这一坨东西仍然 ${\Delta }_0$.

于是 ${\Delta }_0-WDC$ 说, 任给序数 $\alpha$ 都有长 $\mathrm{Succ}(\alpha )$ 的函数 $f$, $f(\varnothing )=\{(a,b)\}$, 且 $f(\mathrm{Succ}(\beta ))$ 里面装了有如上 ${\Delta }_0$ 句子后继于 $f(\beta )$ 里有序对的有序对. 鉴于 $KP$ 知道 ${\mathrm{rank}}_{\in }$ 全局, 我们不妨取这 $\alpha$ 为 ${\mathrm{rank}}_{\in }(a)$ 的后继序数得到这 $f$, 对不超过 $\alpha$ 的全体自然数 $n$ 归纳可证一新的 ${\Delta }_0$ 性质, 它宣称 $f(n)\ne \varnothing$, 且 $\forall z\in f(n)(\neg \theta ((z{)}_{(2)}^{(0)},(z{)}_{(2)}^{(1)},...))$, 且 $\forall z\in f(n)\exists w\in f(\mathrm{Succ}(n))((w{)}_{(2)}^{(0)}\in (z{)}_{(2)}^{(0)})$, 且 $\forall w\in f(\mathrm{Succ}(n))\exists z\in f(n)((w{)}_{(2)}^{(0)}\in (z{)}_{(2)}^{(0)})$.

鉴于 $\mathrm{isNat}$ 是 ${\Delta }_0$ 的, 我们可以分离出 $\{n\in \mathrm{Succ}(\alpha )|\mathrm{isNat}(n)\}$, 这东西不难证明或者是个自然数或者是 $\omega$, 我们记之为序数 $\xi$. 我们定义从 $\xi$ 出发的函数 $g$, $g(n)=\{(z{)}_{(2)}^{(0)}|z\in f(n)\}$, 则上述结论已经说明 $\forall n\in \xi (g(n)\ne \varnothing )$; 我们归纳证明 $\forall n\in \xi \forall u\in g(n)({\mathrm{rank}}_{\in }(u)+n\le {\mathrm{rank}}_{\in }(a))$; 注意 ${\mathrm{rank}}_{\in }$ 是 ${\Sigma }_1$ 的, 这整条性质是 $\Sigma$ 句子, 从而理应可以归纳. 归纳细节并无难处, 唯一值得注意的是在归纳后继步的时候需要注意 ${\mathrm{rank}}_{\in }$ 和 $+$ 都是 ${\Delta }^{KP}$ 的, 从而可以用 ${\Delta }^{KP}$ 分离公理模式.

现在只有两种可能: 如果 $\alpha =\mathrm{Succ}({\mathrm{rank}}_{\in }(a))$ 是自然数, 我们取一个 $u\in g(\alpha )$ 就有 ${\mathrm{rank}}_{\in }(u)+\alpha \le {\mathrm{rank}}_{\in }(a)<\alpha$ 矛盾; 所以 $\alpha$ 不是自然数, 这说明 $\xi =\omega$, 从而 ${\bigcup }_{n\in \omega }g(n)$ 不良基, 这又矛盾.

$\square$

评注. 不难看出, ${\Delta }_0-WDC$ 的主要作用是让我们取出所需的无穷降链.

我们要证明更强的结论: $K{P}^{\prime }$ 可证 ${\Sigma }_1$ 的函数符号也都是原始递归函数 (因而实际用 $KP$ 就能证出来). 这需要声明一些证明论引理, 其具体证明我们不在此处给出.

定义 7.2.0.5. 我们先来构造 $K{P}^{\prime }$ 的矢列演算 $\mathcal{C}\mathcal{A}\mathcal{L}$. 我们无视结构规则, 只用 $\neg ,\wedge ,\vee$ 三个连接词, 同时使用 $\forall ,\exists$ 两个量词; 下面列举 $\mathcal{C}\mathcal{A}\mathcal{L}$ 的语法:

1.	公理有如下诸条: 1. 逻辑公理: $\Gamma ,\phi ,\neg \phi$; 2. 等词公理模式: $\Gamma ,(a=b)\wedge (\phi (a\to \phi (b)))$, 额外限制 $\phi$ 只能是 ${\Delta }_0$ 公式; 3. 外延公理: $\Gamma ,\neg (\forall x\in a(x\in b)\wedge \forall x\in b(x\in a))\vee (a=b)$; 4. 对集公理: $\Gamma ,\exists z(z=\{a,b\})$; 5. 并集公理: $\Gamma ,\exists z(z=\bigcup a)$; 6. ${\Delta }_0$ 分离公理模式: $\Gamma ,\exists z(z=\{x\in a|\phi (x)\})$, 这里 $\phi$ 是 ${\Delta }_0$ 公式; 7. 集合基础公理: $\Gamma ,(\neg \exists x\in a(x\in a))\vee \exists y\in a\forall z\in y(\neg z\in a)$;
2.	逻辑推演规则有: 1. $\wedge$ 引入: $⊢\Gamma ,\phi$ 和 $⊢\Gamma ,\psi$ 推出 $⊢\Gamma ,\phi \wedge \psi$; 2. $\vee$ 引入 (两条): $⊢\Gamma ,\phi$ 或 $⊢\Gamma ,\psi$ 推出 $⊢\Gamma ,\phi \vee \psi$; 3. 受限 $\forall$ 引入: $⊢\Gamma ,\neg (a\in b)\vee \phi (a)$ 推出 $⊢\Gamma ,\forall x\in b(\phi (x))$; 4. $\forall$ 引入: $⊢\Gamma ,\phi (a)$ 推出 $⊢\Gamma ,\forall x(\phi (x))$; 5. 受限 $\exists$ 引入: $⊢\Gamma ,(a\in b)\wedge \phi (a)$ 推出 $⊢\Gamma ,\exists x\in b(\phi (x))$; 6. $\exists$ 引入: $⊢\Gamma ,\phi (a)$ 推出 $⊢\Gamma ,\exists x(\phi (x))$; 7. 切割: $⊢\Gamma ,\phi$ 和 $⊢\Gamma ,\neg \phi$ 推出 $⊢\Gamma$;
3.	非逻辑推演规则有: 1. ${\Delta }_0-Coll$: $⊢\Gamma ,\forall x\in a\exists y(\phi (x,y))$ 推出 $⊢\Gamma ,\exists z\forall x\in a\exists y\in z(\phi (x,y))$, 这里 $\phi$ 是 ${\Delta }_0$ 公式; 2. ${\Sigma }_1-Ind$: $⊢\Gamma ,\exists y\in a\forall z\neg (\phi (y,z)),\exists z(\phi (a,z))$ 推出 $\Gamma ,\exists z(\phi (b,z))$, 这里 $\phi$ 是 ${\Delta }_0$ 公式; 3. ${\Delta }_0-WDC$: $⊢\Gamma ,\exists y(\phi (a,y))$ 推出 $⊢\Gamma ,\exists f({\delta }^{\phi }(b,c,f))$, 这里 $\phi$ 是 ${\Delta }_0$ 公式.

下面考虑 $\mathcal{C}\mathcal{A}\mathcal{L}$ 中推演 $\mathbf{d}$, 我们照常定义其长度 $|\mathbf{d}|$、末推演、直接子推演和 $\mathbf{d}⊢\Gamma$ 等概念; 为了合理地定义 $\mathrm{rank}(\mathbf{d})$, 先定义公式的长度:

1.	${\Delta }_0$ 公式的长度统一视为 $0$; 以下假定不是 ${\Delta }_0$ 公式,
2.	带二元逻辑连接词: 加起来再加一; 带 $\neg$: 加一;
3.	带受限量词: 加二; 带量词: 加一.

现在, $\mathbf{d}$ 的秩定义为:

1.	如果末推演不是切割, 定义为全体直接子推演的秩的上确界;
2.	如果末推演是切割, 额外考察被切掉的公式的长度加一.

记存在长 $n$ 秩 $k$ 的对 $\Gamma$ 的推演 (这句话) 为 ${⊢}_k^n\Gamma$.

断言 ($\mathcal{C}\mathcal{A}\mathcal{L}$ 有效). $K{P}^{\prime }⊢\phi$ 当且仅当 $\mathcal{C}\mathcal{A}\mathcal{L}$ 中 $⊢\phi$.

断言 ($\mathcal{C}\mathcal{A}\mathcal{L}$ 的切消). 如果 ${⊢}_{k+2}^n\Gamma$, 则 ${⊢}_2^m\Gamma$, 这里 $m=2_k^n$, 这东西归纳地定义为 $2_0^n=n$, $2_{k+1}^n=2^{2_k^n}$.

但这些还不够, 我们还需要以下事实.

定义 7.2.0.6. 我们定义 ${\Delta }_0({\Sigma }_1)$ 公式是全体 ${\Sigma }_1$ 公式前面加受限量词和逻辑连接词构成的公式; 不难意识到它是一类特别的 $\Sigma$ 公式.

对函数 $F:\mathbf{V}\times \mathbf{Ord}\to \mathbf{Ord}$, 如果 $\forall t\forall \alpha \in \beta (F(t,\alpha )\in F(t,\beta ))$, 则称 $F$ 严格单增.

对公式 $\phi$, 我们记 ${\phi }_t^{\alpha ,\beta }$ 为将 $\phi$ 中全体 $\forall x$ 改为 $\forall x\in L_{\alpha }(t)$、$\exists x$ 改为 $\exists x\in L_{\beta }(t)$ 所得的公式; 注意 $L_{\alpha }(t)$ 是原始递归函数.

断言 ($\mathcal{C}\mathcal{A}\mathcal{L}$ 的解释定理). 如果 $\phi (a_1,...,a_{\mathfrak{k}})$ 是 ${\Delta }_0({\Sigma }_1)$ 公式, 秩不大于 $2$ 的推演 $\mathbf{d}⊢\phi$, 则存在严格单增的原始递归函数 $F$, 使得任给序数 $\alpha$, 当 $a_1,...,a_{\mathfrak{k}}\in L_{\alpha }(t)$ 时均有 $\phi (a_1,...,a_{\mathfrak{k}}{)}_t^{\alpha ,F(t,\alpha )}$.

我们用这些声明的引理来证明:

元定理 7.2.0.7. 若 $K{P}^{\prime }$ 可证 $H(x_1,...,x_{\mathfrak{k}})$ 是 ${\Sigma }_1$ 公式 $\exists z(\phi (z,y,x_1,...,x_{\mathfrak{k}}))$ 定义的函数符号 ($\phi$ 是 ${\Delta }_0$ 公式), 则 $H$ 原始递归.

证明. 放入 $\mathcal{C}\mathcal{A}\mathcal{L}$ 后用切消可知 ${⊢}_2^m\exists w\exists y\in w\exists z\in w(\phi (z,y,x_1,...,x_{\mathfrak{k}}))$; 解释定理给我们一个原始递归函数 $F(t,\alpha )$, 我们用它做新的原始递归函数 $K(x_1,...,x_{\mathfrak{k}})=L_{F(x,0)}(x)$, 这里 $x=\{x_1,...,x_{\mathfrak{k}}\}$, 则 $\exists w\in K\exists y\in w\exists z\in w(\phi )$, 从而 $H=\bigcup \{y\in K|\exists z\in K(\phi )\}$ 原始递归.

$\square$

对于 $\mathrm{Prim}({\mathrm{G}}_{\mathfrak{i}})$ 与扩展语言中的 $KP({\mathrm{G}}_{\mathfrak{i}})$, 我们有类似的定理, 但这里就不再展示了.