第一章证明（1.1-1.2）¶

在教材第一章中，有些定理留作习题，没有给出证明。我们将这些定理进行汇总，并给出证明。

引理1.3¶

引理1.3

关于 $G\ddot{o}del$ 编码有下述性质：

$\text{ep}_i(\langle x_0,\cdots,x_n\rangle)=\begin{cases}x_i,&若0\leq i\leq n, \\ 0, &否则;\end{cases}$
$\langle x_0, \cdots, x_n\rangle = \langle y_0,\cdots, y_n\rangle$ 当且仅当 $\forall i\leq n. x_i=y_i$ ；
$\langle x_0, \cdots, x_n,0,\cdots,0\rangle = \langle x_0, \cdots, x_n\rangle$ ;
若 $\langle x_0, \cdots, x_m\rangle=\langle y_0, \cdots, y_n\rangle$ 且 $x_m\cdot y_n\not=0$ ，则 $m=n$ 且 $\forall i\leq n.x_i=y_i$ .

证：

(1)

根据 $G\ddot{o}del$ 编码定义，

$$ \langle x_0,\cdots,x_n\rangle=\prod^n_{i=0}[P^{x_i}_i] $$ 其中 $P_i$ 表示第i个素数。故 $x_i=\text{ep}_i(\langle x_0,\cdots,x_n\rangle)$ .

(2)

由 $\langle x_0, \cdots, x_n\rangle = \langle y_0,\cdots, y_n\rangle$ ，故

$\prod^n_{i=0}[P^{x_i}_i]=\prod^n_{i=0}[P^{y_i}_i]$

故 $\forall i\leq n. x_i=y_i$ .

(3)

$\begin{align} \langle x_0, \cdots, x_n,0,\cdots,0\rangle =&(\prod^n_{i=0}[P^{x_i}_i])*(\prod^m_{i=n+1}[P^0_i]) \\\\ =&(\prod^n_{i=0}[P^{x_i}_i])*(\prod^m_{i=n+1}1) \\\\ =&\prod^n_{i=0}[P^{x_i}_i] \\\\ =&\langle x_0, \cdots, x_n\rangle \end{align}$

(4)

反设结论不成立，故 $m\not=n$ 或 $\exists i\leq n,x_i\not=y_i$ 。

若 $m\not=n$ ，由 $x_m\cdot y_n\not=0$ ，必有 $\langle x_0, \cdots, x_m\rangle\not=\langle y_0, \cdots, y_n\rangle$ .

若 $\exists i\leq n,x_i\not=y_i$ ，必有 $\langle x_0, \cdots, x_m\rangle\not=\langle y_0, \cdots, y_n\rangle$ .

矛盾。

引理1.4¶

引理1.4

令： $$ \begin{align} \text{pg}(x,y) &=\langle x,y\rangle = 2^x\times 3^y, \\ K(z) & = \text{ep}_0(z),\\ L(z) & = \text{ep}_1(z), \end{align} $$ 其中 $\langle x,y\rangle$ 为定义1.11中的 $G\ddot{o}del$ 编码，则 $\{\text{pg},K,L\}$ 为配对函数组。

证：

对任意 $x,y\in\mathbb{N}$ ，有

$K(\text{pg}(x,y))=\text{ep}_0(2^x\times 3^y)=x \\\\ L(\text{pg}(x,y))=\text{ep}_1(2^x\times 3^y)=y$

故结论成立。

引理1.5¶

引理1.5

令： $$ \begin{align} \text{pg}(x,y) &= 2^x(2y+1), \\ K(z) & = \text{ep}_0(z),\\ L(z) & = \left\lfloor \frac{z}{2^{\text{ep}_0(z)+1}}\right\rfloor , \end{align} $$ 则 $\{\text{pg},K,L\}$ 为配对函数组。

证：

对任意 $x,y\in\mathbb{N}$ ，有

$K(\text{pg}(x,y))=\text{ep}_0(2^x(2y+1))=x$

$\begin{align} L(\text{pg}(x,y)) &=\left\lfloor \frac{2^x(2y+1)}{2^{\text{ep}_0(2^x(2y+1))+1}}\right\rfloor \\\\ &=\left\lfloor \frac{2^x(2y+1)}{2^{x+1}}\right\rfloor \\\\ &=\left\lfloor y+\frac{1}{2}\right\rfloor \\\\ &=y \end{align}$

故结论成立。

引理1.8¶

引理1.8

设 $n\in\mathbb{N}$ ，令： $$ \begin{align} J_n(x_0,\cdots,x_n)&=\langle x_0,\cdots, x_n\rangle, \\ \pi_i(z) & = \text{ep}_i(z), 0\leq i\leq n, \end{align} $$ 其中 $\langle x_0,\cdots,x_n\rangle$ 为定义1.11中的 $G\ddot{o}del$ 编码，则 $\{J_n,\pi_0,\cdots,\pi_n\}$ 为多元配对函数组。

证：

对任意 $i\leq n$ 和 $x_0,\cdots,x_n\in\mathbb{N}$ ，有

$\pi_i(\langle x_0,\cdots, x_n\rangle)=\text{ep}_i(\prod^{n}_{i=0}[P_i^{x_i}])=x_i$

故结论成立。

引理1.9¶

引理1.9

设 $\{\text{pg},K,L\}$ 为任意配对函数组。对于任意 $n\in\mathbb{N}$ ，令： $$ \begin{align} J_n(x_0,\cdots,x_n)&=\text{pg}(\cdots \text{pg}(\text{pg}(x_0,x_1),x_2)\cdots,x_n), \\ \pi_0(z) & = K^n(z), \\ \pi_i(z) & = L(K^{n-i}(z)), 1\leq i\leq n, \end{align} $$ 则 $\{J_n,\pi_0,\cdots,\pi_n\}$ 为多元配对函数组。

证：

当 $i=0$ 时，

$\begin{align} \pi_0(J_n(x_0,\cdots,x_n))&=K^n(\text{pg}(\cdots \text{pg}(\text{pg}(x_0,x_1),x_2)\cdots,x_n)) \\\\ &=K^{n-1}(\text{pg}(\cdots \text{pg}(\text{pg}(x_0,x_1),x_2)\cdots,x_{n-1})) \\\\ &\cdots \\\\ &=K(\text{pg}(x_0,x_1)) \\\\ &=x_0 \end{align}$

当 $i\geq 1$ 时，

$\begin{align} \pi_i(J_n(x_0,\cdots,x_n))&=L(K^{n-i}(\text{pg}(\cdots \text{pg}(\text{pg}(x_0,x_1),x_2)\cdots,x_n))) \\\\ &=L(K^{n-i-1}(\text{pg}(\cdots \text{pg}(\text{pg}(x_0,x_1),x_2)\cdots,x_{n-1}))) \\\\ &\cdots \\\\ &=L(\text{pg}(\cdots \text{pg}(\text{pg}(x_0,x_1),x_2)\cdots,x_i)) \\\\ &=x_i \end{align}$

故结论成立。

引理1.15¶

引理1.15

$\mathcal{EF}$ 对有界 $\max$ -算子是封闭。

证：

由于 $\mathcal{EF}$ 对于有界 $\mu$ -算子封闭，而 $\max x\leq n. [f(x,\overrightarrow{y})]=n\dot- \min x \leq n. [f(n\dot-x,\overrightarrow{y})]$ 。故 $\mathcal{EF}$ 对有界 $\max$ -算子封闭。