4.1. 第一基本递归

我们首先来考虑对基本函数做递归会发生什么. 我们先考虑最简单的递归方程, 其中没有多余的参数出现.

定义 4.1.0.1 (第一基本递归). 给定一元基本函数符号 $G$ , 我们称满足以下性质的一元函数符号 $F$ 为由 $G$ 经第一基本递归所得的函数符号, 存在 $G$ 的这种 $F$ 将称作第一基本递归函数符号, 简称基本递归函数符号: $y = F (x) \leftrightarrow \exists f (y = G (f) \land isFun (f) \land dom (f) = x \land \forall a \in x \exists b (b = f (a) \land b = F (a)))$

严格地说, 这里其实应当指明何理论可证 $F$ 由 $G$ 第一基本递归而成; 我们需要 $G J_{0}$ 来确保每个基本函数符号 $G$ 都可证为函数符号, 但什么公理能保证对每个 $G$ 都存在 $F$ 呢?

元定理 4.1.0.2. $Π_{1} - G J + (TC o)$ 可证第一基本递归总是可行.

证明. 我们希望

y = F (x)

有

Σ_{1}

的定义

\exists d, h, k (x \in d \land isFun (h) \land isFun (k) \land dom (h) = d \land isTrans (d) \land \forall (z, w) \in h (w = G (k (z))) \land \forall z \in d (k (z) = h ↾ z) \land h (x) = y)

和

Π_{1}

的定义

\forall d, h, k (... \to h (x) = y)

且它们可证等价. 不难意识到唯一需要注意的是存在

d

给出了

x

的传递包括.

$□$

因此, 此小节中我们总是默认所用的理论是某个 $Π_{1} - G J + (TC o)$ 的扩展. 我们现在简要研究基本递归性.

元定理 4.1.0.3. 一元基本函数符号都是基本递归的.

证明. 对一元基本函数符号

F

, 取同样基本的

G (f) = F (dom (f))

, 验证

F (x) = G (F ↾ x)

是显然的.

$□$

鉴于拥有对集公理, 我们其实可以说:

元定理 4.1.0.4. 将基本函数符号 $G (x_{0}, ..., x_{n})$ 通过 $n$ 元元组编码为 $G^{'} (x)$ , 在 $x = (x_{0}, ..., x_{n})$ 时 $G^{'} (x) = G (x_{0}, ..., x_{n})$ , 否则 $G^{'} (x) = \emptyset$ . 鉴于基本函数可以 $Δ_{0}$ 分段定义, $G^{'}$ 同样基本, 但它一元, 因此它基本递归.

评注. 然而, $G^{'}$ 毕竟不是 $G$ . 在拥有二元函数符号 ${-, -}$ 后, 我们确实可以用 $G^{'}$ 计算原本的 $G$ , 但把对集函数符号自己压缩成一元函数符号之后就算不回来了.

基本递归函数的限制同样是基本递归的.

元定理 4.1.0.5. 如果 $F$ 是基本递归的, 那么 $F ↾$ 也是基本递归的.

证明. 假定

F (x) = G (F ↾ x)

, 令

G_{1} (x) = (x_{(2)}^{(0)}, G (x_{(2)}^{(1)}))

, 再令

G_{2} (x) = G_{1}^{''} (x)

, 熟知它们都是基本的; 记

H (x) = F ↾ x

, 则有

H (x) = G_{2} (H ↾ x)

.

$□$

对多重基本递归这类操作, 我们仅指出最特殊的二重基本递归.

元定理 4.1.0.6. 给定两个二元基本函数符号 $G_{1}, G_{2}$ , 如果一元函数符号 $F_{1}, F_{2}$ 满足 $F_{1} (x) = G_{1} (F_{1} ↾ x, F_{2} ↾ x)$ 且 $F_{2} (x) = G_{2} (F_{1} ↾ x, F_{2} ↾ x)$ , 则函数 $F (x) = (F_{1} (x), F_{2} (x))$ 是基本递归的.

证明. 注意此时

F (x) = (G_{1} (F_{1} ↾ x, F_{2} ↾ x), G_{2} (F_{1} ↾ x, F_{2} ↾ x))

且

F ↾ x = {(a, (F_{1} (a), F_{2} (a))) ∣ a \in x}

, 我们可用适当的

Δ_{0}

分离子 (换言之基础, 进而基本的)

G_{3}, G_{4}

来指出

G_{3} (F ↾ x) = F_{1} ↾ x

和

G_{4} (F ↾ x) = F_{2} ↾ x

, 进而取

G_{5} (x) = (G_{1} (G_{3} (x), G_{4} (x)), G_{2} (G_{3} (x), G_{4} (x)))

, 有

F (x) = G_{5} (F ↾ x)

