第 1 讲 · 集合、函数、归纳与形式语言

这门课开头讲集合和函数，不是要重新上一遍集合论，而是为了回答一个更重要的问题：数学命题到底在什么对象上说话，符号又指什么？

集合给出对象范围

集合由元素唯一确定，顺序和重复都不影响集合本身：

$$\{1,2,2\}=\{2,1\}=\{1,2\}.$$

常用关系与运算是：

$$A\subseteq B,\qquad A=B,$$ $$A\cup B,\qquad A\cap B,\qquad A\setminus B,$$

以及笛卡尔积

$$A\times B=\{(a,b)\mid a\in A,\ b\in B\}.$$

笛卡尔积有顺序。若 $A=\{1,2\}$、$B=\{x\}$，则

$$A\times B=\{(1,x),(2,x)\},$$

通常不等于 $B\times A$。谓词 $R(x,y)$ 表示二元关系时，它实际上就在某个笛卡尔积的子集上取值。

函数是一类特殊关系

函数 $f:A\to B$ 要求每个 $a\in A$ 都对应唯一的 $f(a)\in B$。这里有两个容易混淆的词：

• 陪域是声明中的 $B$；
• 值域是实际出现的 $\{f(a)\mid a\in A\}$，它只是 $B$ 的子集。

一个 $n$ 元运算可以看成

$$f:A^n\to A.$$

命题联结词也是函数。例如二元联结词把两个真值送到一个真值：

$$F:\{0,1\}^2\to\{0,1\}.$$

因为输入共有 $4$ 种，每一种可独立选择输出 $0$ 或 $1$，所以二元真值函数共有

$$2^{2^2}=16$$

个。一般地，$n$ 元真值函数共有 $2^{2^n}$ 个。

归纳定义和归纳证明不是一回事

归纳定义告诉我们“哪些对象算合法对象”。例如自然数可递归描述为：

1. $0$ 是自然数；
2. 若 $n$ 是自然数，则后继 $s(n)$ 也是自然数；
3. 只有有限次应用上述规则得到的对象才是自然数。

第三条很重要，它排除了凭空塞进来的其他对象。

归纳证明则是在证明某个性质对所有递归生成的对象成立。证明公式性质时，经常按公式复杂度归纳：

1. 先证原子公式；
2. 假设性质对较简单公式成立；
3. 分别处理 $\neg A$、$A\land B$、$A\to B$ 等构造。

这就是课件证明代换定理、对偶性质和语义递归定义时反复使用的套路。

论域不只是一个集合

课件把论域看成一个数学系统。为了理解一句公式，至少要知道：

• 对象集合；
• 在对象上的函数或运算；
• 在对象上的关系。

例如自然数结构可以写成

$$\mathcal N=\langle\mathbb N,0,s,+,\times,\le\rangle.$$

同一串符号在不同结构中可能真假不同：

$$\forall x\,(x\ge 0)$$

在自然数结构中为真，在整数结构中为假。公式没变，模型变了。

从自然语言到形式语言

形式化要把“意思”拆成三层：

1. 对象语言：公式本身，例如 $\forall x(P(x)\to Q(x))$；
2. 理论：作为出发点的一组公理；
3. 模型：给符号指定对象、函数和关系，使公式获得真假。

“每个自然数都有后继”可以写成

$$\forall x\bigl(N(x)\to\exists y(N(y)\land y=s(x))\bigr).$$

写公式时没有证明它为真；只有给定自然数结构并检查解释后，才能谈真假。

形式系统为什么不看含义

形式系统只处理符号串。一个证明步骤是否合法，取决于它是不是：

• 公理；
• 前提；
• 由规定的推理规则从前面步骤得到。

证明过程不需要知道 $P$ 表示“下雨”还是“程序终止”。正因为推理只依赖形式，一套证明才能被复用到所有具体含义中。

这也解释了整门课的分工：

• 语义研究公式在赋值和模型下是否为真；
• 语法研究公式能否由公理和规则推出；
• 可靠性与完备性研究这两套判断是否吻合。

后面所有内容都围绕这条主线展开。