1.1. 一阶语言

首先, 我们来描述什么是自然数.

定义 1.1.0.1 (自然数). $0, 1, 2, 3, ..., 10, 11, ...$ 这些符号用来表示我们直觉接受的自然数.

当我们需要一个任意的自然数时, 我们会用小写字母 $k, l, m, n$ 之一表达. 在没有特别标注时, 它们一定是任意自然数的意思.

如果我们有一种方法, 任给自然数 $n$ 均可由这一方法确定唯一的自然数 $m$ , 则称这个方法是一个自然数到自然数的函数, 用 $a$ 表示. 这一方法从 $n$ 确定的自然数 $m$ 记为 $a (n)$ .

我们默认一切初等数论知识, 包括但不限于: 加法、乘法、数学归纳法、整除、素数、算术基本定理、同余、中国剩余定理.

评注. 对于自然数的标准性、我们如何认知自然数, 什么是自然数的相等, 以及为何允许谈论任意自然数, 什么是自然数到自然数的函数, 请看本章末尾的注记. 今后不再特别指出.

我们的一切定义都基于自然数. 现在, 我们来指定语言中允许的字符表.

定义 1.1.0.2 (一阶语言的字符). 一阶语言的字符表被我们列举如下:

1.	变元符号 $x_{m}$ , 任意变元用 $w, x, y, z$ 表达.
2.	函数符号 $f_{m}$ , 任意函数符号用 $f, g, h$ 表达.
3.	谓词符号 $P_{m}$ , 任意谓词符号用 $P$ 表达.
4.	逻辑连接词符号 $\neg, \to$ , 读作否定和蕴含.
5.	量词符号 $\forall$ , 读作对所有 (for all).
6.	括号 $(,)$ .

这里 $m$ 总是跑遍自然数, 换言之任给自然数 $m$ 均有一个自由变元符号 $x_{m}$ , 一个 $n$ 元函数符号 $f_{m}$ 和一个谓词符号 $P_{m}$ .

我们还有自然数到自然数的两个函数: 函数元数指示器 $a_{f}$ , 谓词元数指示器 $a_{P}$ . 它们不是字符表中的字符. 我们称 $a_{f} (m)$ 是 $f_{m}$ 的元数, $a_{P} (m)$ 是 $P_{m}$ 的元数.

我们还有两个自然数: 函数个数 $n_{f}$ 与谓词个数 $n_{P}$ . 我们总是只考虑下标 $m < n_{f}$ 的函数符号 $f_{m}$ 与下标 $m < n_{P}$ 的谓词符号 $P_{m}$ .

我们总是特别地要求 $n_{P} \geq 1$ , $a_{P} (0) = 2$ 且记 $P_{0}$ 为 $\approx$ . 如果一个 $m < n_{f}$ 使得 $a_{f} (m) = 0$ , 则称 $f_{m}$ 是一个常数符号.

一个四元组 $(n_{f}, n_{P}, a_{f}, a_{P})$ 称作一个一阶语言 $L$ . 以下我们总是默认选定了一个一阶语言.

评注. 我们也可以认为上面全部都是奇数: $\forall$ 是第一个奇数 $1$ , $(,)$ 是后面两个奇数 $3$ 和 $5$ , $\neg, \to$ 是再后面的两个奇数 $7, 9$ , $x_{m}, f_{m}, p_{m}$ 是 $6 m + 11, 6 + 13$ 和 $6 m + 15$ .

接下来, 我们直觉地指出一个概念.

定义 1.1.0.3 (字符串). 我们归纳地定义一个字符表下长度为任意自然数 $n$ 的字符串:

1.	长度为 $0$ 的字符串是空串.
2.	长度为 $n + 1$ 的字符串是长度为 $n$ 的字符串在后面串接一个字符表中的字符得到的新字符串.

进一步, 我们可以定义字符串的串接, 串接后的字符串长度变为被串接的两字符串长度之和.

我们认为这一递归定义确实归纳地指出所有的字符串.

评注. 我们也可以认为字符串是自然数: 长度 $0$ 的字符串是 $1$ , 长度 $n$ 的作为自然数的字符串 $t$ 串接作为自然数的字符 $m$ 得到的长度 $n + 1$ 的字符串对应的自然数是 $t \times p_{n}^{m + 1}$ , 这里 $p_{n}$ 是第 $n$ 个质数.

有了字符串的概念, 我们就可以定义我们所需的语言中的对象了.

定义 1.1.0.4 (项). 我们递归定义以下形式的字符串为项:

1.	$x$ 是项.
2.	若 $f = f_{m}$ 是函数符号, $n = a_{f} (m)$ 是函数 $f$ 的元数, $t_{1}, ..., t_{n}$ 是 $n$ 个项, 则 $f (t_{1}, ..., t_{n})$ 是项.

我们认为这一递归定义确实归纳地指出所有的项. 项通常用 $s, t$ 表达.

评注. 这一递归定义成立是因为它事实上定义了一些满足要求的自然数, 这些自然数对应的字符串就是项. 以下的递归定义和归纳法都因此成立.

定义 1.1.0.5 (公式). 我们递归定义以下形式的字符串为公式:

