第一章证明（1.3）

引理1.16

引理1.16

下述二元数论谓词是初等数论谓词：

1. $\text{eq}(x,y)\equiv x=y$;
2. $\text{neq}(x,y)\equiv x\not=y$;
3. $\text{lt}(x,y)\equiv x<y$;
4. $\text{leq}(x,y)\equiv x\leq y$;
5. $\text{gt}(x,y)\equiv x>y$;
6. $\text{geq}(x,y)\equiv x\geq y$;

证：

(1)

特征函数为 $f(x,y)=\begin{cases}0,x=y\,,\\ 1, x\not=y\,.\end{cases}$

故 $f(x,y)=N^2(x\ddot-y)$

(2)

特征函数为 $f(x,y)=\begin{cases}0,x\not=y\,,\\ 1, x=y\,.\end{cases}$

故 $f(x,y)=N(x\ddot-y)$

(3)

特征函数为 $f(x,y)=\begin{cases}0,x<y\,,\\ 1, x\geq y\,.\end{cases}$

故 $f(x,y)=N(y\dot-x)$

(4)

特征函数为 $f(x,y)=\begin{cases}0,x\leq y\,,\\ 1, x> y\,.\end{cases}$

故 $f(x,y)=N^2(x\dot-y)$

(5)

特征函数为 $f(x,y)=\begin{cases}0,x> y\,,\\ 1, x\leq y\,.\end{cases}$

故 $f(x,y)=N(x\dot-y)$

(6)

特征函数为 $f(x,y)=\begin{cases}0,x\geq y\,,\\ 1, x< y\,.\end{cases}$

故 $f(x,y)=N^2(y\dot-x)$

引理1.17

引理1.17

若 $n$ 元数论函数 $f,g:\mathbb{N}^n\rightarrow \mathbb{N}$ 是初等数论函数，则下述 $n$ 元数论谓词是初等数论谓词：

1. $\text{eq}_{f,g}(\overrightarrow{x})\equiv f(\overrightarrow{x})=g(\overrightarrow{x})$;
2. $\text{neq}_{f,g}(\overrightarrow{x})\equiv f(\overrightarrow{x})\not=g(\overrightarrow{x})$;
3. $\text{lt}_{f,g}(\overrightarrow{x})\equiv f(\overrightarrow{x})<g(\overrightarrow{x})$;
4. $\text{leq}_{f,g}(\overrightarrow{x})\equiv f(\overrightarrow{x})\leq g(\overrightarrow{x})$;
5. $\text{gt}_{f,g}(\overrightarrow{x})\equiv f(\overrightarrow{x})>g(\overrightarrow{x})$;
6. $\text{geq}_{f,g}(\overrightarrow{x})\equiv f(\overrightarrow{x})\geq g(\overrightarrow{x})$;

证：

(1)

特征函数为 $F(\overrightarrow{x})=\begin{cases}0,f(\overrightarrow{x})=g(\overrightarrow{x})\,,\\ 1, f(\overrightarrow{x})\not=g(\overrightarrow{x})\,.\end{cases}$

故 $F(\overrightarrow{x})=N^2(f(\overrightarrow{x})\ddot-g(\overrightarrow{x}))$

(2)

特征函数为 $F(\overrightarrow{x})=\begin{cases}0,f(\overrightarrow{x})\not=g(\overrightarrow{x})\,,\\ 1, f(\overrightarrow{x})=g(\overrightarrow{x})\,.\end{cases}$

故 $F(\overrightarrow{x})=N(f(\overrightarrow{x})\ddot-g(\overrightarrow{x}))$

(3)

特征函数为 $F(\overrightarrow{x})=\begin{cases}0,f(\overrightarrow{x})<g(\overrightarrow{x})\,,\\ 1, f(\overrightarrow{x})\geq g(\overrightarrow{x})\,.\end{cases}$

故 $F(\overrightarrow{x})=N(g(\overrightarrow{x})\dot-f(\overrightarrow{x}))$

(4)

特征函数为 $F(\overrightarrow{x})=\begin{cases}0,f(\overrightarrow{x})\leq g(\overrightarrow{x})\,,\\ 1, f(\overrightarrow{x})> g(\overrightarrow{x})\,.\end{cases}$

故 $F(\overrightarrow{x})=N^2(f(\overrightarrow{x})\dot-g(\overrightarrow{x}))$

(5)

特征函数为 $F(\overrightarrow{x})=\begin{cases}0,f(\overrightarrow{x})> g(\overrightarrow{x})\,,\\ 1, f(\overrightarrow{x})\leq g(\overrightarrow{x})\,.\end{cases}$

