\[ \def\Th{\mathrm{Th}} \def\Cn{\mathrm{Cn}} \def\Mod{\mathrm{Mod}} \def\A{\mathfrak{A}} \def\B{\mathfrak{B}} \def\N{\mathfrak{N}} \def\K{\mathcal{K}} \def\lh{\mathrm{lh}} \]
本节知识点
教材 3.3 数论的子理论
习题 1：证明：在结构 \(( \mathbb{N}; \cdot, E)\) 中，我们能够定义加法关系 \(\set{\langle m, n, m+n\rangle | m, n \in \mathbb{N}}\)。进一步证明在结构 \(\set{0}\) 中，序关系 \(<\)，后继关系 \(\set{\langle n, S(n) \rangle | n \in \mathbb{N}}\) 都是可定义的。(说明：如果把结构 \(( \mathbb{N}; \cdot, E)\) 简化为 \(( \mathbb{N}; E)\), 这个结果还能加强。在此处，乘法关系可以通过指数运算的一个法则: \((d^a)^b = d^{ab}\) 来定义。）
证明：在算数关系中，很容易使用对数将乘法转化为加法。例如 \(\log(nm) = \log(n) + \log(m)\)。利用这一思路，定义加法关系为 \(\set{\langle n, m, p\rangle | 2En \cdot 2Em = 2Ep}\)，其中 \(2 = S^20\)。
在结构 \(\set{0}\) 中，定义序关系为 \(\set{\langle n, m\rangle | \exists x (x + x \neq x \land n + x = m)}\)；
在算数关系中，后继可以用 \(m = n+1\) 表示，只要构造 \(x=1\) 即可。
定义后继关系为 \(\set{\langle n, m\rangle | \exists x (x + x \neq x \land \forall y \forall z (y+y\neq y \to z+z \neq z \to y+z\neq x) \land n + x = m)}\)。
\(Q.E.D.\)
习题 2（不考）：证明定理 33C, 即（在 \(\N\) 中）真的无量词句子都是 \(A_E\) 的定理。
证明：
首先，令 \(\tau\) 是一个原子句子。那么，\(\tau = t < u\) 或 \(\tau = t = u\)，其中 \(t\) 和 \(u\) 是不含变量的项。根据引理 33B，存在 \(m\) 和 \(n\) 使得 \(A_E \vdash t = S^m 0\) 和 \(A_E \vdash u = S^n 0\)。进一步地，\(A_E \vdash S^m 0 = S^n 0\) 当且仅当 \(m = n\)，而 \(A_E \vdash S^m 0 \neq S^n 0\) 当且仅当 \(m \neq n\)（根据 S1 和 S2），并且，利用这一点，根据引理 33A，\(A_E \vdash S^m 0 < S^n 0\) 当且仅当 \(m < n\)，而 \(A_E \vdash S^m 0 \not< S^n 0\) 当且仅当 \(m \geq n\)。利用这些事实，我们可以证明 \(A_E \vdash t < u\) 当且仅当 \(m < n\)，而 \(A_E \vdash \neg t < u\) 当且仅当 \(m \geq n\)，并且 \(A_E \vdash t = u\) 当且仅当 \(m = n\)，而 \(A_E \vdash \neg t = u\) 当且仅当 \(m \neq n\)。例如，对于 \(m < n\)，\(A_E \vdash \forall x \forall y \forall z (x = y \rightarrow x < z \rightarrow y < z)\) 和 \(A_E \vdash \forall x \forall y \forall z (x = y \rightarrow z < x \rightarrow z < y)\)（演绎公理组 6，DA6），并且利用 DA2，我们可以推导出 \(A_E \vdash S^m 0 = t \rightarrow S^m 0 < S^n 0 \rightarrow t < S^n 0\) 和 \(A_E \vdash S^n 0 = u \rightarrow t < S^n 0 \rightarrow t < u\)，并且类似地对于 \(A_E \vdash \neg u = t\) 和 \(A_E \vdash \neg u < t\)。
其次，令 \(\tau\) 是一个形式为 \(\neg \tau_1\) 或 \(\tau_2 \rightarrow \tau_3\) 的句子，并且在 \(\mathfrak{A}\) 中为真，其中 \(\tau_i\) 是使得 \(A_E \vdash \tau_i\) 当且仅当 \(\tau_i\) 在 \(\mathfrak{A}\) 中为真，而 \(A_E \vdash \neg \tau_i\) 当且仅当 \(\tau_i\) 在 \(\mathfrak{A}\) 中为假。我们证明同样的结论也适用于 \(\tau\)。确实，如果 \(\tau\) 在 \(\mathfrak{A}\) 中为真，那么分别地，\(\tau_1\) 在 \(\mathfrak{A}\) 中为假，而 \(\tau_2\) 在 \(\mathfrak{A}\) 中为假或 \(\tau_3\) 在 \(\mathfrak{A}\) 中为真，这意味着 \(A_E \vdash \neg \tau_1\)，并且 \(A_E \vdash \neg \tau_2 \lor \tau_3\)，即 \(A_E \vdash \tau\)；否则，\(\tau_1\) 在 \(\mathfrak{A}\) 中为真，而 \(\tau_2\) 在 \(\mathfrak{A}\) 中为真，\(\tau_3\) 在 \(\mathfrak{A}\) 中为假，这意味着 \(A_E \vdash \neg \neg \tau_1\)，并且 \(A_E \vdash \neg (\neg \tau_2 \lor \tau_3)\)，即 \(A_E \vdash \neg \tau\)。
\(Q.E.D.\)
习题 5（不考）：证明：序列数字的集合是可表示的（编目 10）。
证明：序列数的集合定义为 $ = { b x (x b x y (y < x y ) } $，其中 $ $ 是素数的集合，而 $ $ 是可整除关系。换句话说，如果某个素数 $ x $ 能整除 $ b $，那么所有小于 $ x $ 的素数 $ y $ 也能整除 $ b $。特别地，这在 $ b = 1 = $ 和 $ b = 2 = $ 时是显然成立的。通过目录项 0、3、4 和 5，我们得出结论 $ $ 是可表示的。
\(Q.E.D.\)
习题 6（不考）：3 是序列数字吗？\(\lh 3\) 等于多少？求出 \((1 \ast 3) \ast 6\) 和 \(1 \ast (3 \ast 6)\)。
\(3 = 2^0 \cdot 3^1\) 是不是一个序列数，因为 $ p_1 = 3 $ 能整除 3，但 $ p_0 = 2 $ 不能整除 3。然而，形式上，我们仍然可以计算问题中的公式。
首先，形式上，\(\text{lh} b\) 定义为最小的 $ n $，使得要么 $ b = 0 $，要么 $ < p_n, b > $，其中 \(\mathcal{D}\) 是可整除关系。在我们的例子中，$ < p_0, 3 > $，因此 \(\text{lh} 3 = 0\)。
其次，形式上，\((b)_c\) 定义为最小的 $ n $，使得要么 $ b = 0 $，要么 $ < p_c^{n+2}, b > \(。在我们的例子中，\)(3)_c = 0$ 对所有 $ c $（包括 $ c = 1 $ 时 $ p_1 = 3 $）。
最后，$ a * b = a _{i < b} p_i^{(b)i + 1} $ 对所有自然数也定义。特别地，由于 \(\text{lh} 1 = 0\)，$ 1 * b = {i < b} p_i^{(b)i + 1} $，这仅仅是能整除 $ b $ 的最大序列数。因此，$ 1 * 3 = 1 $ 和 $ (1 * 3) * 6 = 6 \(（\) 6 = , 0 $ 是一个序列数）。进一步，$ 3 * 6 = 3 {i < 2} p_i^{(6)_i + 1} = 3 = 18 = 2^1 ^2 = < 0, 1 > \(。因此，\) 1 * (3 * 6) = 18 $。
习题 10：设 $ R $ 是可表示的关系，$ g $ 和 $ h $ 是可表示的函数。证明：$ f $ 是可表示的，其中 \[ f(\bar{a}) = \begin{cases} g(\bar{a}) & \text{若 } \bar{a} \in R, \\ h(\bar{a}) & \text{若 } \bar{a} \notin R. \end{cases} \]
证明：函数 $ f $ 可以表示为组合（定理 33L）$ d(g(), h(), K_R()) $，其中 $ g $, $ h $, $ K_R $（目录项 1），且 $ d(x, y, z) = x z + y (1 - z) $ 是可表示的。
\(Q.E.D.\)