1.	若 $P = P_{m}$ 是谓词符号, $n = a_{P} (m)$ 是谓词 $P$ 的元数, $t_{1}, ..., t_{n}$ 是 $n$ 个项, 则 $P (t_{1}, ..., t_{n})$ 是公式.
2.	若 $φ$ 是公式, 则 $\neg φ$ 是公式.
3.	若 $φ$ 与 $ψ$ 是公式, 则 $(φ \to ψ)$ 是公式.
4.	若 $φ$ 是公式, $x$ 是变元, 则 $\forall x (φ)$ 是公式.

我们认为这一递归定义确实归纳地指出所有的公式. 公式通常用 $φ, ϕ, ψ$ 表达. 我们称形如 $P (t_{1}, ..., t_{n})$ 的公式为原子公式.

项和公式是我们要处理的全部语言对象. 它们本质上是满足特定规则的字符串. 接下来, 我们来给出它们的一些性质.

定义 1.1.0.6 (自由出现). 对每个 $m$ , 我们可以对所有项和所有公式讨论 $x_{m}$ 在其中的自由出现性. 对项 $t$ 而言, $x_{m}$ 在 $t$ 中自由出现当且仅当字符 $x_{m}$ 在字符串 $t$ 中出现. 对公式而言, 归纳定义:

1.	形如 $P (t_{1}, ..., t_{n})$ 的公式, $x_{m}$ 在其中自由出现当且仅当它在这个字符串中出现.
2.	形如 $\neg φ$ 的公式, $x_{m}$ 在其中自由出现当且仅当它在 $φ$ 中自由出现.
3.	形如 $(φ \to ψ)$ 的公式, $x_{m}$ 在其中自由出现当且仅当它在 $φ$ 中自由出现或它在 $ψ$ 中自由出现.
4.	形如 $\forall x (φ)$ 的公式, $x_{m}$ 在其中自由出现当且仅当它在 $φ$ 中自由出现且 $x$ 不是 $x_{m}$ .

对项 $t$ , 我们通常将其中自由出现的变元全部列出, 记为 $t (x_{m_{1}}, ..., x_{m_{n}})$ , 这里 $m_{1}, ..., m_{n}$ 是有限个互不相同的自然数. 对公式 $φ$ , 我们同样将其中自由出现的变元全部列出, 记为 $φ (x_{m_{1}}, ..., x_{m_{n}})$ . 为了方便, 我们又会记 $(x_{m_{1}}, ..., x_{m_{n}})$ 为 $(y_{1}, ..., y_{n})$ 以忽略具体的 $m_{1}, ..., m_{n}$ 的值.

评注. 这一递归定义成立的理由仍然需要我们回到它们对应的自然数上去论证.

定义 1.1.0.7 (替换). 给定变元 $x$ 与项 $t$ , 我们定义一个操作 $sub_{t}^{x}$ , 它递归地将公式变为另一个公式:

1.	形如 $P (t_{1}, ..., t_{n})$ 的公式 $ϕ$ , $sub_{t}^{x} (ϕ)$ 是 $ψ$ 这一字符串中所有 $x$ 出现的地方都将 $x$ 替换为 $t$ 得到的新公式.
2.	形如 $\neg φ$ 的公式 $ϕ$ , $sub_{t}^{x} (ϕ)$ 是 $\neg sub_{t}^{x} (φ)$ .
3.	形如 $(φ \to ψ)$ 的公式 $ϕ$ , $sub_{t}^{x} (ϕ)$ 是 $(sub_{t}^{x} (φ) \to sub_{t}^{x} (ψ))$ .
4.	形如 $\forall y (φ)$ 的公式 $ϕ$ , 若 $y = x$ 则 $sub_{t}^{x} (ϕ)$ 仍然是是 $ϕ$ , 若 $y \neq = x$ 则 $sub_{t}^{x} (ϕ)$ 是 $\forall y (sub_{t}^{x} (φ))$ .

我们还要禁止一些改变语义 (虽然我们现在还没有严格定义语义) 的替换操作, 因此我们继续递归地对每个公式 $ϕ$ 定义 $sub_{t}^{x}$ 对 $ϕ$ 是否是无冲突替换.

1.	形如 $P (t_{1}, ..., t_{n})$ 的公式 $ϕ$ , $sub_{t}^{x}$ 对 $ϕ$ 总是无冲突替换.
2.	形如 $\neg φ$ 的公式 $ϕ$ , $sub_{t}^{x}$ 对 $ϕ$ 是无冲突替换当且仅当 $sub_{t}^{x}$ 对 $φ$ 是无冲突替换.
3.	形如 $(φ \to ψ)$ 的公式 $ϕ$ , $sub_{t}^{x}$ 对 $ϕ$ 是无冲突替换当且仅当 $sub_{t}^{x}$ 对 $φ$ 和 $ϕ$ 都是无冲突替换.
4.	形如 $\forall y (φ)$ 的公式 $ϕ$ , $sub_{t}^{x}$ 对 $ϕ$ 是无冲突替换当且仅当 $x$ 不在 $ϕ$ 中自由出现, 或 $sub_{t}^{x}$ 对 $φ$ 是无冲突替换且 $y$ 不在 $t$ 中出现.

评注. 我们写 $x = y$ 指的是这两个字符是同一个字符, 这与公式 $x \approx y$ 即 $P_{0} (x, y)$ 并不是一个意思.

以上定义了为了能讨论证明这一概念所需要的所有前置概念.

名字空间

视图

1.1. 一阶语言