跳转至

算数 (Arithmetic)

接下来我们要讨论的主要语言是一阶算数语言 \(L_\Omega\) ，以及标准 \(L_\Omega\) 结构：

\[ \Omega := (\omega,<,+,\times ,\mathrm{Sc},0) \]

一阶算数语言 \(L_\Omega\) 的非逻辑符号有 \(\dot{<},\dot{+},\dot{\times},\dot{\mathrm{S}},\dot{0}\) . 一阶算数理论即为 \(\mathrm{Th}(\Omega)\) ，这实际上是一个复杂的理论，在数论中研究的主要对象就是它，即使是一些比较简单的语句，可能都难以判定真伪.

例如数论中的一个 Open Problem 就是是否存在无穷多个素数 \(p\) ，使得 \(p,p+2\) 均为素数. 如果将这个语句记为 \(\theta_{\mathrm{TP}}\) ，那么我们目前唯一能确定的一件事情就是 \(\theta_{\mathrm{TP}}\) 和 \(\neg \theta_{\mathrm{TP}}\) 总有且仅有一个成立，这是理论 \(\mathrm{Th}(\Omega)\) 完全带来的.

Peano 假设 (Postulate)

我们暂且不进行那么复杂理论的讨论，我们将其放宽为：\(\mathrm{Th}((\omega,\mathrm{Sc},0))\) 以及它的语言 \(L_{\mathrm{Sc},0}\) ，也就是说只有 \(0\) 和后继的函数.

Dedekind 为了将逻辑学基础公理化，提出了三个假设，现在称为 Peano 假设，它将 \((\omega,\mathrm{Sc},0)\) 刻画到同构：

  1. \(0\) 不为任何对象的后继. (P1)
  2. 后继函数是单射. (P2)
  3. 对于任意集合 \(X \subseteq \omega\) ，如果 \(0\in X\) 且 \(X\) 在后继函数的意义下封闭，那么 \(X = \omega\) . (P3)

上述三条为 Peano 假设. 但是它是一个自然语言的描述，我们将前两条换为形式逻辑的语言：

  1. \(\forall x (\neg 0 = \dot{\mathrm{S}} x)\) . (S1)
  2. \(\forall x \forall y (\dot{\mathrm{S}}x=\dot{\mathrm{S}}y\to x=y)\) . (S2)

注意这两条在其他的结构当中也可能成立，例如对于 \((\omega,\mathrm{Sc}_k,0)\) ，其中 \(\mathrm{Sc}_k(m)=m+k\) . 因此我们还需第三条.

第 \(3\) 条无法翻译为 \(L_{\mathrm{Sc,0}}\) 语句，因为如同我们之前对于二阶逻辑的一个介绍，第 \(3\) 条涉及到了对 \(\omega\) 任意子集的量词作用，所以它是一个二阶逻辑的陈述. 暂且不考虑正式性，我们不妨写为：

  • 对于所有的 \(p\) ，\([p\dot{0}\land \forall x (px\to p \dot{\mathrm{S}}x)]\to \forall x px\) . (P3')

这里 \(p\) 是一个一元关系，所有的 \(p\) 指代了所有的子集. 从而，我们有如下定理：

命题

所有满足 (S1) ，(S2) 和 (P3') 的模型 \((A,\mathrm{Sc}_A,0_A)\) 都和 \((\omega,\mathrm{Sc},0)\) .

递归定义函数 \(\eta: \omega\to A\) 如下：

\[ \eta(0) = 0_A \text{ and } \eta(\mathrm{Sc}(n)) = \mathrm{Sc}_A(\eta(n)). \]

先证明单同态，如果 \(\eta(n) = \eta(m)\) ，二者只有其中一个为 \(0\) 不成立是显然的，考虑 \(\eta(\mathrm{Sc}(n')) = \eta(\mathrm{Sc}(m'))\) 有

\[ \mathrm{Sc}_A(\eta(n')) = \mathrm{Sc}_A(\eta(m')) \]

由 \(\mathfrak{A} = (A,\mathrm{Sc}_A,0_A)\) 也满足 Peano 假设可得 \(\eta(n') = \eta(m')\) ，从归纳的角度看我们实际上将它们往回推了一位，递推可得为单射.

再证明是满射，令 \(B = \left\lbrace \eta(n): n\in \omega \right\rbrace\) ，那么 \(0_A\in B\) 且 \(B\) 在 \(\mathrm{Sc}_A\) 的意义下封闭，因为 \(\mathfrak{A}\) 是 (P3') 的模型，可得 \(B=A\) . \(\square\)

范畴

定义：范畴

对于任意的理论 \(T\) ：

  1. 如果 \(T\) 的任意模型 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) 都有 \(\mathfrak{A}\simeq \mathfrak{B}\) ，则称 \(T\) 是范畴的 (categorical)
  2. 对于任意基数 \(\kappa\) ，如果对于 \(T\) 的任意模型 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) ，当它们基数均为 \(\kappa\) 时，就有 \(\mathfrak{A}\simeq \mathfrak{B}\)，则称 \(T\) 是 \(\kappa\)-范畴的 (\(\kappa\)-categorical) .

\(\kappa\) (kappa) 范畴主要还是说明了如果基数等于 \(\kappa\) ，就相互之间同构这一个性质.
Hinman 一书中使用的可数基数为 \(\aleph_0\) ，我们在这里沿用其记号.

性质

对于任意的语言 \(L\) 和任意 \(L\) 理论 \(T\) ，

  1. 如果 \(T\) 是完全的且有有限模型，那么 \(T\) 是范畴的；
  2. 如果 \(L\) 是可数的且 \(T\) 有一个不可数模型，那么 \(T\) 不是范畴的；
  3. 如果 \(L\) 可数，\(T\) 相容，且没有有限模型，还是 \(\aleph_0\) 范畴的，那么 \(T\) 是完全的.
  4. 所有的 \(L_=\) 理论是 \(\kappa\) 范畴的，其中 \(\kappa\) 为任意无穷基数.
  5. \(T_{\mathrm{DLO}}\) 的四个完全延拓都是 \(\aleph_0\) 范畴的.

评论