第一章证明（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$-算子封闭。