.

$□$

我们甚至能容忍递归操作中的简单分类定义.

元定理 4.1.0.7. 如果 $G (x)$ 是一元基本函数符号, $φ (x)$ 是一个 $Δ_{0}$ 公式, 则满足如下要求的 $F$ 是基本递归的函数符号: $F (x)$ 在 $φ (x)$ 时等于 $G (F ↾ x)$ , 在 $\neg φ (x)$ 时等于 $\emptyset$ .

证明. 此时

F

由

G^{'} (f) = {z \in G (f) ∣ φ (dom (f))}

基本递归而成.

$□$

比较讨厌的是, 基本递归函数与基本递归函数的复合可以不是基本递归的, 且基本递归函数的像函数可以不是基本递归的 (这使得它的性质不如基本函数). 我们引入一个更宽松但恰当的要求以满足这两件事.

定义 4.1.0.8 (和缓性). 如果 $G (x)$ 是基本递归函数符号, $H (x)$ 是基本函数符号, 则称其复合 $F (x) = H (G (x))$ 是和缓 (gentle) 的函数符号.

元定理 4.1.0.9. 和缓函数的复合仍是和缓的.

证明. 我们先来考虑基本递归函数的复合.

断言. 基本递归函数的复合是和缓的.

证明. 假定 $F_{1}$ 由 $G_{1}$ 第一基本递归而成, $F_{2}$ 由 $G_{2}$ 第一基本递归而成, 我们来证明 $F_{1} \circ F_{2}$ 和缓.

如果传递集 $u$ 包括有序对 $(x, F_{2} (x))$ , 则称集合 $f = F_{1} ↾ u$ 对 $x$ 是足够的; 此时显然有 $f (F_{2} (x)) = F_{1} (F_{2} (x))$ . 我们希望找一个 $F$ , 使得 $F (x)$ 总是一个对 $x$ 足够的集合, 且有二元基本函数 $E$ 使得 $F (x) = E (F ↾ x, F_{2} ↾ x)$ , 这样 $x \mapsto (F (x), F_{2} (x))$ 就是基本递归的, 而再对 $q = (F (x), F_{2} (x))$ 取基本函数 $q \mapsto q_{(2)}^{(0)} (q_{(2)}^{(1)})$ 即得到 $x \mapsto F (x) (F_{2} (x)) = F_{1} (F_{2} (x))$ 和缓.

为了达到这一目的, 我们首先来指出两个重要构造. 假定 $b \subseteq ℘ (a)$ , 我们注意到 $F_{1} ↾ b = {(x, G_{1} ((F_{1} ↾ a) ↾ x)) ∣ x \in b}$ . 取基本函数 $ϕ (x, f) = (x, G_{1} (f ↾ x))$ , 则 $F_{1} ↾ b = ϕ^{''} (b \times {F_{1} ↾ a})$ ; 进而我们令基本函数 $H_{1} (b, f) = ϕ^{''} (b \times {f})$ , 则 $F_{1} ↾ b = H_{1} (b, F_{1} ↾ a)$ .

接下来, 我们取一个传递集 $u$ , 我们希望构造一个一元基本函数 $H_{1}^{T}$ , 使得 $F_{1} ↾ T (u) = H_{1}^{T} (F_{1} ↾ u)$ ; 不难验证令 $H_{1}^{T} (f) = H_{1} (T (dom (f)), f)$ 即可满足此条件. 对这个递归方程使用简单的 (元) 归纳法立即指出 $(H_{1}^{T})^{(l)} (F_{1} ↾ u) = F_{1} ↾ ((T)^{l} u)$ .

现在, 我们假定 $dom (f) = x$ 满足每个 $y \in x$ 对应的 $f (y)$ 都对 $y$ 足够 (换言之, $f$ 是目标 $F$ 在 $x$ 上的限制), 来想办法造 $F (x)$ . 对 $y \in x$ , 记 $u (y) = dom (f (y))$ 传递, 则 $\overset{u}{ˉ} = ⋃_{y \in x} u (y)$ 同样传递, 且 $F_{1} ↾ \overset{u}{ˉ} = ⋃ ran (f)$ . 另一方面, $f (y)$ 对 $y$ 足够, 因此 $(y, F_{2} (y)) \in u (y) \subseteq \overset{u}{ˉ}$ , 进而 $F_{2} ↾ x \subseteq \overset{u}{ˉ}$ , 换言之 $t = \overset{u}{ˉ} \cup {F_{2} ↾ x}$ 是传递的. 因此, $F_{1} ↾ t = H_{1} (t, F_{1} ↾ \overset{u}{ˉ})$ 是 $F_{1}$ 到一个包括 $F_{2} ↾ x$ 的传递集上的限制.

但 $F (x)$ 应当是 $F_{1}$ 到一个包括 $(x, F_{2} (x))$ 的传递集上的限制, 而我们知道 $x = dom (F_{2} ↾ x)$ 和 $F_{2} (x) = G_{2} (F_{2} ↾ x)$ . 我们考虑基本函数 $K : g \mapsto (dom (g), G_{2} (g))$ , 则之前对 $T$ 的分析指出存在一个 $l$ 使得任给传递集 $r$ 和 $x \in r$ , 总有 $K (x) \in T^{(l)} (r)$ . 特别地取这个传递集为之前的 $t$ , 则 $K (F_{2} ↾ x) = (x, F_{2} (x)) \in T^{(l)} (t)$ , 而我们也知道 $F_{1} ↾ ((T)^{l} t) = (H_{1}^{T})^{(l)} (F_{1} ↾ t)$ 可以算出来, 因此构造完成了.

总览以上过程, 我们知道应当令

E (f, g) = (H_{1}^{T})^{(l)} H_{1} ({g} \cup ⋃ ran (f), ⋃ ran (f))

以完成证明.

$□$

接下来的证明比较简单. 如果

F_{1} = G_{1} \circ H_{1}

和

F_{2} = G_{2} \circ H_{2}

如分解和缓, 则

F_{1} \circ F_{2} = G_{1} \circ H_{1} \circ G_{2} \circ H_{2}

.

G_{2}

基本, 因此基本递归, 因此

H_{1} \circ G_{2}

和缓, 假定

H_{1} \circ G_{2} = G_{2}^{'} \circ H_{1}^{'}

, 则

F_{1} \circ F_{2} = G_{1} \circ G_{2}^{'} \circ H_{1}^{'} \circ H_{2}

.

H_{1}^{'}

和

H_{2}

均基本递归, 因此

H_{1}^{'} \circ H_{2}

和缓, 假定

H_{1}^{'} \circ H_{2} = G_{3} \circ H

, 则

F_{1} \circ F_{2} = (G_{1} \circ G_{2}^{'} \circ G_{3}) \circ H

和缓.

$□$

元定理 4.1.0.10. 和缓函数的像仍是和缓的.

证明. 注意

F^{''} (x) = ran (F ↾ x)

, 只需证明和缓函数的限制仍是和缓的. 假定

F = G \circ H

如分解和缓, 由于已知基本递归函数的限制仍然基本递归, 自然想法是找一个基本的

G^{'}

使得

F ↾ x = G^{'} (H ↾ x)

, 而这只需要取

G^{'} (f) = {(x, G (f (x))) ∣ x \in dom (f)}

.

$□$

在作为谓词的性质上, 和缓性甚至比基本性还恰到好处. 我们已知以下事实.

元定理 4.1.0.11. $φ$ 是 $Δ_{0}$ 的, 当且仅当其分离子 $t_{φ}$ 是基础的, 当且仅当其特征函数 $χ_{φ}$ 是基本的.

但和缓性不会加强其分离子的性质.

元定理 4.1.0.12. $φ$ 的分离子 $t_{φ}$ 和缓, 当且仅当其特征函数 $χ_{φ}$ 和缓.

证明. 如果

χ_{φ}

和缓, 则

t_{φ} (x) = dom ((χ_{φ} ↾ x) \cap (x \times {{\emptyset}}))

是和缓函数的限制与基本函数的复合, 显然和缓; 如果

t_{φ}

和缓, 则

χ_{φ} (x) = F \circ t_{φ} ({x})

, 这里基本函数

F

分段定义为

\emptyset \mapsto \emptyset

, 不为空集的

x \mapsto {\emptyset}

.

$□$

定义 4.1.0.13. 我们称满足上一定理条件的 $φ$ 为和缓类.

正如 $Δ_{0}$ 类的分类定义不改变基本性, 和缓类的分类定义同样也不改变和缓性.

元定理 4.1.0.14. 如果 $φ$ 是和缓类, $F$ 是和缓函数, 则 $F_{φ}$ 同样是和缓函数, 这里 $F_{φ} (x)$ 在 $φ (x)$ 时取值为 $F (x)$ , 在 $\neg φ (x)$ 时取值为 $\emptyset$ .

我们同样可以把分类定义放到递归操作中去.

元定理 4.1.0.15. 如果 $G (x)$ 是和缓函数符号, $φ (x)$ 是一个和缓类, 则满足如下要求的 $F$ 是和缓的函数符号: $F (x)$ 在 $φ (x)$ 时等于 $G (F ↾ x)$ , 在 $\neg φ (x)$ 时等于 $\emptyset$ .

这两个定理的证明将作为本节最后一个定理的推论给出.

最后, 我们同样在扩展语言 $L_{A}$ 中考虑和缓性.

定义 4.1.0.16. 给定一元 $A$ 中基本函数符号 $G$ , 我们称满足以下性质的一元函数符号 $F$ 为由 $G$ 经 $A$ 中第一基本递归所得的函数符号, 存在 $G$ 的这种 $F$ 将称作 $A$ 中的第一基本递归函数符号, 简称 $A$ 中的基本递归函数符号: $y = F (x) \leftrightarrow \exists f (y = G (f) \land isFun (f) \land dom (f) = x \land \forall a \in x \exists b (b = f (a) \land b = F (a)))$

元定理 4.1.0.17. $G J_{0}^{A} + (TC o) + (F n d)_{Π_{1}}$ 可证 $A$ 中的第一基本递归可行.

证明. 略.

$□$

定义 4.1.0.18. 如果 $G (x)$ 是 $A$ 中的基本递归函数符号, $H (x)$ 是 $A$ 中基本函数符号, 则称其复合 $F (x) = H (G (x))$ 是 $A$ 中和缓 (gentle) 的函数符号.

元定理 4.1.0.19. $A$ 中和缓函数的复合仍是 $A$ 中和缓的, $A$ 中和缓函数的像仍是 $A$ 中和缓的.

证明. 略.

$□$

我们希望指出的事实是, 正如 $Δ_{0}$ 的 $A$ 不新增基本函数, 和缓的 $A$ 也不新增和缓函数. 在此之前, 我们先指出此时一个重要的引理.

元定理 4.1.0.20. 如果 $A$ 的分离子 $O_{A} = H \circ F$ 如分解和缓, 则对任意 $A$ 中基本的函数符号 $G$ , 存在二元基本函数符号 $\hat{G}$ , 使得任给传递集 $u ∋ x$ 均有 $G (x) = \hat{G} (x, F ↾ u)$ .

证明. 这个定理意味着我们可以临时传入一个

y = F ↾ u

来计算

O_{A}

. 显然我们只需要用

H \circ f

替换

H \circ F = O_{A}

, 此处

f = (G^{T^{A}})^{(l)} (y)

, 而

G^{T^{A}} (f) = H_{G} (T (dom (f)) \cup ran (H \circ f), f)

, 其中

ϕ (x, f) = (x, G (f ↾ x))

,

H_{G} (b, f) = ϕ^{''} (b \times {f})

.

$□$

元定理 4.1.0.21. 如果 $A$ 是和缓类, 则在 $A$ 中和缓的函数就是和缓的函数.

证明. 假定 $O_{A} = H_{1} \circ F_{1}$ 如分解和缓, $F_{1}$ 由 $G_{1}$ 基本递归而成. 我们只需证明在 $A$ 中基本递归的函数符号 $F_{2}$ 一定是和缓的, 即可由和缓函数与和缓函数的复合仍和缓立得完整结论. 假定 $F_{2}$ 由 $G_{2}$ 基本递归而成, $G_{2}$ 是 $A$ 中基本的.

使用相同证明手法, 我们在传递集 $u$ 包括有序对 $(x, F_{2} (x))$ 时称集合 $f = F_{1} ↾ u$ 对 $x$ 是足够的. 我们同样宣称存在基本函数 $F$ , 使得 $F (x)$ 总是一个对 $x$ 足够的集合, 且有二元基本函数 $E$ 使得 $F (x) = E (F ↾ x, F_{2} ↾ x)$ .

取基本函数 $ϕ (x, f) = (x, G_{1} (f ↾ x))$ , $H (b, f) = ϕ^{''} (b \times {f})$ 和 $H^{T^{A}} (f) = H (T (dom (f)) \cup ran (H_{1} \circ f), f)$ , 同样考虑基本函数 $K : g \mapsto (dom (g), G_{2} (g))$ , 则之前对 $T^{A}$ 的分析也指出存在一个 $l$ 使得任给传递集 $r$ 和 $x \in r$ , 总有 $K (x) \in (T^{A})^{(l)} (r)$ . 令 $E (f, g) = (H^{T^{A}})^{(l)} H ({g} \cup ⋃ ran (f), ⋃ ran (f))$ 即取得所要的 $H$ 和对应的 $F$ .

我们注意, 任给

f = F ↾ x

都有

F (x) = E (f, F_{2} ↾ x)

对

x

足够, 且

F_{2} ↾ x \in dom (F (x))

, 因此由引理有

F_{2} (x) = \hat{G}_{2} (F_{2} ↾ x, E (f, F_{2} ↾ x))

, 这指出

F

与

F_{2}

事实上是在基本函数的意义下共同递归, 因此

F_{2}

是和缓的.

$□$

名字空间

视图

4.1. 第一基本递归