故 $F(\overrightarrow{x})=N(f(\overrightarrow{x})\dot-g(\overrightarrow{x}))$

(6)

特征函数为 $F(\overrightarrow{x})=\begin{cases}0,f(\overrightarrow{x})\geq g(\overrightarrow{x})\,,\\ 1, f(\overrightarrow{x})< g(\overrightarrow{x})\,.\end{cases}$

故 $F(\overrightarrow{x})=N^2(g(\overrightarrow{x})\dot-f(\overrightarrow{x}))$

引理1.18

引理1.18

初等数论谓词对于 $\neg，\wedge,\vee,\rightarrow,\forall x\leq n.[\cdot],\exists y\leq n.[\cdot]$封闭。

证：

$\neg x$：$N(x)$

$x\wedge y$：$N^2(x+y)$

$x\vee y$：$x\cdot y$

$x\rightarrow y$：$\neg x \vee y=N(x)\cdot y$

$\forall x\leq n.[\cdot]$：$N(\prod_{i=0}^nN[\cdot])$

$\exists y\leq n.[\cdot]$：$\prod_{i=0}^n[\cdot]$

引理1.22

引理1.22

初等数论集合对于 $\cup,\cap,-$封闭。

证：

设初等数论集合 $S_1,S_2\subseteq\mathbb{N}^n$，其特征函数分别为 $\chi_{S_1},\chi_{S_2}$。

故

$$\chi_{S_1\cup S_2}=\chi_{S_1}\cdot \chi_{S_2} \\ \chi_{S_1\cap S_2}=N^2(\chi_{S_1}+ \chi_{S_2}) \\ \chi_{S_1- S_2}=N^2(\chi_{S_1}+ (1\ddot-\chi_{S_2}))$$

引理1.33

引理1.33

定义1.22中的函数 $G 具有以下性质：

1. $G(k,x)$对 $k$ 和 $x$ 皆严格递增；
2. $(x+1)G(k,x)<G(k+2,x)$;
3. $(G(k,x))^{x+1}<G(k+3,x)$

证：

(1)

对任意 $k_1<k_2$，有

$$\frac{G(k_2,x)}{G(k_1,x)}=\frac{\underbrace{2^{\cdot^{\cdot^{\cdot^{2^x}}}}}_{k_2个2}}{ \underbrace{2^{\cdot^{\cdot^{\cdot^{2^x}}}}}_{k_1个2}} >1$$

对任意 $x_1<x_2$，有

$$\frac{G(k,x_2)}{G(k,x_1)}=\frac{\underbrace{2^{\cdot^{\cdot^{\cdot^{2^{x_2}}}}}}_{k个2}}{ \underbrace{2^{\cdot^{\cdot^{\cdot^{2^{x_1}}}}}}_{k个2}} >1$$

(2)

对 $k$ 进行数学归纳。

当 $k=0$时，

$$\frac{G(k+2,x)}{(x+1)G(k,x)}=\frac{2^{2^x}}{(x+1)x}>1$$

假设 $k=t$时成立，即

$$G(t+2,x)>(x+1)G(t,x)$$

当 $k=t+1$时，有

$$\begin{align} \frac{G(t+3,x)}{(x+1)G(t+1,x)} &=\frac{G(t+2,2^x)}{(x+1)G(t,2^x)} \\\\ &>\frac{(2^x+1)G(t,2^x)}{(x+1)G(t,2^x)} \\\\ &=\frac{2^x+1}{x+1} \\\\ &>1 \end{align}$$

(3)

对 $k$ 进行数学归纳。

当 $k=0$时，

$$\frac{G(k+3,x)}{G(k,x)^{x+1}}=\frac{2^{2^{2^x}}}{x^{x+1}}$$

对 $x$ 作归纳，易证 $\frac{2^{2^{2^x}}}{x^{x+1}}>1$

假设 $k=t$时成立，即

$$G(t+3,x)>(G(t,x))^{x+1}$$

当 $k=t+1$时，有

$$\begin{align} \frac{G(t+4,x)}{G(t+1,x)^{x+1}} &=\frac{G(t+3,2^x)}{G(t,2^x)^{x+1}} \\\\ &>\frac{G(t,2^x)^{2^x+1}}{G(t,2^x)^{x+1}} \\\\ &>\frac{G(t,2^x)^{x+1}}{G(t,2^x)^{x+1}} \\\\ &=1 \end{align}$$